OpenRaiser/Intern-Atlas huggingface dataset:
Reasoning About LLVM Code Using Codewalker
Venue: arXiv cs.LO 2015
Year: 2015

This paper reports on initial experiments using J Moore's Codewalker to reason about programs compiled to the Low-Level Virtual Machine (LLVM) intermediate form. Previously, we reported on a translator from LLVM to the applicative subset of Common Lisp accepted by the ACL2 theorem prover, producing executable ACL2 formal models, and allowing us to both prove theorems about the translated models as well as validate those models by testing. That translator provided many of the benefits of a pure decompilation into logic approach, but had the disadvantage of not being verified. The availability of Codewalker as of ACL2 7.0 has provided an opportunity to revisit this idea, and employ a more trustworthy decompilation into logic tool. Thus, we have employed the Codewalker method to create an interpreter for a subset of the LLVM instruction set, and have used Codewalker to analyze some simple array-based C programs compiled to LLVM form. We discuss advantages and limitations of the Codewalker-based method compared to the previous method, and provide some challenge problems for future Codewalker development.
Fourier Series Formalization in ACL2(r)
Venue: arXiv cs.LO 2015
Year: 2015

We formalize some basic properties of Fourier series in the logic of ACL2(r), which is a variant of ACL2 that supports reasoning about the real and complex numbers by way of non-standard analysis. More specifically, we extend a framework for formally evaluating definite integrals of real-valued, continuous functions using the Second Fundamental Theorem of Calculus. Our extended framework is also applied to functions containing free arguments. Using this framework, we are able to prove the orthogonality relationships between trigonometric functions, which are the essential properties in Fourier series analysis. The sum rule for definite integrals of indexed sums is also formalized by applying the extended framework along with the First Fundamental Theorem of Calculus and the sum rule for differentiation. The Fourier coefficient formulas of periodic functions are then formalized from the orthogonality relations and the sum rule for integration. Consequently, the uniqueness of Fourier sums is a straightforward corollary. We also present our formalization of the sum rule for definite integrals of infinite series in ACL2(r). Part of this task is to prove the Dini Uniform Convergence Theorem and the continuity of a limit function under certain conditions. A key technique in our proofs of these theorems is to apply the overspill principle from non-standard analysis.
Highway traffic state estimation using speed measurements: case studies on NGSIM data and highway A20 in the Netherlands
Venue: arXiv cs.SY 2015
Year: 2015

This paper presents two case studies where a macroscopic model-based approach for traffic state estimation, which we have recently developed, is employed and tested. The estimation methodology is developed for a "mixed" traffic scenario, where traffic is composed of both ordinary and connected vehicles. Only average speed measurements, which may be obtained from connected vehicles reports, and a minimum number (sufficient to guarantee observability) of spot sensor-based total flow measurements are utilised. In the first case study, we use NGSIM microscopic data in order to test the capability of estimating the traffic state on the basis of aggregated information retrieved from moving vehicles and considering various penetration rates of connected vehicles. In the second case study, a longer highway stretch with internal congestion is utilised, in order to test the capability of the proposed estimation scheme to produce appropriate estimates for varying traffic conditions on long stretches. In both cases the performances are satisfactory, and the obtained results demonstrate the effectiveness of the methodology, both in qualitative and quantitative terms.
Parallel Query in the Suffix Tree
Venue: arXiv cs.DS 2015
Year: 2015

Given the query string of length $m$, we explore a parallel query in a static suffix tree based data structure for $p \ll n$, where $p$ is the number of processors and $n$ is the length of the text. We present three results on CREW PRAM. The parallel query in the suffix trie requires $O(m + p)$ work, $O(m/p + \lg p)$ time and $O(n^2)$ space in the worst case. We extend the same technique to the suffix tree where we show it is, by design, inherently sequential in the worst case. Finally we perform the parallel query using an interleaved approach and achieve $O(m \lg p)$ work, $O(\frac{m}{p} \lg p)$ time and $O(n \lg p)$ space in the worst case.
Tree Automata
Venue: arXiv cs.FL 2015
Year: 2015

