OpenRaiser/Intern-Atlas huggingface dataset:
Fully De-Amortized Cuckoo Hashing for Cache-Oblivious Dictionaries and Multimaps
Venue: arXiv cs.DS 2011
Year: 2011

A dictionary (or map) is a key-value store that requires all keys be unique, and a multimap is a key-value store that allows for multiple values to be associated with the same key. We design hashing-based indexing schemes for dictionaries and multimaps that achieve worst-case optimal performance for lookups and updates, with a small or negligible probability the data structure will require a rehash operation, depending on whether we are working in the the external-memory (I/O) model or one of the well-known versions of the Random Access Machine (RAM) model. One of the main features of our constructions is that they are \emph{fully de-amortized}, meaning that their performance bounds hold without one having to tune their constructions with certain performance parameters, such as the constant factors in the exponents of failure probabilities or, in the case of the external-memory model, the size of blocks or cache lines and the size of internal memory (i.e., our external-memory algorithms are cache oblivious). Our solutions are based on a fully de-amortized implementation of cuckoo hashing, which may be of independent interest. This hashing scheme uses two cuckoo hash tables, one "nested" inside the other, with one serving as a primary structure and the other serving as an auxiliary supporting queue/stash structure that is super-sized with respect to traditional auxiliary structures but nevertheless adds negligible storage to our scheme. This auxiliary structure allows the success probability for cuckoo hashing to be very high, which is useful in cryptographic or data-intensive applications.
Short Huffman Codes Producing 1s Half of the Time
Venue: arXiv cs.IT 2011
Year: 2011

The design of the channel part of a digital communication system (e.g., error correction, modulation) is heavily based on the assumption that the data to be transmitted forms a fair bit stream. However, simple source encoders such as short Huffman codes generate bit streams that poorly match this assumption. As a result, the channel input distribution does not match the original design criteria. In this work, a simple method called half Huffman coding (halfHc) is developed. halfHc transforms a Huffman code into a source code whose output is more similar to a fair bit stream. This is achieved by permuting the codewords such that the frequency of 1s at the output is close to 0.5. The permutations are such that the optimality in terms of achieved compression ratio is preserved. halfHc is applied in a practical example, and the resulting overall system performs better than when conventional Huffman coding is used.
Leveraging Bus Mobility to Enable Communications in Urban Areas
Venue: arXiv cs.NI 2011
Year: 2011

This paper shows that the deployment of an opportunistic network on any public transportation system leads to obtain a scalable and efficient urban communication platform. We use the term Bus Switched Networks (BSNs) to indicate this urban backbone that complements the services of 3G networks and enables to meet the application level requirements for a large class of applications by ensuring high delivery ratio and acceptable delays under different conditions of packet load. We sustain these arguments by providing three contributions. The first contribution is a novel and lightweight probabilistic routing protocol for BSN which we prove to be highly effective in satisfying the loose QoS required by urban-wide delay-tolerant information services. The second contribution is the proposal of URBeS, an analysis platform that, given a specific city served by public transportation, produces real bus mobility traces and traffic analysis for any given routing protocol. The last contribution is an extensive benchmark analysis on three real cities which have been selected to explore geo and structural diversity.
Applications of Derandomization Theory in Coding
Venue: arXiv cs.DM 2011
Year: 2011

Randomized techniques play a fundamental role in theoretical computer science and discrete mathematics, in particular for the design of efficient algorithms and construction of combinatorial objects. The basic goal in derandomization theory is to eliminate or reduce the need for randomness in such randomized constructions. In this thesis, we explore some applications of the fundamental notions in derandomization theory to problems outside the core of theoretical computer science, and in particular, certain problems related to coding theory. First, we consider the wiretap channel problem which involves a communication system in which an intruder can eavesdrop a limited portion of the transmissions, and construct efficient and information-theoretically optimal communication protocols for this model. Then we consider the combinatorial group testing problem. In this classical problem, one aims to determine a set of defective items within a large population by asking a number of queries, where each query reveals whether a defective item is present within a specified group of items. We use randomness condensers to explicitly construct optimal, or nearly optimal, group testing schemes for a setting where the query outcomes can be highly unreliable, as well as the threshold model where a query returns positive if the number of defectives pass a certain threshold. Finally, we design ensembles of error-correcting codes that achieve the information-theoretic capacity of a large class of communication channels, and then use the obtained ensembles for construction of explicit capacity achieving codes. [This is a shortened version of the actual abstract in the thesis.]
Parallel Backtracking with Answer Memoing for Independent And-Parallelism
Venue: arXiv cs.PL 2011
Year: 2011

