OpenRaiser/Intern-Atlas huggingface dataset:
On Parsimonious Explanations for 2-D Tree- and Linearly-Ordered Data
Venue: arXiv cs.DS 2011
Year: 2011

This paper studies the "explanation problem" for tree- and linearly-ordered array data, a problem motivated by database applications and recently solved for the one-dimensional tree-ordered case. In this paper, one is given a matrix A whose rows and columns have semantics: special subsets of the rows and special subsets of the columns are meaningful, others are not. A submatrix in A is said to be meaningful if and only if it is the cross product of a meaningful row subset and a meaningful column subset, in which case we call it an "allowed rectangle." The goal is to "explain" A as a sparse sum of weighted allowed rectangles. Specifically, we wish to find as few weighted allowed rectangles as possible such that, for all i,j, a_{ij} equals the sum of the weights of all rectangles which include cell (i,j). In this paper we consider the natural cases in which the matrix dimensions are tree-ordered or linearly-ordered. In the tree-ordered case, we are given a rooted tree T1 whose leaves are the rows of A and another, T2, whose leaves are the columns. Nodes of the trees correspond in an obvious way to the sets of their leaf descendants. In the linearly-ordered case, a set of rows or columns is meaningful if and only if it is contiguous. For tree-ordered data, we prove the explanation problem NP-Hard and give a randomized 2-approximation algorithm for it. For linearly-ordered data, we prove the explanation problem NP-Hard and give a 2.56-approximation algorithm. To our knowledge, these are the first results for the problem of sparsely and exactly representing matrices by weighted rectangles.
Data Accuracy Estimation for Cluster with Spatially Correlated Data in Wireless Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

Objective-The main purpose of this paper is to construct a data accuracy model for the maximal set of sensor nodes that sense a point event and forms a cluster with fully connected network between them. We determine the minimal set of sensor nodes that are sufficient to give approximately the same data accuracy achieve by the maximal set of sensor nodes. Design approach/Procedure-L set of sensor nodes are randomly deployed over a region Z. Since a point event S has occurred in the region Z, M maximal set of sensor nodes wake up and start sensing the point event. The set of M sensor nodes forms a cluster with fully connected network and remaining set of sensor nodes continue to be in sleep mode. One sensor node is elected randomly as a cluster head (CH) node which can estimate the data accuracy for the cluster before data aggregation and finally send the data to the sink node. Findings - Since we simulate the data accuracy for the cluster (M set of sensor nodes) at CH node, there exist P minimal set of sensor nodes which give approximately the same data accuracy level achieve by M set of sensor nodes .Moreover we find that as the distance from the point event to the number of sensor nodes increases, the data accuracy also get decreases. Design Limitation -This model is only applicable to estimate data accuracy for the point event where the sensed data are assumed to be spatially correlated with approximately same variations. Practical implementation-Detect point event e.g. fire in forest. Inventive/Novel idea - This is the first time that a data accuracy model is performed for the cluster before data aggregation at the CH node which can reduce data redundancy and communication overhead.
Data Accuracy Estimation for Spatially Correlated Data in Wireless Sensor Networks under Distributed Clustering
Venue: arXiv cs.NI 2011
Year: 2011