This is a reissue of the book Tree Automata by F. Gécseg and M. Steinby originally published in 1984 by Akadémiai Kiadó, Budapest. Some mistakes have been corrected and a few obscure passages have been clarified. Moreover, some more recent contributions and current lines of research are reviewed in an appendix that also contains several new references.
A class of three-weight and five-weight linear codes
Venue: arXiv cs.IT 2015
Year: 2015

Recently, linear codes with few weights have been widely studied, since they have applications in data storage systems, communication systems and consumer electronics. In this paper, we present a class of three-weight and five-weight linear codes over Fp, where p is an odd prime and Fp denotes a finite field with p elements. The weight distributions of the linear codes constructed in this paper are also settled. Moreover, the linear codes illustrated in the paper may have applications in secret sharing schemes.
Design and Analysis of Green Optical Line Terminal for TDM Passive Optical Networks
Venue: arXiv cs.NI 2015
Year: 2015

This paper proposes a novel scheme which can efficiently reduce the energy consumption of Optical Line Terminals (OLTs) in Time Division Multiplexing (TDM) Passive Optical Networks (PONs) such as EPON and GPON. Currently, OLTs consume a significant amount of energy in PON, which is one of the major FTTx technologies. To be environmentally friendly, it is desirable to reduce energy consumption of OLT as much as possible; such requirement becomes even more urgent as OLT keeps increasing its provisioning data rate, and higher data rate provisioning usually implies higher energy consumption. In this paper, we propose a novel energy-efficient OLT structure which guarantees services of end users with the smallest number of power-on OLT line cards. More specifically, we adapt the number of power-on OLT line cards to the real-time incoming traffic. Also, in order to avoid service disruption resulted by powering off OLT line cards, proper optical switches are equipped in OLT to dynamically configure the communications between OLT line cards and ONUs.
A note on linear fractional set packing problem
Venue: arXiv cs.DS 2015
Year: 2015

In this note we point out various errors in the paper by Rashmi Gupta and R. R. Saxena, Set packing problem with linear fractional objective function, International Journal of Mathematics and Computer Applications Research (IJMCAR), 4 (2014) 9 - 18. We also provide some additional results.
Quantum Query Complexity of Subgraph Isomorphism and Homomorphism
Venue: arXiv cs.CC 2015
Year: 2015

Let $H$ be a fixed graph on $n$ vertices. Let $f_H(G) = 1$ iff the input graph $G$ on $n$ vertices contains $H$ as a (not necessarily induced) subgraph. Let $α_H$ denote the cardinality of a maximum independent set of $H$. In this paper we show: \[Q(f_H) = Ω\left(\sqrt{α_H \cdot n}\right),\] where $Q(f_H)$ denotes the quantum query complexity of $f_H$. As a consequence we obtain a lower bounds for $Q(f_H)$ in terms of several other parameters of $H$ such as the average degree, minimum vertex cover, chromatic number, and the critical probability. We also use the above bound to show that $Q(f_H) = Ω(n^{3/4})$ for any $H$, improving on the previously best known bound of $Ω(n^{2/3})$. Until very recently, it was believed that the quantum query complexity is at least square root of the randomized one. Our $Ω(n^{3/4})$ bound for $Q(f_H)$ matches the square root of the current best known bound for the randomized query complexity of $f_H$, which is $Ω(n^{3/2})$ due to Gröger. Interestingly, the randomized bound of $Ω(α_H \cdot n)$ for $f_H$ still remains open. We also study the Subgraph Homomorphism Problem, denoted by $f_{[H]}$, and show that $Q(f_{[H]}) = Ω(n)$. Finally we extend our results to the $3$-uniform hypergraphs. In particular, we show an $Ω(n^{4/5})$ bound for quantum query complexity of the Subgraph Isomorphism, improving on the previously known $Ω(n^{3/4})$ bound. For the Subgraph Homomorphism, we obtain an $Ω(n^{3/2})$ bound for the same.
A Multi-Agent System Approach to Load-Balancing and Resource Allocation for Distributed Computing
Venue: arXiv cs.NE 2015
Year: 2015

