OpenRaiser/Intern-Atlas huggingface dataset:
CrowdInside: Automatic Construction of Indoor Floorplans
Venue: arXiv cs.OH 2012
Year: 2012

The existence of a worldwide indoor floorplans database can lead to significant growth in location-based applications, especially for indoor environments. In this paper, we present CrowdInside: a crowdsourcing-based system for the automatic construction of buildings floorplans. CrowdInside leverages the smart phones sensors that are ubiquitously available with humans who use a building to automatically and transparently construct accurate motion traces. These accurate traces are generated based on a novel technique for reducing the errors in the inertial motion traces by using the points of interest in the indoor environment, such as elevators and stairs, for error resetting. The collected traces are then processed to detect the overall floorplan shape as well as higher level semantics such as detecting rooms and corridors shapes along with a variety of points of interest in the environment. Implementation of the system in two testbeds, using different Android phones, shows that CrowdInside can detect the points of interest accurately with 0.2% false positive rate and 1.3% false negative rate. In addition, the proposed error resetting technique leads to more than 12 times enhancement in the median distance error compared to the state-of-the-art. Moreover, the detailed floorplan can be accurately estimated with a a relatively small number of traces. This number is amortized over the number of users of the building. We also discuss possible extensions to CrowdInside for inferring even higher level semantics about the discovered floorplans.
A Distributed Algorithm for Gathering Many Fat Mobile Robots in the Plane
Venue: arXiv cs.DC 2012
Year: 2012

In this work we consider the problem of gathering autonomous robots in the plane. In particular, we consider non-transparent unit-disc robots (i.e., fat) in an asynchronous setting. Vision is the only mean of coordination. Using a state-machine representation we formulate the gathering problem and develop a distributed algorithm that solves the problem for any number of robots. The main idea behind our algorithm is for the robots to reach a configuration in which all the following hold: (a) The robots' centers form a convex hull in which all robots are on the convex, (b) Each robot can see all other robots, and (c) The configuration is connected, that is, every robot touches another robot and all robots together form a connected formation. We show that starting from any initial configuration, the robots, making only local decisions and coordinate by vision, eventually reach such a configuration and terminate, yielding a solution to the gathering problem.
Keyspace: A Consistently Replicated, Highly-Available Key-Value Store
Venue: arXiv cs.DB 2012
Year: 2012

This paper describes the design and architecture of Keyspace, a distributed key-value store offering strong consistency, fault-tolerance and high availability. The source code is available under the open-source AGPL license for Linux, Windows and BSD-like platforms. As of 2012, Keyspace is no longer undergoing active development.
Some extremal properties of the Fibonacci word
Venue: arXiv cs.DM 2012
Year: 2012

We prove that the Fibonacci word $f$ satisfies among all characteristic Sturmian words, three interesting extremal properties. The first concerns the length and the second the minimal period of its palindromic prefixes. Each of these two properties characterizes $f$ up to a renaming of its letters. A third property concerns the number of occurrences of the letter $b$ in its palindromic prefixes. It characterizes uniquely $f$ among all characteristic Sturmian words having the prefix $abaa$.
Binary equality sets are generated by two words
Venue: arXiv cs.FL 2012
Year: 2012

We show that the equality language of two non-periodic binary morphisms is generated by at most two words. If its rank is two, then the generators start (and end) with different letters. This in particular implies that any binary language has a test set of cardinality at most two.
AutoAmp : An Open-Source Analog Amplifier Design Tool - For Classroom and Lab Purposes
Venue: arXiv cs.OH 2012
Year: 2012

This correspondence presents an open-source tool AutoAmp developed at the Indian Institute of Technology, Guwahati. It is available at http://sourceforge.net/projects/autoamp-iitg/ This tool helps the user to design different types of electronic amplifiers, using solid state devices, for a given specification. It can handle several types of designs namely common-emitter BJT amplifier (single and two-stage), operational amplifiers (inverting and non-inverting) and power amplifier. Not only does it design the amplifier, it also simulates the designed amplifier using SPICE simulator and displays the performance curves. This tool is deemed to prove invaluable in undergraduate teaching and labs. Especially in electronics-design related laboratories, the student need not design the amplifiers which are mostly the heart of many electronic designs.
A combinatorial algorithm to generate all spanning trees of a weighted graph in order of increasing cost
Venue: arXiv cs.DS 2012
Year: 2012

The most popular algorithms for generation of minimal spanning tree are Kruskal and Prim algorithm. Many algorithms have been proposed for generation of all spanning tree. This paper deals with generation of all possible spanning trees in increasing cost of a weighted graph. This approach uses one matrix called Difference Weighted Circuit Matrix; it is little bit modification of FCM.
Image Super-Resolution via Sparse Bayesian Modeling of Natural Images
Venue: arXiv cs.CV 2012
Year: 2012

