Histogram-based embedding for learning on statistical manifolds

A novel binning and learning framework is presented for analyzing and applying large data sets that have no explicit knowledge of distribution parameterizations, and can only be assumed generated by the underlying probability density functions (PDFs) lying on a nonparametric statistical manifold. For models’ discretization, the uniform sampling-based data space partition is used to bin flat-distributed data sets, while the quantile-based binning is adopted for complex distributed data sets to reduce the number of under-smoothed bins in histograms on average. The compactified histogram embedding is designed so that the Fisher–Riemannian structured multinomial manifold is compatible to the intrinsic geometry of nonparametric statistical manifold, providing a computationally efficient model space for information distance calculation between binned distributions. In particular, without considering histogramming in optimal bin number, we utilize multiple random partitions on data space to embed the associated data sets onto a product multinomial manifold to integrate the complementary bin information with an information metric designed by factor geodesic distances, further alleviating the effect of over-smoothing problem. Using the equipped metric on the embedded submanifold, we improve classical manifold learning and dimension estimation algorithms in metric-adaptive versions to facilitate lower-dimensional Euclidean embedding. The effectiveness of our method is verified by visualization of data sets drawn from known manifolds, visualization and recognition on a subset of ALOI object database, and Gabor feature-based face recognition on the FERET database.     

A new variable-sized bin packing problem

The problem of BLASTing a genome against a database of DNA sequences to identify potential relationships with other genomes can be divided into subproblems quite naturally. We consider a setting where the problem is distributed to PCs having idle time. This results in a new variant of bin packing, where a rectangle is divided into smaller rectangles that are to be packed in variable-sized bins which arrive on-line. A rectangle fits in a bin, if the sum of its height and width is no more than the size of the bin. The goal is to minimize the total size of the bins used for packing the entire rectangle.     

基于流形嵌入的宏基因组叠连群分箱方法研究

宏基因组组装往往只能得到较长片段的叠连群,无法恢复完整的基因组.现有的一些分箱方法并未充分挖掘叠连群序列组成和样本覆盖度内部结构信息.开发了基于流形嵌入的宏基因组学叠连群分箱方法,可以挖掘出高维数据中内部的非线性结构特征,从而降低数据的维度,提高计算性能.使用流形嵌入的结果估计出初始分箱数,比使用基于单拷贝基因的分箱数...     

Recipes for Spatial Statistics with Global Datasets: A Martian Case Study

The Mars Odyssey Gamma Ray Spectrometer has yielded planetary data of global extent. Such remote-sensing missions usually assign the value of a continuous-valued geospatial attribute to a uniform latitude-longitude grid of bins. Typical attributes include elemental-mass fraction, areal fraction of a mineral type, areal fraction of rocks, thermal inertia, etc. The fineness of the grid is chosen according to the spatial resolution of the orbiter and concomitant data processing. We describe methods to maximize the information extracted from both bin and regional data. Rigorous use of statistical parameters and related methods for inter- and intra- regional comparisons are also discussed. While we discuss results from the Mars Odyssey mission, the techniques we describe are applicable whenever continuous-valued attributes of a planet’s surface are characterized with bins and regions. Our goal is to distill the simplest statistical methods for regional comparisons that would be intuitively accessible to planetary scientists.     

Theoretical model and implementation of a real time intelligent bin status monitoring system using rule based decision algorithms

Due to the rising trend of urbanization along with overconsumption of non-recyclable resources, the volume of municipal solid waste is increasing every day. An efficient, cost effective and environment friendly solution for real time bin status monitoring, collection and transportation of municipal solid waste is still a major challenge to the local municipal authorities. This research proposes a novel model, architecture and intelligent sensing algorithm for real time solid waste bin monitoring system that would contribute to the solid waste collection optimization. The monitoring application is based on decision algorithms for sensing solid waste data in a wireless sensor network. The system is built on a three level architecture like smart bin, gateway and control station. The elementary concept is that, smart bins collect their status when any changes occur and transmit the status data to a server via an intermediate coordinator. A set of applications in server presents the updated bin status on real time. The field test performances show that the system can efficiently monitor real time bin status that makes it feasible to decide, which bin should collect and which should not. Thus the proposed system has achieved its goal to provide real time bin status information to the solid waste management operator. Later, this information can be used for collection route optimization to reduce collection costs and carbon emissions which in turn contribute to build green society.     

