OpenRaiser/Intern-Atlas huggingface dataset:
Transparent Programming of Heterogeneous Smartphones for Sensing
Venue: arXiv cs.OS 2011
Year: 2011

Sensing on smartphones is known to be power-hungry. It has been shown that this problem can be solved by adding an ultra low-power processor to execute simple, frequent sensor data processing. While very effective in saving energy, this resulting heterogeneous, distributed architecture poses a significant challenge to application development. We present Reflex, a suite of runtime and compilation techniques to conceal the heterogeneous, distributed nature from developers. The Reflex automatically transforms the developer's code for distributed execution with the help of the Reflex runtime. To create a unified system illusion, Reflex features a novel software distributed shared memory (DSM) design that leverages the extreme architectural asymmetry between the low-power processor and the powerful central processor to achieve both energy efficiency and performance. We report a complete realization of Reflex for heterogeneous smartphones with Maemo/Linux as the central kernel. Using a tri-processor hardware prototype and sensing applications reported in recent literature, we evaluate the Reflex realization for programming transparency, energy efficiency, and performance. We show that Reflex supports a programming style that is very close to contemporary smartphone programming. It allows existing sensing applications to be ported with minor source code changes. Reflex reduces the system power in sensing by up to 83%, and its runtime system only consumes 10% local memory on a typical ultra-low power processor.
Automatic Wrappers for Large Scale Web Extraction
Venue: arXiv cs.DB 2011
Year: 2011

We present a generic framework to make wrapper induction algorithms tolerant to noise in the training data. This enables us to learn wrappers in a completely unsupervised manner from automatically and cheaply obtained noisy training data, e.g., using dictionaries and regular expressions. By removing the site-level supervision that wrapper-based techniques require, we are able to perform information extraction at web-scale, with accuracy unattained with existing unsupervised extraction techniques. Our system is used in production at Yahoo! and powers live applications.
Optimal query/update tradeoffs in versioned dictionaries
Venue: arXiv cs.DS 2011
Year: 2011