Goal-level Independent and-parallelism (IAP) is exploited by scheduling for simultaneous execution two or more goals which will not interfere with each other at run time. This can be done safely even if such goals can produce multiple answers. The most successful IAP implementations to date have used recomputation of answers and sequentially ordered backtracking. While in principle simplifying the implementation, recomputation can be very inefficient if the granularity of the parallel goals is large enough and they produce several answers, while sequentially ordered backtracking limits parallelism. And, despite the expected simplification, the implementation of the classic schemes has proved to involve complex engineering, with the consequent difficulty for system maintenance and extension, while still frequently running into the well-known trapped goal and garbage slot problems. This work presents an alternative parallel backtracking model for IAP and its implementation. The model features parallel out-of-order (i.e., non-chronological) backtracking and relies on answer memoization to reuse and combine answers. We show that this approach can bring significant performance advantages. Also, it can bring some simplification to the important engineering task involved in implementing the backtracking mechanism of previous approaches.
Design of Arabic Diacritical Marks
Venue: arXiv cs.CL 2011
Year: 2011

Diacritical marks play a crucial role in meeting the criteria of usability of typographic text, such as: homogeneity, clarity and legibility. To change the diacritic of a letter in a word could completely change its semantic. The situation is very complicated with multilingual text. Indeed, the problem of design becomes more difficult by the presence of diacritics that come from various scripts; they are used for different purposes, and are controlled by various typographic rules. It is quite challenging to adapt rules from one script to another. This paper aims to study the placement and sizing of diacritical marks in Arabic script, with a comparison with the Latin's case. The Arabic script is cursive and runs from right-to-left; its criteria and rules are quite distinct from those of the Latin script. In the beginning, we compare the difficulty of processing diacritics in both scripts. After, we will study the limits of Latin resolution strategies when applied to Arabic. At the end, we propose an approach to resolve the problem for positioning and resizing diacritics. This strategy includes creating an Arabic font, designed in OpenType format, along with suitable justification in TEX.
Actual Causation in CP-logic
Venue: arXiv cs.AI 2011
Year: 2011

Given a causal model of some domain and a particular story that has taken place in this domain, the problem of actual causation is deciding which of the possible causes for some effect actually caused it. One of the most influential approaches to this problem has been developed by Halpern and Pearl in the context of structural models. In this paper, I argue that this is actually not the best setting for studying this problem. As an alternative, I offer the probabilistic logic programming language of CP-logic. Unlike structural models, CP-logic incorporates the deviant/default distinction that is generally considered an important aspect of actual causation, and it has an explicitly dynamic semantics, which helps to formalize the stories that serve as input to an actual causation problem.
Dual-Level Compressed Aggregation: Recovering Fields of Physical Quantities from Incomplete Sensory Data
Venue: arXiv cs.NI 2011
Year: 2011

Although wireless sensor networks (WSNs) are powerful in monitoring physical events, the data collected from a WSN are almost always incomplete if the surveyed physical event spreads over a wide area. The reason for this incompleteness is twofold: i) insufficient network coverage and ii) data aggregation for energy saving. Whereas the existing recovery schemes only tackle the second aspect, we develop Dual-lEvel Compressed Aggregation (DECA) as a novel framework to address both aspects. Specifically, DECA allows a high fidelity recovery of a widespread event, under the situations that the WSN only sparsely covers the event area and that an in-network data aggregation is applied for traffic reduction. Exploiting both the low-rank nature of real-world events and the redundancy in sensory data, DECA combines matrix completion with a fine-tuned compressed sensing technique to conduct a dual-level reconstruction process. We demonstrate that DECA can recover a widespread event with less than 5% of the data, with respect to the dimension of the event, being collected. Performance evaluation based on both synthetic and real data sets confirms the recovery fidelity and energy efficiency of our DECA framework.
Oblivious RAM Simulation with Efficient Worst-Case Access Overhead
Venue: arXiv cs.CR 2011
Year: 2011

Oblivious RAM simulation is a method for achieving confidentiality and privacy in cloud computing environments. It involves obscuring the access patterns to a remote storage so that the manager of that storage cannot infer information about its contents. Existing solutions typically involve small amortized overheads for achieving this goal, but nevertheless involve potentially huge variations in access times, depending on when they occur. In this paper, we show how to de-amortize oblivious RAM simulations, so that each access takes a worst-case bounded amount of time.
Cooperative Estimation of 3D Target Motion via Networked Visual Motion Observer
Venue: arXiv cs.SY 2011
Year: 2011

This paper investigates cooperative estimation of 3D target object motion for visual sensor networks. In particular, we consider the situation where multiple smart vision cameras see a group of target objects. The objective here is to meet two requirements simultaneously: averaging for static objects and tracking to moving target objects. For this purpose, we present a cooperative estimation mechanism called networked visual motion observer. We then derive an upper bound of the ultimate error between the actual average and the estimates produced by the present networked estimation mechanism. Moreover, we also analyze the tracking performance of the estimates to moving target objects. Finally the effectiveness of the networked visual motion observer is demonstrated through simulation.
Analysis of the Incircle predicate for the Euclidean Voronoi diagram of axes-aligned line segments
Venue: arXiv cs.CG 2011
Year: 2011