Approximation Algorithms for Extensible Bin Packing

In a variation of bin packing called extensible bin packing, the number of bins is specified as part of the input, and bins may be extended to hold more than the usual unit capacity. The cost of a bin is 1 if it is not extended, and the size if it is extended. The goal is to pack a set of items of given sizes into the specified number of bins so as to minimize the total cost. Adapting ideas Grötschel et al. (1981), Grötschel et al. (1988), Karmarkar and Karp (1982), Murgolo (1987), we give a fully polynomial time asymptotic approximation scheme (FPTAAS) for extensible bin packing. We close with comments on the complexity of obtaining stronger results.     

Embedding in medical images with contrast enhancement and tamper detection capability

This paper presents an efficient data hiding technique capable of providing improved visual quality of watermarked images, besides having the ability to detect the tamper, if any. It is a spatial domain approach in which major emphasis is on improving the visual quality rather than increasing the PSNR or the embedding capacity. The medical images have been divided into Region of Interest (ROI) and Non-Region of Interest (NROI). Bringing out details that lie within the low dynamic range is very important in medical images for effective diagnosis. ROI being diagnostically critical region is enhanced using contrast stretching and subsequently, data is reversibly embedded into the peak bins of ROI. Only those peak bins are employed for reversible data embedding that have an adjacent empty bin to overcome the problem of overflow and underflow. In NROI, the uniform intensity and redundant information region, Least Significant Bit (LSB) embedding is employed for increasing the payload. For tamper detection, a fragile watermark has been embedded in the ROI. To evaluate the scheme various parameters like peak signal to noise ratio (PSNR), No-Reference Quality Metric for contrast-distorted images (NR-CDIQA) and Structural Similarity Index Matrix (SSIM) have been calculated. The experimental results show a remarkable increase in visual quality compared to state-of-art.

     

Online bin stretching with three bins

Online bin stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack the bins. The goal is to minimize the amount of overpacking, i.e., the maximum size packed into any bin. We give an algorithm for online bin stretching with a stretching factor of \(11/8 = 1.375\) for three bins. Additionally, we present a lower bound of \(45/33 = 1.\overline{36}\) for online bin stretching on three bins and a lower bound of 19/14 for four and five bins that were discovered using a computer search.     

分布式电源并网对配电网电流保护影响的研究

分析了分布式电源并网对传统的配电网电流保护的影响,采用Matlab/Simulink仿真软件验证了分布式电源容量不同、并网位置不同对配电网各段电流保护的影响,提出了一种能够满足分布式电源并网后配电网保护要求的改进方案。该改进方案实现原理:对于分布式电源下游的保护,将供电系统电源和分布式电源作为一个整体,重新整定各段电流保护的整定值;对于分布式电源上游的保护,需在各保护装置上安装一个基于故障电流分量的方向元件,只有当保护中的过流元件和方向元件同时启动时,保护才能够可靠动作。     

Binning schemes for partition-based compound selection

Partition-based approaches to the selection of structurally diverse sets of compounds involve allocating compounds to the individual elements of a multidimensional grid that spans the available chemical space. The space is defined by an appropriate set of chemical properties, with subranges of the values of these properties being used to define the constituent elements, or bins. This article compares several binning schemes in terms of their ability to provide an even distribution of compounds across the available space and to maximise the numbers of active molecules identified in simulated assay experiments.     

Optimal data-based binning for histograms and histogram-based probability density models

