OpenRaiser/Intern-Atlas huggingface dataset:
Progressive Processing of Continuous Range Queries in Hierarchical Wireless Sensor Networks
Venue: arXiv cs.DB 2009
Year: 2009

In this paper, we study the problem of processing continuous range queries in a hierarchical wireless sensor network. Contrasted with the traditional approach of building networks in a "flat" structure using sensor devices of the same capability, the hierarchical approach deploys devices of higher capability in a higher tier, i.e., a tier closer to the server. While query processing in flat sensor networks has been widely studied, the study on query processing in hierarchical sensor networks has been inadequate. In wireless sensor networks, the main costs that should be considered are the energy for sending data and the storage for storing queries. There is a trade-off between these two costs. Based on this, we first propose a progressive processing method that effectively processes a large number of continuous range queries in hierarchical sensor networks. The proposed method uses the query merging technique proposed by Xiang et al. as the basis and additionally considers the trade-off between the two costs. More specifically, it works toward reducing the storage cost at lower-tier nodes by merging more queries, and toward reducing the energy cost at higher-tier nodes by merging fewer queries (thereby reducing "false alarms"). We then present how to build a hierarchical sensor network that is optimal with respect to the weighted sum of the two costs. It allows for a cost-based systematic control of the trade-off based on the relative importance between the storage and energy in a given network environment and application. Experimental results show that the proposed method achieves a near-optimal control between the storage and energy and reduces the cost by 0.989~84.995 times compared with the cost achieved using the flat (i.e., non-hierarchical) setup as in the work by Xiang et al.
Information-Theoretic Inequalities on Unimodular Lie Groups
Venue: arXiv cs.IT 2009
Year: 2009

Classical inequalities used in information theory such as those of de Bruijn, Fisher, and Kullback carry over from the setting of probability theory on Euclidean space to that of unimodular Lie groups. These are groups that posses integration measures that are invariant under left and right shifts, which means that even in noncommutative cases they share many of the useful features of Euclidean space. In practical engineering terms the rotation group and Euclidean motion group are the unimodular Lie groups of most interest, and the development of information theory applicable to these Lie groups opens up the potential to study problems relating to image reconstruction from irregular or random projection directions, information gathering in mobile robotics, satellite attitude control, and bacterial chemotaxis and information processing. Several definitions are extended from the Euclidean case to that of Lie groups including the Fisher information matrix, and inequalities analogous to those in classical information theory are derived and stated in the form of fifteen small theorems. In all such inequalities, addition of random variables is replaced with the group product, and the appropriate generalization of convolution of probability densities is employed.
Semiparametric Estimation of a Noise Model with Quantization Errors
Venue: arXiv cs.DM 2009
Year: 2009

The detectors in mass spectrometers are precise enough to count ion events. In practice, the statistics of chemical noise are affected by large quantization errors and overdispersion because of amplification in the detector. The detector signal is modelled as X =floor(t N) where N represents integer-valued ion counts and t represents the gain parameter. When t <= 1, the gain parameter cannot be recovered without a priori information on N. When t > 1 however, we introduce compatible lattices and derive an estimator for t that is optimal, independent of N and enables subsequent analyses of the ion counts.
A New Upper Bound on 2D Online Bin Packing
Venue: arXiv cs.DS 2009
Year: 2009

The 2D Online Bin Packing is a fundamental problem in Computer Science and the determination of its asymptotic competitive ratio has attracted great research attention. In a long series of papers, the lower bound of this ratio has been improved from 1.808, 1.856 to 1.907 and its upper bound reduced from 3.25, 3.0625, 2.8596, 2.7834 to 2.66013. In this paper, we rewrite the upper bound record to 2.5545. Our idea for the improvement is as follows. In SODA 2002 \cite{SS03}, Seiden and van Stee proposed an elegant algorithm called $H \otimes B$, comprised of the {\em Harmonic algorithm} $H$ and the {\em Improved Harmonic algorithm} $B$, for the two-dimensional online bin packing problem and proved that the algorithm has an asymptotic competitive ratio of at most 2.66013. Since the best known online algorithm for one-dimensional bin packing is the {\em Super Harmonic algorithm} \cite{S02}, a natural question to ask is: could a better upper bound be achieved by using the Super Harmonic algorithm instead of the Improved Harmonic algorithm? However, as mentioned in \cite{SS03}, the previous analysis framework does not work. In this paper, we give a positive answer for the above question. A new upper bound of 2.5545 is obtained for 2-dimensional online bin packing. The main idea is to develop new weighting functions for the Super Harmonic algorithm and propose new techniques to bound the total weight in a rectangular bin.
Methodologies for Analyzing Equilibria in Wireless Games
Venue: arXiv cs.GT 2009
Year: 2009