Objective-The main purpose of this paper is to construct a distributed clustering algorithm such that each distributed cluster can perform the data accuracy at their respective cluster head node before data aggregation and transmit the data to the sink node. Design approach/Procedure - We investigate that the data are spatially correlated among the sensor nodes which form the clusters in the spatial domain. Due to high correlation of data, these clusters of sensor nodes are overlapped in the spatial domain. To overcome this problem, we construct a distributed clustering algorithm with non-overlapping irregular clusters in the spatial domain. Then each distributed cluster can perform data accuracy at the cluster head node and finally send the data to the sink node. Findings- Simulation result shows the associate sensor nodes of each distributed cluster and clarifies their data accuracy profile in the spatial domain. We demonstrate the simulation results for a single cluster to verify that their exist an optimal cluster which give approximately the same data accuracy level achieve by the single cluster. Moreover we find that as the distance from the tracing point to the number of sensor node increases the data accuracy decreases. Design Limitations - This model is only applicable to estimate data accuracy for distributed clusters where the sensed data are assumed to be spatially correlated with approximately same variations. Practical implementation - Measure the moisture content in the distributed agricultural field. Inventive/Novel idea- This is the first time that a data accuracy model is performed for the distributed clusters before data aggregation at the cluster head node which can reduce data redundancy and communication overhead.
Power Allocation Games in Interference Relay Channels: Existence Analysis of Nash Equilibria
Venue: arXiv cs.IT 2011
Year: 2011

We consider a network composed of two interfering point-to-point links where the two transmitters can exploit one common relay node to improve their individual transmission rate. Communications are assumed to be multi-band and transmitters are assumed to selfishly allocate their resources to optimize their individual transmission rate. The main objective of this paper is to show that this conflicting situation (modeled by a non-cooperative game) has some stable outcomes, namely Nash equilibria. This result is proved for three different types of relaying protocols: decode-and-forward, estimate-and-forward, and amplify-and-forward. We provide additional results on the problems of uniqueness, efficiency of the equilibrium, and convergence of a best-response based dynamics to the equilibrium. These issues are analyzed in a special case of the amplify-and-forward protocol and illustrated by simulations in general.
Casting Robotic End-effectors To Reach Faraway Moving Objects
Venue: arXiv cs.RO 2011
Year: 2011

In this article we address the problem of catching objects that move at a relatively large distance from the robot, of the order of tens of times the size of the robot itself. To this purpose, we adopt casting manipulation and visual-based feedback control. Casting manipulation is a technique to deploy a robotic end-effector far from the robot's base, by throwing the end-effector and controlling its ballistic flight using forces transmitted through a light tether connected to the end-effector itself. The tether cable can then be used to retrieve the end- effector to exert forces on the robot's environment. In previous work, planar casting manipulation was demon- strated to aptly catch static objects placed at a distant, known position, thus proving it suitable for applications such as sample acquisition and return, rescue, etc. In this paper we propose an extension of the idea to controlling the position of the end- effector to reach moving targets in 3D. The goal is achieved by an innovative design of the casting mechanism, and by closing a real-time control loop on casting manipulation using visual feedback of moving targets. To achieve this result, simplified yet accurate models of the system suitable for real-time computation are developed, along with a suitable visual feedback scheme for the flight phase. Effectiveness of the visual feedback controller is demonstrated through experiments with a 2D casting robot.
On the Degree of Freedom for Multi-Source Multi-Destination Wireless Network with Multi-layer Relays
Venue: arXiv cs.IT 2011
Year: 2011

Degree of freedom (DoF) region provides an approximation of capacity region in high signal-to-noise ratio (SNR) regime, while sum DoF gives the scaling factor. In this correspondence, we analyse the DoF region and sum DoF for unicast layered multi-hop relay wireless networks with arbitrary number of source/destination/relay nodes, arbitrary number of hops and arbitrary number of antennas at each node. The result is valid for quite a few message topologies. We reveal the limitation on capacity of multi-hop network due to the concatenation structure and show the similarity with capacitor network. From the analysis on bound gap and optimality condition, the ultimate capacity of multi-hop network is shown to be strictly inferior to that of single-hop network. Linear scaling law can be established when the number of hops is fixed. At cost of channel state information at transmitters (CSIT) for each component single-hop network, our achievable scheme avoids routing and simplifies scheduling.
A Factorial Experiment on Scalability of Search Based Software Testing
Venue: arXiv cs.SE 2011
Year: 2011