Image super-resolution (SR) is one of the long-standing and active topics in image processing community. A large body of works for image super resolution formulate the problem with Bayesian modeling techniques and then obtain its Maximum-A-Posteriori (MAP) solution, which actually boils down to a regularized regression task over separable regularization term. Although straightforward, this approach cannot exploit the full potential offered by the probabilistic modeling, as only the posterior mode is sought. Also, the separable property of the regularization term can not capture any correlations between the sparse coefficients, which sacrifices much on its modeling accuracy. We propose a Bayesian image SR algorithm via sparse modeling of natural images. The sparsity property of the latent high resolution image is exploited by introducing latent variables into the high-order Markov Random Field (MRF) which capture the content adaptive variance by pixel-wise adaptation. The high-resolution image is estimated via Empirical Bayesian estimation scheme, which is substantially faster than our previous approach based on Markov Chain Monte Carlo sampling [1]. It is shown that the actual cost function for the proposed approach actually incorporates a non-factorial regularization term over the sparse coefficients. Experimental results indicate that the proposed method can generate competitive or better results than \emph{state-of-the-art} SR algorithms.
Distributed Estimation of a Parametric Field Using Sparse Noisy Data
Venue: arXiv cs.IT 2012
Year: 2012

The problem of distributed estimation of a parametric physical field is stated as a maximum likelihood estimation problem. Sensor observations are distorted by additive white Gaussian noise. Prior to data transmission, each sensor quantizes its observation to $M$ levels. The quantized data are then communicated over parallel additive white Gaussian channels to a fusion center for a joint estimation. An iterative expectation-maximization (EM) algorithm to estimate the unknown parameter is formulated, and its linearized version is adopted for numerical analysis. The numerical examples are provided for the case of the field modeled as a Gaussian bell. The dependence of the integrated mean-square error on the number of quantization levels, the number of sensors in the network and the SNR in observation and transmission channels is analyzed.
Speech Signal Filters based on Soft Computing Techniques: A Comparison
Venue: arXiv cs.AI 2012
Year: 2012

The paper presents a comparison of various soft computing techniques used for filtering and enhancing speech signals. The three major techniques that fall under soft computing are neural networks, fuzzy systems and genetic algorithms. Other hybrid techniques such as neuro-fuzzy systems are also available. In general, soft computing techniques have been experimentally observed to give far superior performance as compared to non-soft computing techniques in terms of robustness and accuracy.
Beyond Cumulated Gain and Average Precision: Including Willingness and Expectation in the User Model
Venue: arXiv cs.IR 2012
Year: 2012

In this paper, we define a new metric family based on two concepts: The definition of the stopping criterion and the notion of satisfaction, where the former depends on the willingness and expectation of a user exploring search results. Both concepts have been discussed so far in the IR literature, but we argue in this paper that defining a proper single valued metric depends on merging them into a single conceptual framework.
Bouma2 - A Quasi-Stateless, Tunable Multiple String-Match Algorithm
Venue: arXiv cs.DS 2012
Year: 2012

The Bouma2 algorithm attempts to challenge the prevalent "stateful" exact string-match paradigms by suggesting a "quasi-stateless" approach. We claim that using state-machines to solve the multiple exact string-match problem introduces a hidden artificial constraint, namely the Consume-Order Dependency, which results in unnecessary overhead. Bouma2 is not restricted in this sense; we postulate that this allows memory-efficiency and improved performance versus its state-machine equivalents. The heart of the Bouma2 preprocessing problem is formulated as a weighted Integer Linear Programming problem, that can be tuned for memory footprint and performance optimization. Specifically, this allows Bouma2 to be input-sensitive, as tuning can be based on input characteristics. Evaluating Bouma2 against the Aho-Corasick variant of the popular Snort Intrusion Prevention System, we demonstrate double the throughput while using about 10% of the memory.
A Metric For The Activeness Of An Object-Oriented Component Library
Venue: arXiv cs.SE 2012
Year: 2012

In this paper, an attempt has been made to analyze the Activeness of an Object Oriented Component Library and develop a special type of software metric called Component Activeness Quotient which is defined as the degree of readiness of an OOCL. The advantages of the CAQ include a possible comparison between various OOCLs leading to selection of the best OOCL for use during the development task, and Stability of the software can be gauged as indicated by the value of the CAQ. The disadvantage of the CAQ is that it may have some error because of its subjective and random nature. The paper also tries to improvise the calculation of the Activeness Quotient. The extreme case of a software organization having an RQ greater than 1 and MQ equal to 0 was not handled by the method of taking an average of RQ and MQ to calculate the AQ. The improvisation is that the AQ must be equal to a product of MQ and RQ and this is mentioned in the Appendix.
Discontinuous Galerkin method for Navier-Stokes equations using kinetic flux vector splitting
Venue: arXiv cs.NA 2012
Year: 2012