In this research we use a decentralized computing approach to allocate and schedule tasks on a massively distributed grid. Using emergent properties of multi-agent systems, the algorithm dynamically creates and dissociates clusters to serve the changing resource demands of a global task queue. The algorithm is compared to a standard First-in First-out (FIFO) scheduling algorithm. Experiments done on a simulator show that the distributed resource allocation protocol (dRAP) algorithm outperforms the FIFO scheduling algorithm on time to empty queue, average waiting time and CPU utilization. Such a decentralized computing approach holds promise for massively distributed processing scenarios like SETI@home and Google MapReduce.
Option contracts for a privacy-aware market
Venue: arXiv cs.CR 2015
Year: 2015

Suppliers (including companies and individual prosumers) may wish to protect their private information when selling items they have in stock. A market is envisaged where private information can be protected through the use of differential privacy and option contracts, while privacy-aware suppliers deliver their stock at a reduced price. In such a marketplace a broker acts as intermediary between privacy-aware suppliers and end customers, providing the extra items possibly needed to fully meet the customers' demand, while end customers book the items they need through an option contract. All stakeholders may benefit from such a marketplace. A formula is provided for the option price, and a budget equation is set for the mechanism to be profitable for the broker/producer.
Diverse Yet Efficient Retrieval using Hash Functions
Venue: arXiv cs.IR 2015
Year: 2015

Typical retrieval systems have three requirements: a) Accurate retrieval i.e., the method should have high precision, b) Diverse retrieval, i.e., the obtained set of points should be diverse, c) Retrieval time should be small. However, most of the existing methods address only one or two of the above mentioned requirements. In this work, we present a method based on randomized locality sensitive hashing which tries to address all of the above requirements simultaneously. While earlier hashing approaches considered approximate retrieval to be acceptable only for the sake of efficiency, we argue that one can further exploit approximate retrieval to provide impressive trade-offs between accuracy and diversity. We extend our method to the problem of multi-label prediction, where the goal is to output a diverse and accurate set of labels for a given document in real-time. Moreover, we introduce a new notion to simultaneously evaluate a method's performance for both the precision and diversity measures. Finally, we present empirical results on several different retrieval tasks and show that our method retrieves diverse and accurate images/labels while ensuring $100x$-speed-up over the existing diverse retrieval approaches.
Virtualizing Lifemapper Software Infrastructure for Biodiversity Expedition
Venue: arXiv cs.SE 2015
Year: 2015

One of the activities of the Pacific Rim Applications and Grid Middleware Assembly (PRAGMA) is fostering Virtual Biodiversity Expeditions (VBEs) by bringing domain scientists and cyber infrastructure specialists together as a team. Over the past few years PRAGMA members have been collaborating on virtualizing the Lifemapper software. Virtualization and cloud computing have introduced great flexibility and efficiency into IT projects. Virtualization provides application scalability, maximizes resources utilization, and creates a more efficient, agile, and automated infrastructure. However, there are downsides to the complexity inherent in these environments, including the need for special techniques to deploy cluster hosts, dependence on virtual environments, and challenging application installation, management, and configuration. In this paper, we report on progress of the Lifemapper virtualization framework focused on a reproducible and highly configurable infrastructure capable of fast deployment. A key contribution of this work is describing the practical experience in taking a complex, clustered, domain-specific, data analysis and simulation system and making it available to operate on a variety of system configurations. Uses of this portability range from whole cluster replication to teaching and experimentation on a single laptop. System virtualization is used to practically define and make portable the full application stack, including all of its complex set of supporting software.
Bin Packing with Linear Usage Costs
Venue: arXiv cs.DS 2015
Year: 2015

Bin packing is a well studied problem involved in many applications. The classical bin packing problem is about minimising the number of bins and ignores how the bins are utilised. We focus in this paper, on a variant of bin packing that is at the heart of efficient management of data centres. In this context, servers can be viewed as bins and virtual machines as items. The efficient management of a data-centre involves minimising energy costs while ensuring service quality. The assignment of virtual machines on servers and how these servers are utilised has a huge impact on the energy consumption. We focus on a bin packing problem where linear costs are associated to the use of bins to model the energy consumption. We study lower bounds based on Linear Programming and extend the bin packing global constraint with cost information.
Preprint: Intuitive Evaluation of Kinect2 based Balance Measurement Software
Venue: arXiv cs.HC 2015
Year: 2015