Software testing is an expensive process, which is vital in the industry. Construction of the test-data in software testing requires the major cost and to decide which method to use in order to generate the test data is important. This paper discusses the efficiency of search-based algorithms (preferably genetic algorithm) versus random testing, in soft- ware test-data generation. This study differs from all previous studies due to sample programs (SUTs) which are used. Since we want to in- crease the complexity of SUTs gradually, and the program generation is automatic as well, Grammatical Evolution is used to guide the program generation. SUTs are generated according to the grammar we provide, with different levels of complexity. SUTs will first undergo genetic al- gorithm and then random testing. Based on the test results, this paper recommends one method to use for automation of software testing.
A Generalized MMSE Detection with Reduced Complexity for Spatially Multiplexed MIMO Signals
Venue: arXiv cs.IT 2011
Year: 2011

In multiple-input multiple-output (MIMO) spatially multiplexing (SM) systems, achievable error rate performance is determined by signal detection strategy. The optimal maximum-likelihood detection (MLD) that exhaustively examines all symbol candidates has exponential complexity and may not be applicable in many practical systems. In this paper, we consider a generalized minimum mean square error (MMSE) detection derived from conditional mean estimation, which in principle behaves equivalently to MLD but also includes a linear MMSE detection as a special case. Motivated by this fact, we propose a low-complexity detection which significantly reduces the number of examined symbol candidates without significant error rate performance degradation from MLD. Our approach is to approximate the probability density function (pdf) of modulated symbols that appears in the exact conditional mean expression such that the decision metric can be cast into a partially closed form. It is found that uniform ring approximation in combination with phase shift keying (PSK) and amplitude phase shift keying (APSK) is promising, as it can achieve a performance even comparable to MLD, while its complexity is linear when the number of transmit antennas is two.
Review and Evaluation of Feature Selection Algorithms in Synthetic Problems
Venue: arXiv cs.AI 2011
Year: 2011

The main purpose of Feature Subset Selection is to find a reduced subset of attributes from a data set described by a feature set. The task of a feature selection algorithm (FSA) is to provide with a computational solution motivated by a certain definition of relevance or by a reliable evaluation measure. In this paper several fundamental algorithms are studied to assess their performance in a controlled experimental scenario. A measure to evaluate FSAs is devised that computes the degree of matching between the output given by a FSA and the known optimal solutions. An extensive experimental study on synthetic problems is carried out to assess the behaviour of the algorithms in terms of solution accuracy and size as a function of the relevance, irrelevance, redundancy and size of the data samples. The controlled experimental conditions facilitate the derivation of better-supported and meaningful conclusions.
Minimum Covering with Travel Cost
Venue: arXiv cs.DS 2011
Year: 2011