In this paper we study the most-demanding predicate for computing the Euclidean Voronoi diagram of axes-aligned line segments, namely the Incircle predicate. Our contribution is two-fold: firstly, we describe, in algorithmic terms, how to compute the Incircle predicate for axes-aligned line segments, and secondly we compute its algebraic degree. Our primary aim is to minimize the algebraic degree, while, at the same time, taking into account the amount of operations needed to compute our predicate of interest. In our predicate analysis we show that the Incircle predicate can be answered by evaluating the signs of algebraic expressions of degree at most 6; this is half the algebraic degree we get when we evaluate the Incircle predicate using the current state-of-the-art approach. In the most demanding cases of our predicate evaluation, we reduce the problem of answering the Incircle predicate to the problem of computing the sign of the value of a linear polynomial (in one variable), when evaluated at a known specific root of a quadratic polynomial (again in one variable). Another important aspect of our approach is that, from a geometric point of view, we answer the most difficult case of the predicate via implicitly performing point locations on an appropriately defined subdivision of the place induced by the Voronoi circle implicated in the Incircle predicate.
Information-theoretically Secure Regenerating Codes for Distributed Storage
Venue: arXiv cs.IT 2011
Year: 2011

Regenerating codes are a class of codes for distributed storage networks that provide reliability and availability of data, and also perform efficient node repair. Another important aspect of a distributed storage network is its security. In this paper, we consider a threat model where an eavesdropper may gain access to the data stored in a subset of the storage nodes, and possibly also, to the data downloaded during repair of some nodes. We provide explicit constructions of regenerating codes that achieve information-theoretic secrecy capacity in this setting.
Bidirectional Pipelining for Scalable IP Lookup and Packet Classification
Venue: arXiv cs.NI 2011
Year: 2011

Both IP lookup and packet classification in IP routers can be implemented by some form of tree traversal. SRAM-based Pipelining can improve the throughput dramatically. However, previous pipelining schemes result in unbalanced memory allocation over the pipeline stages. This has been identified as a major challenge for scalable pipelined solutions. This paper proposes a flexible bidirectional linear pipeline architecture based on widely-used dual-port SRAMs. A search tree is partitioned, and then mapped onto pipeline stages by a bidirectional fine-grained mapping scheme. We introduce the notion of inversion factor and several heuristics to invert subtrees for memory balancing. Due to its linear structure, the architecture maintains packet input order, and supports non-blocking route updates. Our experiments show that, the architecture can achieve a perfectly balanced memory distribution over the pipeline stages, for both trie-based IP lookup and tree-based multi-dimensional packet classification. For IP lookup, it can store a full backbone routing table with 154419 entries using 2MB of memory, and sustain a high throughput of 1.87 billion packets per second (GPPS), i.e. 0.6 Tbps for the minimum size (40 bytes) packets. The throughput can be improved further to be 2.4 Tbps, by employing caching to exploit the Internet traffic locality.
Proposed Information Sharing Security Approach for Security Personnels, Vertical Integration, Semantic Interoperability Architecture and Framework for Digital Government
Venue: arXiv cs.CR 2011
Year: 2011

This paper mainly depicts the conceptual overview of vertical integration, semantic interoperability architecture such as Educational Sector Architectural Framework (ESAF) for New Zealand government and different interoperability framework solution for digital government. In this paper, we try to develop a secure information sharing approach for digital government to improve home land security. This approach is a role and cooperation based approach for security personnel of different government departments. In order to run any successful digital government of any country in the world, it is necessary to interact with their citizen and to share secure information via different network among the citizen or other government. Consequently, in order to smooth the progress of users to cooperate with and share information without darkness and flawlessly transversely different networks and databases universally, a safe and trusted information-sharing environment has been renowned as a very important requirement and to press forward homeland security endeavor. The key incentive following this research is to put up a secure and trusted information-sharing approach for government departments. This paper presents a proficient function and teamwork based information sharing approach for safe exchange of hush-hush and privileged information amid security personnels and government departments inside the national boundaries by means of public key cryptography. The expanded approach makes use of cryptographic hash function; public key cryptosystem and a unique and complex mapping function for securely swapping over secret information. Moreover, the projected approach facilitates privacy preserving information sharing with probable restrictions based on the rank of the security personnels.
Measuring Pulsed Interference in 802.11 Links
Venue: arXiv cs.NI 2011
Year: 2011