Histograms are convenient non-parametric density estimators, which continue to be used ubiquitously. Summary quantities estimated from histogram-based probability density models depend on the choice of the number of bins. We introduce a straightforward data-based method of determining the optimal number of bins in a uniform bin-width histogram. By assigning a multinomial likelihood and a non-informative prior, we derive the posterior probability for the number of bins in a piecewise-constant density model given the data. In addition, we estimate the mean and standard deviations of the resulting bin heights, examine the effects of small sample sizes and digitized data, and demonstrate the application to multi-dimensional histograms.     

Approximation Schemes for Packing Splittable Items with Cardinality Constraints

We continue the study of bin packing with splittable items and cardinality constraints. In this problem, a set of n items must be packed into as few bins as possible. Items may be split, but each bin may contain at most?k (parts of) items, where k is some given parameter. Complicating the problem further is the fact that items may be larger than?1, which is the size of a bin. The problem is known to be strongly NP-hard for any fixed value of?k. We essentially close this problem by providing an efficient polynomial-time approximation scheme (EPTAS) for most of its versions. Namely, we present an efficient polynomial time approximation scheme for k=o(n). A?PTAS for k=Θ(n) does not exist unless P = NP. Additionally, we present dual approximation schemes for k=2 and for constant values of?k. Thus we show that for any ε>0, it is possible to pack the items into the optimal number of bins in polynomial time, if the algorithm may use bins of size 1+ε.     

Using self-organizing maps to learn geometric hash functions formodel-based object recognition

A major problem associated with geometric hashing and methods which have emerged from it is the nonuniform distribution of invariants over the hash space. In this paper, a new approach is proposed based on an elastic hash table. We proceed by distributing the hash bins over the invariants. The key idea is to associate the hash bins with the output nodes of a self-organizing feature map (SOFM) neural network which is trained using the invariants as training examples. In this way, the location of a hash bin in the space of invariants is determined by the weight vector of the node associated with the hash bin. The advantage of the proposed approach is that it is a process that adapts to the invariants through learning. Hence, it makes absolutely no assumptions about the statistical characteristics of the invariants and the geometric hash function is actually computed through learning. Furthermore, SOFM's topology preserving property ensures that the computed geometric hash function should be well behaved.     

基于数据网格环境的连接操作算法

数据网格是一种分布式数据管理体系结构，能够为分布在网格中的资源提供协同的管理机制．数据库管理系统在数据网格中发挥着重要作用，在各种数据库操作中，连接操作是一种最常用也是最耗时的操作，到目前为止，尚未有文献提出数据网格环境下的连接操作算法．主要对数据网格环境下海量数据的连接操作算法进行了研究，针对网格中各结点之间网络带宽异构的特点，采取关系缩减算法、行分块传输技术和流水线并行机制来减少查询的响应时间．理论分析和实验结果证明，算法在减少网络通信开销、增加I／0和CPU并行、降低响应时间方面具有较好的性能．     

Selfish Bin Packing

Following recent interest in the study of computer science problems in a game theoretic setting, we consider the well known bin packing problem where the items are controlled by selfish agents. Each agent is charged with a cost according to the fraction of the used bin space its item requires. That is, the cost of the bin is split among the agents, proportionally to their sizes. Thus, the selfish agents prefer their items to be packed in a bin that is as full as possible. The social goal is to minimize the number of the bins used. The social cost in this case is therefore the number of bins used in the packing.     

基于均衡分簇的无线传感器网络压缩数据收集

应用压缩感知（CS）理论结合稀疏随机投影的无线传感器网络（WSN）压缩数据收集（CDG）可以大大减少网络传输的数据量。针对随机选择投影节点作为簇头来收集数据导致网络整体能耗不稳定和不平衡的问题,提出两种平衡投影节点的压缩数据收集方法。对于节点分布均匀WSN,提出基于空间位置的均衡分簇法：首先,均匀划分网格;然后,在每个网格选举投影节点,依距离最短原则成簇;最后,由投影节点收集簇内数据到汇聚节点完成数据收集,从而使得投影节点分布均匀、网络能耗均衡。对于节点分布不均匀的WSN,提出基于节点密度的均衡分簇法：同时考虑节点的位置和密度,对节点数量少的网格不再选择投影节点,将网格内的少量节点分配到邻近的网格,从而平衡网络能量,延长网络寿命。仿真结果表明,与随机投影节点法相比,所提的两种方法的网络寿命均延长了25%以上,剩余节点数在网络运行中期均能达到2倍左右,具有更好的网络连通性,显著提高了整个网络的生命周期。     