Kinetic schemes for compressible flow of gases are constructed by exploiting the connection between Boltzmann equation and the Navier-Stokes equations. This connection allows us to construct a flux splitting for the Navier-Stokes equations based on the direction of molecular motion from which a numerical flux can be obtained. The naive use of such a numerical flux function in a discontinuous Galerkin (DG) discretization leads to an unstable scheme in the viscous dominated case. Stable schemes are constructed by adding additional terms either in a symmetric or non-symmetric manner which are motivated by the DG schemes for elliptic equations. The novelty of the present scheme is the use of kinetic fluxes to construct the stabilization terms. In the symmetric case, interior penalty terms have to be added for stability and the resulting schemes give optimal convergence rates in numerical experiments. The non-symmetric schemes lead to a cell energy/entropy inequality but exhibit sub-optimal convergence rates. These properties are studied by applying the schemes to a scalar convection-diffusion equation and the 1-D compressible Navier-Stokes equations. In the case of Navier-Stokes equations, entropy variables are used to construct stable schemes.
Delay Analysis of Max-Weight Queue Algorithm for Time-varying Wireless Adhoc Networks - Control Theoretical Approach
Venue: arXiv cs.SY 2012
Year: 2012

Max weighted queue (MWQ) control policy is a widely used cross-layer control policy that achieves queue stability and a reasonable delay performance. In most of the existing literature, it is assumed that optimal MWQ policy can be obtained instantaneously at every time slot. However, this assumption may be unrealistic in time varying wireless systems, especially when there is no closed-form MWQ solution and iterative algorithms have to be applied to obtain the optimal solution. This paper investigates the convergence behavior and the queue delay performance of the conventional MWQ iterations in which the channel state information (CSI) and queue state information (QSI) are changing in a similar timescale as the algorithm iterations. Our results are established by studying the stochastic stability of an equivalent virtual stochastic dynamic system (VSDS), and an extended Foster-Lyapunov criteria is applied for the stability analysis. We derive a closed form delay bound of the wireless network in terms of the CSI fading rate and the sensitivity of MWQ policy over CSI and QSI. Based on the equivalent VSDS, we propose a novel MWQ iterative algorithm with compensation to improve the tracking performance. We demonstrate that under some mild conditions, the proposed modified MWQ algorithm converges to the optimal MWQ control despite the time-varying CSI and QSI.
APRAP: Another Privacy Preserving RFID Authentication Protocol
Venue: arXiv cs.CR 2012
Year: 2012

Privacy preserving RFID (Radio Frequency Identification) authentication has been an active research area in recent years. Both forward security and backward security are required to maintain the privacy of a tag, i.e., exposure of a tag's secret key should not reveal the past or future secret keys of the tag. We envisage the need for a formal model for backward security for RFID protocol designs in shared key settings, since the RFID tags are too resource-constrained to support public key settings. However, there has not been much research on backward security for shared key environment since Serge Vaudenay in his Asiacrypt 2007 paper showed that perfect backward security is impossible to achieve without public key settings. We propose a Privacy Preserving RFID Authentication Protocol for shared key environment, APRAP, which minimizes the damage caused by secret key exposure using insulated keys. Even if a tag's secret key is exposed during an authentication session, forward security and 'restricted' backward security of the tag are preserved under our assumptions. The notion of 'restricted' backward security is that the adversary misses the protocol transcripts which are needed to update the compromised secret key. Although our definition does not capture perfect backward security, it is still suitable for effective implementation as the tags are highly mobile in practice. We also provide a formal security model of APRAP. Our scheme is more efficient than previous proposals from the viewpoint of computational requirements.
Global passive system approximation
Venue: arXiv cs.SY 2012
Year: 2012

In this paper we present a new approach towards global passive approximation in order to find a passive transfer function G(s) that is nearest in some well-defined matrix norm sense to a non-passive transfer function H(s). It is based on existing solutions to pertinent matrix nearness problems. It is shown that the key point in constructing the nearest passive transfer function, is to find a good rational approximation of the well-known ramp function over an interval defined by the minimum and maximum dissipation of H(s). The proposed algorithms rely on the stable anti-stable projection of a given transfer function. Pertinent examples are given to show the scope and accuracy of the proposed algorithms.
Distributed Spectrum Access with Spatial Reuse
Venue: arXiv cs.NI 2012
Year: 2012