This is the preprint version of our paper on REHAB2015. A balance measurement software based on Kinect2 sensor is evaluated by comparing to golden standard balance measure platform intuitively. The software analysis the tracked body data from the user by Kinect2 sensor and get user's center of mass(CoM) as well as its motion route on a plane. The software is evaluated by several comparison tests, the evaluation results preliminarily prove the reliability of the software.
Supersizing Self-supervision: Learning to Grasp from 50K Tries and 700 Robot Hours
Venue: arXiv cs.LG 2015
Year: 2015

Current learning-based robot grasping approaches exploit human-labeled datasets for training the models. However, there are two problems with such a methodology: (a) since each object can be grasped in multiple ways, manually labeling grasp locations is not a trivial task; (b) human labeling is biased by semantics. While there have been attempts to train robots using trial-and-error experiments, the amount of data used in such experiments remains substantially low and hence makes the learner prone to over-fitting. In this paper, we take the leap of increasing the available training data to 40 times more than prior work, leading to a dataset size of 50K data points collected over 700 hours of robot grasping attempts. This allows us to train a Convolutional Neural Network (CNN) for the task of predicting grasp locations without severe overfitting. In our formulation, we recast the regression problem to an 18-way binary classification over image patches. We also present a multi-stage learning approach where a CNN trained in one stage is used to collect hard negatives in subsequent stages. Our experiments clearly show the benefit of using large-scale datasets (and multi-stage training) for the task of grasping. We also compare to several baselines and show state-of-the-art performance on generalization to unseen objects for grasping.
Design and Implementation of Domain based Semantic Hidden Web Crawler
Venue: arXiv cs.IR 2015
Year: 2015

Web is a wide term which mainly consists of surface web and hidden web. One can easily access the surface web using traditional web crawlers, but they are not able to crawl the hidden portion of the web. These traditional crawlers retrieve contents from web pages, which are linked by hyperlinks ignoring the information hidden behind form pages, which cannot be extracted using simple hyperlink structure. Thus, they ignore large amount of data hidden behind search forms. This paper emphasizes on the extraction of hidden data behind html search forms. The proposed technique makes use of semantic mapping to fill the html search form using domain specific database. Using semantics to fill various fields of a form leads to more accurate and qualitative data extraction.
Throughput capacity of two-hop relay MANETs under finite buffers
Venue: arXiv cs.PF 2015
Year: 2015

Since the seminal work of Grossglauser and Tse [1], the two-hop relay algorithm and its variants have been attractive for mobile ad hoc networks (MANETs) due to their simplicity and efficiency. However, most literature assumed an infinite buffer size for each node, which is obviously not applicable to a realistic MANET. In this paper, we focus on the exact throughput capacity study of two-hop relay MANETs under the practical finite relay buffer scenario. The arrival process and departure process of the relay queue are fully characterized, and an ergodic Markov chain-based framework is also provided. With this framework, we obtain the limiting distribution of the relay queue and derive the throughput capacity under any relay buffer size. Extensive simulation results are provided to validate our theoretical framework and explore the relationship among the throughput capacity, the relay buffer size and the number of nodes.
A Novel Method for Soft Error Mitigation in FPGA using Adaptive Cross Parity Code
Venue: arXiv cs.AR 2015
Year: 2015