Tight bounds for parallel randomized load balancing

Given a distributed system of \(n\) balls and \(n\) bins, how evenly can we distribute the balls to the bins, minimizing communication? The fastest non-adaptive and symmetric algorithm achieving a constant maximum bin load requires \(\varTheta (\log \log n)\) rounds, and any such algorithm running for \(r\in {\mathcal {O}}(1)\) rounds incurs a bin load of \(\varOmega ((\log n/\log \log n)^{1/r})\). In this work, we explore the fundamental limits of the general problem. We present a simple adaptive symmetric algorithm that achieves a bin load of 2 in \(\log ^* n+{\mathcal {O}}(1)\) communication rounds using \({\mathcal {O}}(n)\) messages in total. Our main result, however, is a matching lower bound of \((1-o(1))\log ^* n\) on the time complexity of symmetric algorithms that guarantee small bin loads. The essential preconditions of the proof are (i) a limit of \({\mathcal {O}}(n)\) on the total number of messages sent by the algorithm and (ii) anonymity of bins, i.e., the port numberings of balls need not be globally consistent. In order to show that our technique yields indeed tight bounds, we provide for each assumption an algorithm violating it, in turn achieving a constant maximum bin load in constant time.     

带拒绝箱覆盖问题的局内算法

作为对装箱覆盖问题的推广,提出带拒绝的装箱覆盖问题.设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和费用.物品可以放入箱子也可被拒绝放入箱子,每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少为箱子容量,一旦箱子中的物品长度达到要求则需启用新箱.如果物品被放入箱中,则产生费用.该问题是一个新的组合优化问题,在内部互联网信息管理等问题中有着广泛的应用背景.给出一个求解该问题的局内近似算法C-FF,分析其最坏情况渐近性能比为1/2,并给出了相应的实验结果.     

A Hierarchical Grid Based Framework for Fast Collision Detection

We present a novel hierarchical grid based method for fast collision detection (CD) for deformable models on GPU architecture. A two‐level grid is employed to accommodate the non‐uniform distribution of practical scene geometry. A bottom‐to‐top method is implemented to assign the triangles into the hierarchical grid without any iteration while a deferred scheme is introduced to efficiently update the data structure. To address the issue of load balancing, which greatly influences the performance in SIMD parallelism, a propagation scheme which utilizes a parallel scan and a segmented scan is presented, distributing workloads evenly across all concurrent threads. The proposed method supports both discrete collision detection (DCD) and continuous collision detection (CCD) with self‐collision. Some typical benchmarks are tested to verify the effectiveness of our method. The results highlight our speedups over prior algorithms on different commodity GPUs.     

Comparative study of forward and backward test-kinetic simulation approaches

In this paper we perform a comparative study of the forward and backward Liouville mapping applied to the modeling of ring-shaped and non-gyrotropic velocity distribution functions of particles injected in a sheared electromagnetic field. The test-kinetic method is used to compute the velocity distribution function in various areas of a proton cloud moving in the vicinity of a region with a sharp transition of the magnetic field and a non-uniform electric field. In the forward approach the velocity distribution function is computed for a two-dimensional spatial bin, while in the backward approach the distribution function is averaged over a spatial bin with the same size as for the forward method and using a two-dimensional trapezoidal integration scheme. It is shown that the two approaches lead to similar results for spatial bins where the velocity distribution function varies smoothly. On the other hand, with bins covering regions of configuration space characterized by sharp spatial gradients of the velocity distribution function, the forward and backward approaches will generally provide different results.