Under certain assumptions in terms of information and models, equilibria correspond to possible stable outcomes in conflicting or cooperative scenarios where rational entities interact. For wireless engineers, it is of paramount importance to be able to predict and even ensure such states at which the network will effectively operate. In this article, we provide non-exhaustive methodologies for characterizing equilibria in wireless games in terms of existence, uniqueness, selection, and efficiency.
An optimal linear separator for the Sonar Signals Classification task
Venue: arXiv cs.LG 2009
Year: 2009

The problem of classifying sonar signals from rocks and mines first studied by Gorman and Sejnowski has become a benchmark against which many learning algorithms have been tested. We show that both the training set and the test set of this benchmark are linearly separable, although with different hyperplanes. Moreover, the complete set of learning and test patterns together, is also linearly separable. We give the weights that separate these sets, which may be used to compare results found by other algorithms.
On lines and Joints
Venue: arXiv cs.CG 2009
Year: 2009

Let $L$ be a set of $n$ lines in $\reals^d$, for $d\ge 3$. A {\em joint} of $L$ is a point incident to at least $d$ lines of $L$, not all in a common hyperplane. Using a very simple algebraic proof technique, we show that the maximum possible number of joints of $L$ is $Θ(n^{d/(d-1)})$. For $d=3$, this is a considerable simplification of the orignal algebraic proof of Guth and Katz~\cite{GK}, and of the follow-up simpler proof of Elekes et al. \cite{EKS}.
New Instability Results for High Dimensional Nearest Neighbor Search
Venue: arXiv cs.DB 2009
Year: 2009

Consider a dataset of n(d) points generated independently from R^d according to a common p.d.f. f_d with support(f_d) = [0,1]^d and sup{f_d([0,1]^d)} growing sub-exponentially in d. We prove that: (i) if n(d) grows sub-exponentially in d, then, for any query point q^d in [0,1]^d and any epsilon>0, the ratio of the distance between any two dataset points and q^d is less that 1+epsilon with probability -->1 as d-->infinity; (ii) if n(d)>[4(1+epsilon)]^d for large d, then for all q^d in [0,1]^d (except a small subset) and any epsilon>0, the distance ratio is less than 1+epsilon with limiting probability strictly bounded away from one. Moreover, we provide preliminary results along the lines of (i) when f_d=N(mu_d,Sigma_d).
Computational Complexity and Numerical Stability of Linear Problems
Venue: arXiv cs.CC 2009
Year: 2009

We survey classical and recent developments in numerical linear algebra, focusing on two issues: computational complexity, or arithmetic costs, and numerical stability, or performance under roundoff error. We present a brief account of the algebraic complexity theory as well as the general error analysis for matrix multiplication and related problems. We emphasize the central role played by the matrix multiplication problem and discuss historical and modern approaches to its solution.
Single Neuron Memories and the Network's Proximity Matrix
Venue: arXiv cs.NE 2009
Year: 2009

This paper extends the treatment of single-neuron memories obtained by the B-matrix approach. The spreading of the activity within the network is determined by the network's proximity matrix which represents the separations amongst the neurons through the neural pathways.
A Memetic Algorithm for the Multidimensional Assignment Problem
Venue: arXiv cs.DS 2009
Year: 2009

The Multidimensional Assignment Problem (MAP or s-AP in the case of s dimensions) is an extension of the well-known assignment problem. The most studied case of MAP is 3-AP, though the problems with larger values of s have also a number of applications. In this paper we propose a memetic algorithm for MAP that is a combination of a genetic algorithm with a local search procedure. The main contribution of the paper is an idea of dynamically adjusted generation size, that yields an outstanding flexibility of the algorithm to perform well for both small and large fixed running times. The results of computational experiments for several instance families show that the proposed algorithm produces solutions of very high quality in a reasonable time and outperforms the state-of-the art 3-AP memetic algorithm.
Adobe AIR, Bringing Rich Internet Applications to the Desktop
Venue: arXiv cs.OH 2009
Year: 2009

Rich Internet Applications are the new trend in software development today. Adobe AIR offers the possibility to create cross-platform desktop applications using popular Web technologies like HTML, JavaScript, Flash and Flex. This article is focused on presenting the advantages that this new environment has to offer for the web development community and how quickly you can develop a desktop application using Adobe AIR.
Modified Frame Reconstruction Algorithm for Compressive Sensing
Venue: arXiv cs.IT 2009
Year: 2009