Field Programmable Gate Arrays (FPGAs) are more prone to be affected by transient faults in presence of radiation and other environmental hazards compared to Application Specific Integrated Circuits (ASICs). Hence, error mitigation and recovery techniques are absolutely necessary to protect the FPGA hardware from soft errors arising due to such transient faults. In this paper, a new efficient multi-bit error correcting method for FPGAs is proposed using adaptive cross parity check (ACPC) code. ACPC is easy to implement and the needed decoding circuit is also simple. In the proposed scheme total configuration memory is partitioned into two parts. One part will contain ACPC hardware, which is static and assumed to be unaffected by any kind of errors. Other portion will store the binary file for logic, which is to be protected from transient error and is assumed to be dynamically reconfigurable (Partial reconfigurable area). Binary file from the secondary memory passes through ACPC hardware and the bits for forward error correction (FEC) field are calculated before entering into the reconfigurable portion. In the runtime scenario, the data from the dynamically reconfigurable portion of the configuration memory will be read back and passed through the ACPC hardware. The ACPC hardware will correct the errors before the data enters into the dynamic configuration memory. We propose a first of its kind methodology for novel transient fault correction using ACPC code for FPGAs. To validate the design we have tested the proposed methodology with Kintex FPGA. We have also measured different parameters like critical path, power consumption, overhead resource and error correction efficiency to estimate the performance of our proposed method.
Size-Dependent Tile Self-Assembly: Constant-Height Rectangles and Stability
Venue: arXiv cs.CG 2015
Year: 2015

We introduce a new model of algorithmic tile self-assembly called size-dependent assembly. In previous models, supertiles are stable when the total strength of the bonds between any two halves exceeds some constant temperature. In this model, this constant temperature requirement is replaced by an nondecreasing temperature function $τ: \mathbb{N} \rightarrow \mathbb{N}$ that depends on the size of the smaller of the two halves. This generalization allows supertiles to become unstable and break apart, and captures the increased forces that large structures may place on the bonds holding them together. We demonstrate the power of this model in two ways. First, we give fixed tile sets that assemble constant-height rectangles and squares of arbitrary input size given an appropriate temperature function. Second, we prove that deciding whether a supertile is stable is coNP-complete. Both results contrast with known results for fixed temperature.
Dynamic concurrent van Emde Boas array
Venue: arXiv cs.DS 2015
Year: 2015

The growing popularity of shared-memory multiprocessor machines has caused significant changes in the design of concurrent software. In this approach, the concurrently running threads communicate and synchronize with each other through data structures in shared memory. Hence, the efficiency of these structures is essential for the performance of concurrent applications. The need to find new concurrent data structures prompted the author some time ago to propose the cvEB array modeled on the van Emde Boas Tree structure as a dynamic set alternative. This paper describes an improved version of that structure - the dcvEB array (Dynamic Concurrent van Emde Boas Array). One of the improvements involves memory usage optimization. This enhancement required the design of a tree which grows and shrinks at both: the top (root) and the bottom (leaves) level. Another enhancement concerns the successor (and predecessor) search strategy. The tests performed seem to confirm the high performance of the dcvEB array. They are especially visible when the range of keys is significantly larger than the number of elements in the collection.
3D Scan Registration using Curvelet Features in Planetary Environments
Venue: arXiv cs.CV 2015
Year: 2015

Topographic mapping in planetary environments relies on accurate 3D scan registration methods. However, most global registration algorithms relying on features such as FPFH and Harris-3D show poor alignment accuracy in these settings due to the poor structure of the Mars-like terrain and variable resolution, occluded, sparse range data that is hard to register without some a-priori knowledge of the environment. In this paper, we propose an alternative approach to 3D scan registration using the curvelet transform that performs multi-resolution geometric analysis to obtain a set of coefficients indexed by scale (coarsest to finest), angle and spatial position. Features are detected in the curvelet domain to take advantage of the directional selectivity of the transform. A descriptor is computed for each feature by calculating the 3D spatial histogram of the image gradients, and nearest neighbor based matching is used to calculate the feature correspondences. Correspondence rejection using Random Sample Consensus identifies inliers, and a locally optimal Singular Value Decomposition-based estimation of the rigid-body transformation aligns the laser scans given the re-projected correspondences in the metric space. Experimental results on a publicly available data-set of planetary analogue indoor facility, as well as simulated and real-world scans from Neptec Design Group's IVIGMS 3D laser rangefinder at the outdoor CSA Mars yard demonstrates improved performance over existing methods in the challenging sparse Mars-like terrain.