External-memory dictionaries are a fundamental data structure in file systems and databases. Versioned (or fully-persistent) dictionaries have an associated version tree where queries can be performed at any version, updates can be performed on leaf versions, and any version can be `cloned' by adding a child. Various query/update tradeoffs are known for unversioned dictionaries, many of them with matching upper and lower bounds. No fully-versioned external-memory dictionaries are known with optimal space/query/update tradeoffs. In particular, no versioned constructions are known that offer updates in $o(1)$ I/Os using O(N) space. We present the first cache-oblivious and cache-aware constructions that achieve a wide range of optimal points on this tradeoff.
Accelerating Nearest Neighbor Search on Manycore Systems
Venue: arXiv cs.DB 2011
Year: 2011

We develop methods for accelerating metric similarity search that are effective on modern hardware. Our algorithms factor into easily parallelizable components, making them simple to deploy and efficient on multicore CPUs and GPUs. Despite the simple structure of our algorithms, their search performance is provably sublinear in the size of the database, with a factor dependent only on its intrinsic dimensionality. We demonstrate that our methods provide substantial speedups on a range of datasets and hardware platforms. In particular, we present results on a 48-core server machine, on graphics hardware, and on a multicore desktop.
Scheduled-PEG construction of LDPC codes for Upper-Layer FEC
Venue: arXiv cs.IT 2011
Year: 2011

The Progressive Edge Growth (PEG) algorithm is one of the most widely-used method for constructing finite length LDPC codes. In this paper we consider the PEG algorithm together with a scheduling distribution, which specifies the order in which edges are established in the graph. The goal is to find a scheduling distribution that yields "the best" performance in terms of decoding overhead, performance metric specific to erasure codes and widely used for upper-layer forward error correction (UL-FEC). We rigorously formulate this optimization problem, and we show that it can be addressed by using genetic optimization algorithms. We also exhibit PEG codes with optimized scheduling distribution, whose decoding overhead is less than half of the decoding overhead of their classical-PEG counterparts.
Sparse Transfer Learning for Interactive Video Search Reranking
Venue: arXiv cs.IR 2011
Year: 2011

Visual reranking is effective to improve the performance of the text-based video search. However, existing reranking algorithms can only achieve limited improvement because of the well-known semantic gap between low level visual features and high level semantic concepts. In this paper, we adopt interactive video search reranking to bridge the semantic gap by introducing user's labeling effort. We propose a novel dimension reduction tool, termed sparse transfer learning (STL), to effectively and efficiently encode user's labeling information. STL is particularly designed for interactive video search reranking. Technically, it a) considers the pair-wise discriminative information to maximally separate labeled query relevant samples from labeled query irrelevant ones, b) achieves a sparse representation for the subspace to encodes user's intention by applying the elastic net penalty, and c) propagates user's labeling information from labeled samples to unlabeled samples by using the data distribution knowledge. We conducted extensive experiments on the TRECVID 2005, 2006 and 2007 benchmark datasets and compared STL with popular dimension reduction algorithms. We report superior performance by using the proposed STL based interactive video search reranking.
Fitting Ranked English and Spanish Letter Frequency Distribution in U.S. and Mexican Presidential Speeches
Venue: arXiv cs.CL 2011
Year: 2011

The limited range in its abscissa of ranked letter frequency distributions causes multiple functions to fit the observed distribution reasonably well. In order to critically compare various functions, we apply the statistical model selections on ten functions, using the texts of U.S. and Mexican presidential speeches in the last 1-2 centuries. Dispite minor switching of ranking order of certain letters during the temporal evolution for both datasets, the letter usage is generally stable. The best fitting function, judged by either least-square-error or by AIC/BIC model selection, is the Cocho/Beta function. We also use a novel method to discover clusters of letters by their observed-over-expected frequency ratios.
Syntactic Complexity of Prefix-, Suffix-, Bifix-, and Factor-Free Regular Languages
Venue: arXiv cs.FL 2011
Year: 2011

The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of the class of regular languages is the maximal syntactic complexity of languages in that class, taken as a function of the state complexity $n$ of these languages. We study the syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages. We prove that $n^{n-2}$ is a tight upper bound for prefix-free regular languages. We present properties of the syntactic semigroups of suffix-, bifix-, and factor-free regular languages, conjecture tight upper bounds on their size to be $(n-1)^{n-2}+(n-2)$, $(n-1)^{n-3} + (n-2)^{n-3} + (n-3)2^{n-3}$, and $(n-1)^{n-3} + (n-3)2^{n-3} + 1$, respectively, and exhibit languages with these syntactic complexities.
Generalized Filtering Decomposition
Venue: arXiv cs.NA 2011
Year: 2011

This paper introduces a new preconditioning technique that is suitable for matrices arising from the discretization of a system of PDEs on unstructured grids. The preconditioner satisfies a so-called filtering property, which ensures that the input matrix is identical with the preconditioner on a given filtering vector. This vector is chosen to alleviate the effect of low frequency modes on convergence and so decrease or eliminate the plateau which is often observed in the convergence of iterative methods. In particular, the paper presents a general approach that allows to ensure that the filtering condition is satisfied in a matrix decomposition. The input matrix can have an arbitrary sparse structure. Hence, it can be reordered using nested dissection, to allow a parallel computation of the preconditioner and of the iterative process.
Cryptanalysis And Further Improvement Of A Biometric-Based Remote User Authentication Scheme Using Smart Cards
Venue: arXiv cs.CR 2011
Year: 2011

Recently, Li et al. proposed a secure biometric-based remote user authentication scheme using smart cards to withstand the security flaws of Li-Hwang's efficient biometric-based remote user authentication scheme using smart cards. Li et al.'s scheme is based on biometrics verification, smart card and one-way hash function, and it also uses the random nonce rather than a synchronized clock, and thus it is efficient in computational cost and more secure than Li-Hwang's scheme. Unfortunately, in this paper we show that Li et al.'s scheme still has some security weaknesses in their design. In order to withstand those weaknesses in their scheme, we further propose an improvement of their scheme so that the improved scheme always provides proper authentication and as a result, it establishes a session key between the user and the server at the end of successful user authentication.
Which cities produce excellent papers worldwide more than can be expected? A new mapping approach--using Google Maps--based on statistical significance testing
Venue: arXiv cs.DL 2011
Year: 2011

The methods presented in this paper allow for a statistical analysis revealing centers of excellence around the world using programs that are freely available. Based on Web of Science data, field-specific excellence can be identified in cities where highly-cited papers were published significantly. Compared to the mapping approaches published hitherto, our approach is more analytically oriented by allowing the assessment of an observed number of excellent papers for a city (in the sample) against the expected number. Using this test, the approach cannot only identify the top performers in output but the "true jewels." These are cities locating authors who publish significantly more top cited papers than can be expected. As the examples in this paper show for physics, chemistry, and psychology, these cities do not necessarily have a high output of excellent papers.
Measuring NUMA effects with the STREAM benchmark
Venue: arXiv cs.PF 2011
Year: 2011

Modern high-end machines feature multiple processor packages, each of which contains multiple independent cores and integrated memory controllers connected directly to dedicated physical RAM. These packages are connected via a shared bus, creating a system with a heterogeneous memory hierarchy. Since this shared bus has less bandwidth than the sum of the links to memory, aggregate memory bandwidth is higher when parallel threads all access memory local to their processor package than when they access memory attached to a remote package. But, the impact of this heterogeneous memory architecture is not easily understood from vendor benchmarks. Even where these measurements are available, they provide only best-case memory throughput. This work presents a series of modifications to the well-known STREAM benchmark to measure the effects of NUMA on both a 48-core AMD Opteron machine and a 32-core Intel Xeon machine.
Generic Trace Logics
Venue: arXiv cs.LO 2011
Year: 2011

We combine previous work on coalgebraic logic with the coalgebraic traces semantics of Hasuo, Jacobs, and Sokolova.
Feedback Reduction for MIMO Broadcast Channel with Heterogeneous Fading
Venue: arXiv cs.IT 2011
Year: 2011

This paper considers feedback load reduction for multiuser multiple input multiple output (MIMO) broadcast channel where the users' channel distributions are not homogeneous. A cluster-based feedback scheme is proposed such that the range of possible signal-to-noise ratio (SNR) of the users are divided into several clusters according to the order statistics of the users' SNRs. Each cluster has a corresponding threshold, and the users compare their measured instantaneous SNRs with the thresholds to determine whether and how many bits they should use to feed back their instantaneous SNRs. If a user's instantaneous SNR is lower than a certain threshold, the user does not feed back. Feedback load reduction is thus achieved. For a given number of clusters, the sum rate loss using the cluster-based feedback scheme is investigated. Then the minimum number of clusters given a maximum tolerable sum rate loss is derived. Through simulations, it is shown that, when the number of users is large, full multiuser diversity can be achieved by the proposed feedback scheme, which is more efficient than the conventional schemes.
Typed Operational Semantics for Dependent Record Types
Venue: arXiv cs.LO 2011
Year: 2011

Typed operational semantics is a method developed by H. Goguen to prove meta-theoretic properties of type systems. This paper studies the metatheory of a type system with dependent record types, using the approach of typed operational semantics. In particular, the metatheoretical properties we have proved include strong normalisation, Church-Rosser and subject reduction.
On the capabilities of grammars, automata, and transducers controlled by monoids
Venue: arXiv cs.FL 2011
Year: 2011

During the last decades, classical models in language theory have been extended by control mechanisms defined by monoids. We study which monoids cause the extensions of context-free grammars, finite automata, or finite state transducers to exceed the capacity of the original model. Furthermore, we investigate when, in the extended automata model, the nondeterministic variant differs from the deterministic one in capacity. We show that all these conditions are in fact equivalent and present an algebraic characterization. In particular, the open question of whether every language generated by a valence grammar over a finite monoid is context-free is provided with a positive answer.
Finding Shortest Path for Developed Cognitive Map Using Medial Axis
Venue: arXiv cs.AI 2011
Year: 2011

this paper presents an enhancement of the medial axis algorithm to be used for finding the optimal shortest path for developed cognitive map. The cognitive map has been developed, based on the architectural blueprint maps. The idea for using the medial-axis is to find main path central pixels; each center pixel represents the center distance between two side boarder pixels. The need for these pixels in the algorithm comes from the need of building a network of nodes for the path, where each node represents a turning in the real world (left, right, critical left, critical right...). The algorithm also ignores from finding the center pixels paths that are too small for intelligent robot navigation. The Idea of this algorithm is to find the possible shortest path between start and end points. The goal of this research is to extract a simple, robust representation of the shape of the cognitive map together with the optimal shortest path between start and end points. The intelligent robot will use this algorithm in order to decrease the time that is needed for sweeping the targeted building.
Self-Stabilization, Byzantine Containment, and Maximizable Metrics: Necessary Conditions
Venue: arXiv cs.DC 2011
Year: 2011

Self-stabilization is a versatile approach to fault-tolerance since it permits a distributed system to recover from any transient fault that arbitrarily corrupts the contents of all memories in the system. Byzantine tolerance is an attractive feature of distributed systems that permits to cope with arbitrary malicious behaviors. We consider the well known problem of constructing a maximum metric tree in this context. Combining these two properties leads to some impossibility results. In this paper, we provide two necessary conditions to construct maximum metric tree in presence of transients and (permanent) Byzantine faults.
Incremental dimension reduction of tensors with random index
Venue: arXiv cs.DS 2011
Year: 2011

We present an incremental, scalable and efficient dimension reduction technique for tensors that is based on sparse random linear coding. Data is stored in a compactified representation with fixed size, which makes memory requirements low and predictable. Component encoding and decoding are performed on-line without computationally expensive re-analysis of the data set. The range of tensor indices can be extended dynamically without modifying the component representation. This idea originates from a mathematical model of semantic memory and a method known as random indexing in natural language processing. We generalize the random-indexing algorithm to tensors and present signal-to-noise-ratio simulations for representations of vectors and matrices. We present also a mathematical analysis of the approximate orthogonality of high-dimensional ternary vectors, which is a property that underpins this and other similar random-coding approaches to dimension reduction. To further demonstrate the properties of random indexing we present results of a synonym identification task. The method presented here has some similarities with random projection and Tucker decomposition, but it performs well at high dimensionality only (n>10^3). Random indexing is useful for a range of complex practical problems, e.g., in natural language processing, data mining, pattern recognition, event detection, graph searching and search engines. Prototype software is provided. It supports encoding and decoding of tensors of order >= 1 in a unified framework, i.e., vectors, matrices and higher order tensors.
Energy-Optimal Scheduling in Low Duty Cycle Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

Energy consumption of a wireless sensor node mainly depends on the amount of time the node spends in each of the high power active (e.g., transmit, receive) and low power sleep modes. It has been well established that in order to prolong node's lifetime the duty-cycle of the node should be low. However, low power sleep modes usually have low current draw but high energy cost while switching to the active mode with a higher current draw. In this work, we investigate a MaxWeightlike opportunistic sleep-active scheduling algorithm that takes into account time- varying channel and traffic conditions. We show that our algorithm is energy optimal in the sense that the proposed ESS algorithm can achieve an energy consumption which is arbitrarily close to the global minimum solution. Simulation studies are provided to confirm the theoretical results.
Learning Equilibrium Play for Stochastic Parallel Gaussian Interference Channels
Venue: arXiv cs.GT 2011
Year: 2011

Distributed power control for parallel Gaussian interference channels recently draws great interests. However, all existing works only studied this problem under deterministic communication channels and required certain perfect information to carry out their proposed algorithms. In this paper, we study this problem for stochastic parallel Gaussian interference channels. In particular, we take into account the randomness of the communication environment and the estimation errors of the desired information, and thus formulate a stochastic noncooperative power control game. We then propose a stochastic distributed learning algorithm SDLA-I to help communication pairs learn the Nash equilibrium. A careful convergence analysis on SDLA-I is provided based on stochastic approximation theory and projected dynamic systems approach. We further propose another learning algorithm SDLA-II by including a simple iterate averaging idea into SDLA-I to improve algorithmic convergence performance. Numerical results are also presented to demonstrate the performance of our algorithms and theoretical results.
Framework for Clique-based Fusion of Graph Streams in Multi-function System Testing
Venue: arXiv cs.SE 2011
Year: 2011

The paper describes a framework for multi-function system testing. Multi-function system testing is considered as fusion (or revelation) of clique-like structures. The following sets are considered: (i) subsystems (system parts or units / components / modules), (ii) system functions and a subset of system components for each system function, and (iii) function clusters (some groups of system functions which are used jointly). Test procedures (as units testing) are used for each subsystem. The procedures lead to an ordinal result (states, colors) for each component, e.g., [1,2,3,4] (where 1 corresponds to 'out of service', 2 corresponds to 'major faults', 3 corresponds to 'minor faults', 4 corresponds to 'trouble free service'). Thus, for each system function a graph over corresponding system components is examined while taking into account ordinal estimates/colors of the components. Further, an integrated graph (i.e., colored graph) for each function cluster is considered (this graph integrates the graphs for corresponding system functions). For the integrated graph (for each function cluster) structure revelation problems are under examination (revelation of some subgraphs which can lead to system faults): (1) revelation of clique and quasi-clique (by vertices at level 1, 2, etc.; by edges/interconnection existence) and (2) dynamical problems (when vertex colors are functions of time) are studied as well: existence of a time interval when clique or quasi-clique can exist. Numerical examples illustrate the approach and problems.
Multibeam Satellite Frequency/Time Duality Study and Capacity Optimization
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we investigate two new candidate transmission schemes, Non-Orthogonal Frequency Reuse (NOFR) and Beam-Hoping (BH). They operate in different domains (frequency and time/space, respectively), and we want to know which domain shows overall best performance. We propose a novel formulation of the Signal-to-Interference plus Noise Ratio (SINR) which allows us to prove the frequency/time duality of these schemes. Further, we propose two novel capacity optimization approaches assuming per-beam SINR constraints in order to use the satellite resources (e.g. power and bandwidth) more efficiently. Moreover, we develop a general methodology to include technological constraints due to realistic implementations, and obtain the main factors that prevent the two technologies dual of each other in practice, and formulate the technological gap between them. The Shannon capacity (upper bound) and current state-of-the-art coding and modulations are analyzed in order to quantify the gap and to evaluate the performance of the two candidate schemes. Simulation results show significant improvements in terms of power gain, spectral efficiency and traffic matching ratio when comparing with conventional systems, which are designed based on uniform bandwidth and power allocation. The results also show that BH system turns out to show a less complex design and performs better than NOFR system specially for non-real time services.