Given a polygon and a visibility range, the Myopic Watchman Problem with Discrete Vision (MWPDV) asks for a closed path P and a set of scan points S, such that (i) every point of the polygon is within visibility range of a scan point; and (ii) path length plus weighted sum of scan number along the tour is minimized. Alternatively, the bicriteria problem (ii') aims at minimizing both scan number and tour length. We consider both lawn mowing (in which tour and scan points may leave P) and milling (in which tour, scan points and visibility must stay within P) variants for the MWPDV; even for simple special cases, these problems are NP-hard. We show that this problem is NP-hard, even for the special cases of rectilinear polygons and L_\infty scan range 1, and negligible small travel cost or negligible travel cost. For rectilinear MWPDV milling in grid polygons we present a 2.5-approximation with unit scan range; this holds for the bicriteria version, thus for any linear combination of travel cost and scan cost. For grid polygons and circular unit scan range, we describe a bicriteria 4-approximation. These results serve as stepping stones for the general case of circular scans with scan radius r and arbitrary polygons of feature size a, for which we extend the underlying ideas to a pi(r/a}+(r+1)/2) bicriteria approximation algorithm. Finally, we describe approximation schemes for MWPDV lawn mowing and milling of grid polygons, for fixed ratio between scan cost and travel cost.
Planarity Testing Revisited
Venue: arXiv cs.CC 2011
Year: 2011

Planarity Testing is the problem of determining whether a given graph is planar while planar embedding is the corresponding construction problem. The bounded space complexity of these problems has been determined to be exactly Logspace by Allender and Mahajan with the aid of Reingold's result. Unfortunately, the algorithm is quite daunting and generalizing it to say, the bounded genus case seems a tall order. In this work, we present a simple planar embedding algorithm running in logspace. We hope this algorithm will be more amenable to generalization. The algorithm is based on the fact that 3-connected planar graphs have a unique embedding, a variant of Tutte's criterion on conflict graphs of cycles and an explicit change of cycle basis.% for planar graphs. We also present a logspace algorithm to find obstacles to planarity, viz. a Kuratowski minor, if the graph is non-planar. To the best of our knowledge this is the first logspace algorithm for this problem.
Routing Security Issues in Wireless Sensor Networks: Attacks and Defenses
Venue: arXiv cs.NI 2011
Year: 2011

Wireless Sensor Networks (WSNs) are rapidly emerging as an important new area in wireless and mobile computing research. Applications of WSNs are numerous and growing, and range from indoor deployment scenarios in the home and office to outdoor deployment scenarios in adversary's territory in a tactical battleground (Akyildiz et al., 2002). For military environment, dispersal of WSNs into an adversary's territory enables the detection and tracking of enemy soldiers and vehicles. For home/office environments, indoor sensor networks offer the ability to monitor the health of the elderly and to detect intruders via a wireless home security system. In each of these scenarios, lives and livelihoods may depend on the timeliness and correctness of the sensor data obtained from dispersed sensor nodes. As a result, such WSNs must be secured to prevent an intruder from obstructing the delivery of correct sensor data and from forging sensor data. To address the latter problem, end-to-end data integrity checksums and post-processing of senor data can be used to identify forged sensor data (Estrin et al., 1999; Hu et al., 2003a; Ye et al., 2004). The focus of this chapter is on routing security in WSNs. Most of the currently existing routing protocols for WSNs make an optimization on the limited capabilities of the nodes and the application-specific nature of the network, but do not any the security aspects of the protocols. Although these protocols have not been designed with security as a goal, it is extremely important to analyze their security properties. When the defender has the liabilities of insecure wireless communication, limited node capabilities, and possible insider threats, and the adversaries can use powerful laptops with high energy and long range communication to attack the network, designing a secure routing protocol for WSNs is obviously a non-trivial task.
Robust Line Planning in case of Multiple Pools and Disruptions
Venue: arXiv cs.GT 2011
Year: 2011

We consider the line planning problem in public transportation, under a robustness perspective. We present a mechanism for robust line planning in the case of multiple line pools, when the line operators have a different utility function per pool. We conduct an experimental study of our mechanism on both synthetic and real-world data that shows fast convergence to the optimum. We also explore a wide range of scenarios, varying from an arbitrary initial state (to be solved) to small disruptions in a previously optimal solution (to be recovered). Our experiments with the latter scenario show that our mechanism can be used as an online recovery scheme causing the system to re-converge to its optimum extremely fast.
Subjective Collaborative Filtering
Venue: arXiv cs.IR 2011
Year: 2011

We present an item-based approach for collaborative filtering. We determine a list of recommended items for a user by considering their previous purchases. Additionally other features of the users could be considered such as page views, search queries, etc... In particular we address the problem of efficiently comparing items. Our algorithm can efficiently approximate an estimate of the similarity between two items. As measure of similarity we use an approximation of the Jaccard similarity that can be computed by constant time operations and one bitwise OR. Moreover we improve the accuracy of the similarity by introducing the concept of user preference for a given product, which both takes into account multiple purchases and purchases of related items. The product of the user preference and the Jaccard measure (or its approximation) is used as a score for deciding whether a given product has to be recommended.
Support vector machines/relevance vector machine for remote sensing classification: A review
Venue: arXiv cs.CV 2011
Year: 2011

Kernel-based machine learning algorithms are based on mapping data from the original input feature space to a kernel feature space of higher dimensionality to solve a linear problem in that space. Over the last decade, kernel based classification and regression approaches such as support vector machines have widely been used in remote sensing as well as in various civil engineering applications. In spite of their better performance with different datasets, support vector machines still suffer from shortcomings such as visualization/interpretation of model, choice of kernel and kernel specific parameter as well as the regularization parameter. Relevance vector machines are another kernel based approach being explored for classification and regression with in last few years. The advantages of the relevance vector machines over the support vector machines is the availability of probabilistic predictions, using arbitrary kernel functions and not requiring setting of the regularization parameter. This paper presents a state-of-the-art review of SVM and RVM in remote sensing and provides some details of their use in other civil engineering application also.
Generalizing Topology via Chu Spaces
Venue: arXiv cs.LO 2011
Year: 2011

By using the representational power of Chu spaces we define the notion of a generalized topological space (or GTS, for short), i.e., a mathematical structure that generalizes the notion of a topological space. We demonstrate that these topological spaces have as special cases known topological spaces. Furthermore, we develop the various topological notions and concepts for GTS. Moreover, since the logic of Chu spaces is linear logic, we give an interpretation of most linear logic connectives as operators that yield topological spaces.
Psi-calculi: a framework for mobile processes with nominal data and logic
Venue: arXiv cs.LO 2011
Year: 2011

The framework of psi-calculi extends the pi-calculus with nominal datatypes for data structures and for logical assertions and conditions. These can be transmitted between processes and their names can be statically scoped as in the standard pi-calculus. Psi-calculi can capture the same phenomena as other proposed extensions of the pi-calculus such as the applied pi-calculus, the spi-calculus, the fusion calculus, the concurrent constraint pi-calculus, and calculi with polyadic communication channels or pattern matching. Psi-calculi can be even more general, for example by allowing structured channels, higher-order formalisms such as the lambda calculus for data structures, and predicate logic for assertions. We provide ample comparisons to related calculi and discuss a few significant applications. Our labelled operational semantics and definition of bisimulation is straightforward, without a structural congruence. We establish minimal requirements on the nominal data and logic in order to prove general algebraic properties of psi-calculi, all of which have been checked in the interactive theorem prover Isabelle. Expressiveness of psi-calculi significantly exceeds that of other formalisms, while the purity of the semantics is on par with the original pi-calculus.
Fast Vertex Guarding for Polygons
Venue: arXiv cs.CG 2011
Year: 2011

For a polygon P with n vertices, the vertex guarding problem asks for the minimum subset G of P's vertices such that every point in P is seen by at least one point in G. This problem is NP-complete and APX-hard. The first approximation algorithm (Ghosh, 1987) involves decomposing P into O(n^4) cells that are equivalence classes for visibility from the vertices of P. This discretized problem can then be treated as an instance of set cover and solved in O(n^5) time with a greedy O(log n)-approximation algorithm. Ghosh (2010) recently revisited the algorithm, noting that minimum visibility decompositions for simple polygons (Bose et al., 2000) have only O(n^3) cells, improving the running time of the algorithm to O(n^4) for simple polygons. In this paper we show that, since minimum visibility decompositions for simple polygons have only O(n^2) cells of minimal visibility (Bose et al., 2000), the running time of the algorithm can be further improved to O(n^3). This result was obtained independently by Jang and Kwon (2011). We extend the result of Bose et al. to polygons with holes, showing that a minimum visibility decomposition of a polygon with h holes has only O((h+1)n^3) cells and only O((h+1)^2 n^2) cells of minimal visibility. We exploit this result to obtain a faster algorithm for vertex guarding polygons with holes. We then show that, in the same time complexity, we can attain approximation factors of O(log log(opt)) for simple polygons and O((1+\log((h+1))) log(opt)) for polygons with holes.