Compressive sensing is a technique to sample signals well below the Nyquist rate using linear measurement operators. In this paper we present an algorithm for signal reconstruction given such a set of measurements. This algorithm generalises and extends previous iterative hard thresholding algorithms and we give sufficient conditions for successful reconstruction of the original data signal. In addition we show that by underestimating the sparsity of the data signal we can increase the success rate of the algorithm. We also present a number of modifications to this algorithm: the incorporation of a least squares step, polynomial acceleration and an adaptive method for choosing the step-length. These modified algorithms converge to the correct solution under similar conditions to the original un-modified algorithm. Empirical evidence show that these modifications dramatically increase both the success rate and the rate of convergence, and can outperform other algorithms previously used for signal reconstruction in compressive sensing.
Physical portrayal of computational complexity
Venue: arXiv cs.CC 2009
Year: 2009

Computational complexity is examined using the principle of increasing entropy. To consider computation as a physical process from an initial instance to the final acceptance is motivated because many natural processes have been recognized to complete in non-polynomial time (NP). The irreversible process with three or more degrees of freedom is found intractable because, in terms of physics, flows of energy are inseparable from their driving forces. In computational terms, when solving problems in the class NP, decisions will affect subsequently available sets of decisions. The state space of a non-deterministic finite automaton is evolving due to the computation itself hence it cannot be efficiently contracted using a deterministic finite automaton that will arrive at a solution in super-polynomial time. The solution of the NP problem itself is verifiable in polynomial time (P) because the corresponding state is stationary. Likewise the class P set of states does not depend on computational history hence it can be efficiently contracted to the accepting state by a deterministic sequence of dissipative transformations. Thus it is concluded that the class P set of states is inherently smaller than the set of class NP. Since the computational time to contract a given set is proportional to dissipation, the computational complexity class P is a subset of NP.
Collaborative filtering based on multi-channel diffusion
Venue: arXiv cs.IR 2009
Year: 2009

In this paper, by applying a diffusion process, we propose a new index to quantify the similarity between two users in a user-object bipartite graph. To deal with the discrete ratings on objects, we use a multi-channel representation where each object is mapped to several channels with the number of channels being equal to the number of different ratings. Each channel represents a certain rating and a user having voted an object will be connected to the channel corresponding to the rating. Diffusion process taking place on such a user-channel bipartite graph gives a new similarity measure of user pairs, which is further demonstrated to be more accurate than the classical Pearson correlation coefficient under the standard collaborative filtering framework.
The CIFF Proof Procedure for Abductive Logic Programming with Constraints: Theory, Implementation and Experiments
Venue: arXiv cs.AI 2009
Year: 2009

We present the CIFF proof procedure for abductive logic programming with constraints, and we prove its correctness. CIFF is an extension of the IFF proof procedure for abductive logic programming, relaxing the original restrictions over variable quantification (allowedness conditions) and incorporating a constraint solver to deal with numerical constraints as in constraint logic programming. Finally, we describe the CIFF system, comparing it with state of the art abductive systems and answer set solvers and showing how to use it to program some applications. (To appear in Theory and Practice of Logic Programming - TPLP).
On the Throughput/Bit-Cost Tradeoff in CSMA Based Cooperative Networks
Venue: arXiv cs.IT 2009
Year: 2009

Wireless local area networks (WLAN) still suffer from a severe performance discrepancy between different users in the uplink. This is because of the spatially varying channel conditions provided by the wireless medium. Cooperative medium access control (MAC) protocols as for example CoopMAC were proposed to mitigate this problem. In this work, it is shown that cooperation implies for cooperating nodes a tradeoff between throughput and bit-cost, which is the energy needed to transmit one bit. The tradeoff depends on the degree of cooperation. For carrier sense multiple access (CSMA) based networks, the throughput/bit-cost tradeoff curve is theoretically derived. A new distributed CSMA protocol called fairMAC is proposed and it is theoretically shown that fairMAC can asymptotically achieve any operating point on the tradeoff curve when the packet lengths go to infinity. The theoretical results are validated through Monte Carlo simulations.
Multidimensional Analysis of System Logs in Large-scale Cluster Systems
Venue: arXiv cs.DC 2009
Year: 2009

It is effective to improve the reliability and availability of large-scale cluster systems through the analysis of failures. Existed failure analysis methods understand and analyze failures from one or few dimension. The analysis results are partial and with less precision because of the limitation of data source. This paper presents multidimensional analysis based on graph mining to analyze multi-source system logs, which is a promising failure analysis method to get more complete and precise failure knowledge.
Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs
Venue: arXiv cs.DS 2009
Year: 2009