Efficient distributed spectrum sharing mechanism is crucial for improving the spectrum utilization. The spatial aspect of spectrum sharing, however, is less understood than many other aspects. In this paper, we generalize a recently proposed spatial congestion game framework to design efficient distributed spectrum access mechanisms with spatial reuse. We first propose a spatial channel selection game to model the distributed channel selection problem with fixed user locations. We show that the game is a potential game, and develop a distributed learning mechanism that converges to a Nash equilibrium only based on users' local observations. We then formulate the joint channel and location selection problem as a spatial channel selection and mobility game, and show that it is also a potential game. We next propose a distributed strategic mobility algorithm, jointly with the distributed learning mechanism, that can converge to a Nash equilibrium.
Error Correction for Cooperative Data Exchange
Venue: arXiv cs.IT 2012
Year: 2012

This paper considers the problem of error correction for a cooperative data exchange (CDE) system, where some clients are compromised or failed and send false messages. Assuming each client possesses a subset of the total messages, we analyze the error correction capability when every client is allowed to broadcast only one linearly-coded message. Our error correction capability bound determines the maximum number of clients that can be compromised or failed without jeopardizing the final decoding solution at each client. We show that deterministic, feasible linear codes exist that can achieve the derived bound. We also evaluate random linear codes, where the coding coefficients are drawn randomly, and then develop the probability for a client to withstand a certain number of compromised or failed peers and successfully deduce the complete message for any network size and any initial message distributions.
Capacity Results for Arbitrarily Varying Wiretap Channels
Venue: arXiv cs.IT 2012
Year: 2012

In this work the arbitrarily varying wiretap channel AVWC is studied. We derive a lower bound on the random code secrecy capacity for the average error criterion and the strong secrecy criterion in the case of a best channel to the eavesdropper by using Ahlswede's robustification technique for ordinary AVCs. We show that in the case of a non-symmetrisable channel to the legitimate receiver the deterministic code secrecy capacity equals the random code secrecy capacity, a result similar to Ahlswede's dichotomy result for ordinary AVCs. Using this we can derive that the lower bound is also valid for the deterministic code capacity of the AVWC. The proof of the dichotomy result is based on the elimination technique introduced by Ahlswede for ordinary AVCs. We further prove upper bounds on the deterministic code secrecy capacity in the general case, which results in a multi-letter expression for the secrecy capacity in the case of a best channel to the eavesdropper. Using techniques of Ahlswede, developed to guarantee the validity of a reliability criterion, the main contribution of this work is to integrate the strong secrecy criterion into these techniques.
Walking with the Oracle: Efficient Use of Mobile Networks through Location-Awareness
Venue: arXiv cs.NI 2012
Year: 2012

Always Best Packet Switching (ABPS) is a novel approach for wireless communications that enables mobile nodes, equipped with multiple network interface cards (NICs), to dynamically determine the most appropriate NIC to use. Using ABPS, a mobile node can seamlessly switch to a different NIC in order to get better performance, without causing communication interruptions at the application level. To make this possible, NICs are kept always active and a software monitor constantly probes the channels for available access points. While this ensures maximum connection availability, considerable energy may be wasted when no access points are available for a given NIC. In this paper we address this issue by investigating the use of an "oracle" able to provide information on network availability. This allows to dynamically switch on/off NICs based on reported availability, thus reducing the power consumption. We present a Markov model which allows us to estimate the impact of the oracle on the ABPS mechanism: results show that significant reduction in energy consumption can be achieved with minimal impact on connection availability. We conclude by describing a prototype implementation of the oracle based on Web services and geolocalization.
Multiprocessor Scheduling Using Parallel Genetic Algorithm
Venue: arXiv cs.DC 2012
Year: 2012

Tasks scheduling is the most challenging problem in the parallel computing. Hence, the inappropriate scheduling will reduce or even abort the utilization of the true potential of the parallelization. Genetic algorithm (GA) has been successfully applied to solve the scheduling problem. The fitness evaluation is the most time consuming GA operation for the CPU time, which affect the GA performance. The proposed synchronous master-slave algorithm outperforms the sequential algorithm in case of complex and high number of generations problem.
eBay's Market Intermediation Problem
Venue: arXiv cs.GT 2012
Year: 2012

We study the optimal mechanism design problem faced by a market intermediary who makes revenue by connecting buyers and sellers. We first show that the optimal intermediation protocol has substantial structure: it is the solution to an algorithmic pricing problem in which seller's costs are replaced with virtual costs, and the sellers' payments need only depend on the buyer's behavior and not the buyer's actual valuation function. Since the underlying algorithmic pricing problem may be difficult to solve optimally, we study specific models of buyer behavior and give mechanisms with provable approximation guarantees. We show that offering only the single most profitable item for sale guarantees an $Ω(\frac1{\log n})$ fraction of the optimal revenue when item value distributions are independent and have monotone hazard rates. We also give constant factor approximations when the buyer considers all items at once, $k$ items at once, or items in sequence.