Wireless 802.11 links operate in unlicensed spectrum and so must accommodate other unlicensed transmitters which generate pulsed interference. We propose a new approach for detecting the presence of pulsed interference affecting 802.11 links, and for estimating temporal statistics of this interference. This approach builds on recent work on distinguishing collision losses from noise losses in 802.11 links. When the intervals between interference pulses are i.i.d., the approach is not confined to estimating the mean and variance of these intervals but can recover the complete probability distribution. The approach is a transmitter-side technique that provides per-link information and is compatible with standard hardware. We demonstrate the effectiveness of the proposed approach using extensive experimental measurements. In addition to applications to monitoring, management and diagnostics, the fundamental information provided by our approach can potentially be used to adapt the frame durations used in a network so as to increase capacity in the presence of pulsed interference.
Axioms for Rational Reinforcement Learning
Venue: arXiv cs.LG 2011
Year: 2011

We provide a formal, simple and intuitive theory of rational decision making including sequential decisions that affect the environment. The theory has a geometric flavor, which makes the arguments easy to visualize and understand. Our theory is for complete decision makers, which means that they have a complete set of preferences. Our main result shows that a complete rational decision maker implicitly has a probabilistic model of the environment. We have a countable version of this result that brings light on the issue of countable vs finite additivity by showing how it depends on the geometry of the space which we have preferences over. This is achieved through fruitfully connecting rationality with the Hahn-Banach Theorem. The theory presented here can be viewed as a formalization and extension of the betting odds approach to probability of Ramsey and De Finetti.
Lagrange Stabilization of Pendulum-like Systems: A Pseudo H-infinity Control Approach
Venue: arXiv cs.SY 2011
Year: 2011

This paper studies the Lagrange stabilization of a class of nonlinear systems whose linear part has a singular system matrix and which have multiple periodic (in state) nonlinearities. Both state and output feedback Lagrange stabilization problems are considered. The paper develops a pseudo H-infinity control theory to solve these stabilization problems. In a similar fashion to the Strict Bounded Real Lemma in classic H-infinity control theory, a Pseudo Strict Bounded Real Lemma is established for systems with a single unstable pole. Sufficient conditions for the synthesis of state feedback and output feedback controllers are given to ensure that the closed-loop system is pseudo strict bounded real. The pseudo H-infinity control approach is applied to solve state feedback and output feedback Lagrange stabilization problems for nonlinear systems with multiple nonlinearities. An example is given to illustrate the proposed method.
Automatic Network Reconstruction using ASP
Venue: arXiv cs.LG 2011
Year: 2011

Building biological models by inferring functional dependencies from experimental data is an im- portant issue in Molecular Biology. To relieve the biologist from this traditionally manual process, various approaches have been proposed to increase the degree of automation. However, available ap- proaches often yield a single model only, rely on specific assumptions, and/or use dedicated, heuris- tic algorithms that are intolerant to changing circumstances or requirements in the view of the rapid progress made in Biotechnology. Our aim is to provide a declarative solution to the problem by ap- peal to Answer Set Programming (ASP) overcoming these difficulties. We build upon an existing approach to Automatic Network Reconstruction proposed by part of the authors. This approach has firm mathematical foundations and is well suited for ASP due to its combinatorial flavor providing a characterization of all models explaining a set of experiments. The usage of ASP has several ben- efits over the existing heuristic algorithms. First, it is declarative and thus transparent for biological experts. Second, it is elaboration tolerant and thus allows for an easy exploration and incorporation of biological constraints. Third, it allows for exploring the entire space of possible models. Finally, our approach offers an excellent performance, matching existing, special-purpose systems.
Termination in a Pi-calculus with Subtyping
Venue: arXiv cs.LO 2011
Year: 2011

We present a type system to guarantee termination of pi-calculus processes that exploits input/output capabilities and subtyping, as originally introduced by Pierce and Sangiorgi, in order to analyse the usage of channels. We show that our system improves over previously existing proposals by accepting more processes as terminating. This increased expressiveness allows us to capture sensible programming idioms. We demonstrate how our system can be extended to handle the encoding of the simply typed lambda-calculus, and discuss questions related to type inference.
On the Role of Diversity in Sparsity Estimation
Venue: arXiv cs.IT 2011
Year: 2011

A major challenge in sparsity pattern estimation is that small modes are difficult to detect in the presence of noise. This problem is alleviated if one can observe samples from multiple realizations of the nonzero values for the same sparsity pattern. We will refer to this as "diversity". Diversity comes at a price, however, since each new realization adds new unknown nonzero values, thus increasing uncertainty. In this paper, upper and lower bounds on joint sparsity pattern estimation are derived. These bounds, which improve upon existing results even in the absence of diversity, illustrate key tradeoffs between the number of measurements, the accuracy of estimation, and the diversity. It is shown, for instance, that diversity introduces a tradeoff between the uncertainty in the noise and the uncertainty in the nonzero values. Moreover, it is shown that the optimal amount of diversity significantly improves the behavior of the estimation problem for both optimal and computationally efficient estimators.