We consider the problem of extracting a maximum-size reflected network in a linear program. This problem has been studied before and a state-of-the-art SGA heuristic with two variations have been proposed. In this paper we apply a new approach to evaluate the quality of SGA\@. In particular, we solve majority of the instances in the testbed to optimality using a new fixed-parameter algorithm, i.e., an algorithm whose runtime is polynomial in the input size but exponential in terms of an additional parameter associated with the given problem. This analysis allows us to conclude that the the existing SGA heuristic, in fact, produces solutions of a very high quality and often reaches the optimal objective values. However, SGA contain two components which leave some space for improvement: building of a spanning tree and searching for an independent set in a graph. In the hope of obtaining even better heuristic, we tried to replace both of these components with some equivalent algorithms. We tried to use a fixed-parameter algorithm instead of a greedy one for searching of an independent set. But even the exact solution of this subproblem improved the whole heuristic insignificantly. Hence, the crucial part of SGA is building of a spanning tree. We tried three different algorithms, and it appears that the Depth-First search is clearly superior to the other ones in building of the spanning tree for SGA. Thereby, by application of fixed-parameter algorithms, we managed to check that the existing SGA heuristic is of a high quality and selected the component which required an improvement. This allowed us to intensify the research in a proper direction which yielded a superior variation of SGA.
Multiaccess Channels with State Known to One Encoder: Another Case of Degraded Message Sets
Venue: arXiv cs.IT 2009
Year: 2009

We consider a two-user state-dependent multiaccess channel in which only one of the encoders is informed, non-causally, of the channel states. Two independent messages are transmitted: a common message transmitted by both the informed and uninformed encoders, and an individual message transmitted by only the uninformed encoder. We derive inner and outer bounds on the capacity region of this model in the discrete memoryless case as well as the Gaussian case. Further, we show that the bounds for the Gaussian case are tight in some special cases.
The morpho-topographic and cartographic analysis of the archaeological site Cornesti "Iarcuri", Timis County, Romania, using computer sciences methods (GIS and Remote Sensing techniques)
Venue: arXiv cs.OH 2009
Year: 2009

The archaeological site Cornesti "Iarcuri" is the largest earth fortification in Romania, made out of four concentric compounds, spreading over 1780 hectares. It is known since 1700, but it had only a few small attempts of systematic research, the fortress gained interest only after the publishing of some satellite images by Google Earth. It is located in an area of high fields and it occupies three interfluves and contains two streams. Our paper contains a geomorphologic, topographic and cartographic analysis of the site in order to determine the limits, the structure, the morphology, the construction technique and the functionality of such a fortification.Our research is based on satellite image analysis, on archaeological topography, on soil, climate and vegetation analysis as a way to offer a complex image, through this interdisciplinary study of landscape archaeology. Through our work we try not to date the site as this objective will be achieved only after completing the systematic excavations which started in 2007, but only to analyze the co-relationship with the environment.
Secret-Key Generation using Correlated Sources and Channels
Venue: arXiv cs.IT 2009
Year: 2009

We study the problem of generating a shared secret key between two terminals in a joint source-channel setup -- the sender communicates to the receiver over a discrete memoryless wiretap channel and additionally the terminals have access to correlated discrete memoryless source sequences. We establish lower and upper bounds on the secret-key capacity. These bounds coincide, establishing the capacity, when the underlying channel consists of independent, parallel and reversely degraded wiretap channels. In the lower bound, the equivocation terms of the source and channel components are functionally additive. The secret-key rate is maximized by optimally balancing the the source and channel contributions. This tradeoff is illustrated in detail for the Gaussian case where it is also shown that Gaussian codebooks achieve the capacity. When the eavesdropper also observes a source sequence, the secret-key capacity is established when the sources and channels of the eavesdropper are a degraded version of the legitimate receiver. Finally the case when the terminals also have access to a public discussion channel is studied. We propose generating separate keys from the source and channel components and establish the optimality of this approach when the when the channel outputs of the receiver and the eavesdropper are conditionally independent given the input.
On Maximum a Posteriori Estimation of Hidden Markov Processes
Venue: arXiv cs.AI 2009
Year: 2009

We present a theoretical analysis of Maximum a Posteriori (MAP) sequence estimation for binary symmetric hidden Markov processes. We reduce the MAP estimation to the energy minimization of an appropriately defined Ising spin model, and focus on the performance of MAP as characterized by its accuracy and the number of solutions corresponding to a typical observed sequence. It is shown that for a finite range of sufficiently low noise levels, the solution is uniquely related to the observed sequence, while the accuracy degrades linearly with increasing the noise strength. For intermediate noise values, the accuracy is nearly noise-independent, but now there are exponentially many solutions to the estimation problem, which is reflected in non-zero ground-state entropy for the Ising model. Finally, for even larger noise intensities, the number of solutions reduces again, but the accuracy is poor. It is shown that these regimes are different thermodynamic phases of the Ising model that are related to each other via first-order phase transitions.