OpenRaiser/Intern-Atlas huggingface dataset:
A++ Random Access for Two-way Relaying in Wireless Networks
Venue: arXiv cs.IT 2012
Year: 2012

Two-way relaying can significantly improve performance of next generation wireless networks. However, due to its dependence on multi-node cooperation and transmission coordination, applying this technique to a wireless network in an effective and scalable manner poses a challenging problem. To tackle this problem without relying on complicated scheduling or network optimization algorithms, we propose a scalable random access scheme that takes measures in both the physical layer and the medium access control layer. Specifically, we propose a two-way relaying technique that supports fully asynchronous transmission and is modulation-independent. It also assumes no priori knowledge of channel conditions. On the top of this new physical layer technique, a random access MAC protocol is designed to dynamically form two-way relaying cooperation in a wireless network. To evaluate the scalable random access scheme, both theoretical analysis and simulations are carried out. Performance results illustrate that our scheme has achieved the goal of scalable two-way relaying in a wireless network and significantly outperforms CSMA/CA protocol.
Touchalytics: On the Applicability of Touchscreen Input as a Behavioral Biometric for Continuous Authentication
Venue: arXiv cs.CR 2012
Year: 2012

We investigate whether a classifier can continuously authenticate users based on the way they interact with the touchscreen of a smart phone. We propose a set of 30 behavioral touch features that can be extracted from raw touchscreen logs and demonstrate that different users populate distinct subspaces of this feature space. In a systematic experiment designed to test how this behavioral pattern exhibits consistency over time, we collected touch data from users interacting with a smart phone using basic navigation maneuvers, i.e., up-down and left-right scrolling. We propose a classification framework that learns the touch behavior of a user during an enrollment phase and is able to accept or reject the current user by monitoring interaction with the touch screen. The classifier achieves a median equal error rate of 0% for intra-session authentication, 2%-3% for inter-session authentication and below 4% when the authentication test was carried out one week after the enrollment phase. While our experimental findings disqualify this method as a standalone authentication mechanism for long-term authentication, it could be implemented as a means to extend screen-lock time or as a part of a multi-modal biometric authentication system.
Off-line test selection with test purposes for non-deterministic timed automata
Venue: arXiv cs.FL 2012
Year: 2012

This article proposes novel off-line test generation techniques from non-deterministic timed automata with inputs and outputs (TAIOs) in the formal framework of the tioco conformance theory. In this context, a first problem is the determinization of TAIOs, which is necessary to foresee next enabled actions after an observable trace, but is in general impossible because not all timed automata are determinizable. This problem is solved thanks to an approximate determinization using a game approach. The algorithm performs an io-abstraction which preserves the tioco conformance relation and thus guarantees the soundness of generated test cases. A second problem is the selection of test cases from a TAIO specification. The selection here relies on a precise description of timed behaviors to be tested which is carried out by expressive test purposes modeled by a generalization of TAIOs. Finally, an algorithm is described which generates test cases in the form of TAIOs equipped with verdicts, using a symbolic co-reachability analysis guided by the test purpose. Properties of test cases are then analyzed with respect to the precision of the approximate determinization: when determinization is exact, which is the case on known determinizable classes, in addition to soundness, properties characterizing the adequacy of test cases verdicts are also guaranteed.
On Randomness of Goldbach Sequences
Venue: arXiv cs.CR 2012
Year: 2012

We consider the use of Goldbach numbers as random sequences. The randomness is analyzed in terms of the autocorrelation function of the sequence of number of partitions. The distinct representations of an even number n as the sum of two primes is a local maximum for multiples of the product of the consecutive smallest primes less than the number. Specific partitions, which we call Goldbach ellipses, are examined. It is shown that such ellipse sequences also have excellent randomness property.
Sum of squares representation for the Böttcher-Wenzel biquadratic form
Venue: arXiv cs.DM 2012
Year: 2012

We find the minimum scale factor, for which the nonnegative Böttcher-Wenzel biquadratic form becomes a sum of squares (sos). To this we give the primal and dual solutions for the underlying semide finite program. Moreover, for special matrix classes (tridiagonal, backward tridiagonal and cyclic Hankel matrices) we show that the above form is sos. Finally, we conjecture sos representability for Toeplitz matrices.
Counting (k,l)-sumsets in groups of prime order
Venue: arXiv cs.DM 2012
Year: 2012

A subset $A$ of a group $G$ is called $(k, l)$-{\it sumset}, if $A= kB-lB$ for some $B\subseteq G$, where $kB-lB={x_1+...+x_k-x_{k+1}-...-x_{k+l} : x_1,..., x_{k+l}\in B}.$ Upper and lower bounds for the number $(k, l)$-sumsets in groups of prime order are provided.
Profit Incentive In A Secondary Spectrum Market: A Contract Design Approach
Venue: arXiv cs.CE 2012
Year: 2012

In this paper we formulate a contract design problem where a primary license holder wishes to profit from its excess spectrum capacity by selling it to potential secondary users/buyers. It needs to determine how to optimally price the excess spectrum so as to maximize its profit, knowing that this excess capacity is stochastic in nature, does not come with exclusive access, and cannot provide deterministic service guarantees to a buyer. At the same time, buyers are of different {\em types}, characterized by different communication needs, tolerance for the channel uncertainty, and so on, all of which a buyer's private information. The license holder must then try to design different contracts catered to different types of buyers in order to maximize its profit. We address this problem by adopting as a reference a traditional spectrum market where the buyer can purchase exclusive access with fixed/deterministic guarantees. We fully characterize the optimal solution in the cases where there is a single buyer type, and when multiple types of buyers share the same, known channel condition as a result of the primary user activity. In the most general case we construct an algorithm that generates a set of contracts in a computationally efficient manner, and show that this set is optimal when the buyer types satisfy a monotonicity condition.
A Robust Relay Placement Framework for 60GHz mmWave Wireless Personal Area Networks
Venue: arXiv cs.NI 2012
Year: 2012

Multimedia streaming applications with stringent QoS requirements in 60GHz mmWave wireless personal area networks (WPANs) demand high rate and low latency data transfer as well as low service disruption. In this paper, we consider the problem of robust relay placement in 60GHz WPANs. Relays forward traffic from transmitter devices to receiver devices facilitating i) the primary communication path for non-line-of-sight (NLOS) transceiver pairs, and ii) secondary (backup) communication path for line-of-sight (LOS) transceiver pairs. We formulate the robust minimum relay placement problem and the robust maximum utility relay placement problem with the objective to minimize the number of relays deployed and maximize the network utility, respectively. Efficient algorithms are developed to solve both problems and have been shown to incur less service disruption in presence of moving subjects that may block the LOS paths in the environment.
Achieving Net Feedback Gain in the Butterfly Network with a Full-Duplex Bidirectional Relay
Venue: arXiv cs.IT 2012
Year: 2012

A symmetric butterfly network (BFN) with a full-duplex relay operating in a bi-directional fashion for feedback is considered. This network is relevant for a variety of wireless networks, including cellular systems dealing with cell-edge users. Upper bounds on the capacity region of the general memoryless BFN with feedback are derived based on cut-set and cooperation arguments and then specialized to the linear deterministic BFN with really-source feedback. It is shown that the upper bounds are achievable using combinations of the compute-forward strategy and the classical decode-and-forward strategy, thus fully characterizing the capacity region. It is shown that net rate gains are possible in certain parameter regimes.
RapidRAID: Pipelined Erasure Codes for Fast Data Archival in Distributed Storage Systems
Venue: arXiv cs.DC 2012
Year: 2012

To achieve reliability in distributed storage systems, data has usually been replicated across different nodes. However the increasing volume of data to be stored has motivated the introduction of erasure codes, a storage efficient alternative to replication, particularly suited for archival in data centers, where old datasets (rarely accessed) can be erasure encoded, while replicas are maintained only for the latest data. Many recent works consider the design of new storage-centric erasure codes for improved repairability. In contrast, this paper addresses the migration from replication to encoding: traditionally erasure coding is an atomic operation in that a single node with the whole object encodes and uploads all the encoded pieces. Although large datasets can be concurrently archived by distributing individual object encodings among different nodes, the network and computing capacity of individual nodes constrain the archival process due to such atomicity. We propose a new pipelined coding strategy that distributes the network and computing load of single-object encodings among different nodes, which also speeds up multiple object archival. We further present RapidRAID codes, an explicit family of pipelined erasure codes which provides fast archival without compromising either data reliability or storage overheads. Finally, we provide a real implementation of RapidRAID codes and benchmark its performance using both a cluster of 50 nodes and a set of Amazon EC2 instances. Experiments show that RapidRAID codes reduce a single object's coding time by up to 90%, while when multiple objects are encoded concurrently, the reduction is up to 20%.
Technology Use in the Virtual R&D Teams
Venue: arXiv cs.CY 2012
Year: 2012

Problem statement: Although, literature proves the importance of the technology role in the effectiveness of virtual Research and Development (R&D) teams for new product development. However, the factors that make technology construct in a virtual R&D team are still ambiguous. The manager of virtual R&D teams for new product development does not know which type of technology should be used. Approach: To address the gap and answer the question, the study presents a set of factors that make a technology construct. The proposed construct modified by finding of the field survey (N = 240). We empirically examine the relationship between construct and its factors by employing the Structural Equation Modeling (SEM). A measurement model built base on the 19 preliminary factors that extracted from literature review. The result shows 10 factors out of 19 factors maintaining to make technology construct. Results: These 10 technology factors can be grouped into two constructs namely Web base communication and Web base data sharing. The findings can help new product development managers of enterprises to concentrate in the main factors for leading an effective virtual R&D team. In addition, it provides a guideline for software developers as well. Conclusion: The second and third generation technologies are now more suitable for developing new products through virtual R&D teams.
Impact of fault prediction on checkpointing strategies
Venue: arXiv cs.DC 2012
Year: 2012

This paper deals with the impact of fault prediction techniques on checkpointing strategies. We extend the classical analysis of Young and Daly in the presence of a fault prediction system, which is characterized by its recall and its precision, and which provides either exact or window-based time predictions. We succeed in deriving the optimal value of the checkpointing period (thereby minimizing the waste of resource usage due to checkpoint overhead) in all scenarios. These results allow to analytically assess the key parameters that impact the performance of fault predictors at very large scale. In addition, the results of this analytical evaluation are nicely corroborated by a comprehensive set of simulations, thereby demonstrating the validity of the model and the accuracy of the results.
Two Embedding Theorems for Data with Equivalences under Finite Group Action
Venue: arXiv cs.DS 2012
Year: 2012

There is recent interest in compressing data sets for non-sequential settings, where lack of obvious orderings on their data space, require notions of data equivalences to be considered. For example, Varshney & Goyal (DCC, 2006) considered multiset equivalences, while Choi & Szpankowski (IEEE Trans. IT, 2012) considered isomorphic equivalences in graphs. Here equivalences are considered under a relatively broad framework - finite-dimensional, non-sequential data spaces with equivalences under group action, for which analogues of two well-studied embedding theorems are derived: the Whitney embedding theorem and the Johnson-Lindenstrauss lemma. Only the canonical data points need to be carefully embedded, each such point representing a set of data points equivalent under group action. Two-step embeddings are considered. First, a group invariant is applied to account for equivalences, and then secondly, a linear embedding takes it down to low-dimensions. Our results require hypotheses on discriminability of the applied invariant, such notions related to seperating invariants (Dufresne, 2008), and completeness in pattern recognition (Kakarala, 1992). In the latter theorem, the embedding complexity depends on the size of the canonical part, which may be significantly smaller than the whole data set, up to a factor equal to the size the group.
Towards a Book Publishers Citation Reports. First approach using the Book Citation Index
Venue: arXiv cs.DL 2012
Year: 2012

The absence of books and book chapters in the Web of Science Citation Indexes (SCI, SSCI and A&HCI) has always been considered an important flaw but the Thomson Reuters 'Book Citation Index' database was finally available in October of 2010 indexing 29,618 books and 379,082 book chapters. The Book Citation Index opens a new window of opportunities for analyzing these fields from a bibliometric point of view. The main objective of this article is to analyze different impact indicators referred to the scientific publishers included in the Book Citation Index for the Social Sciences and Humanities fields during 2006-2011. This way we construct what we have called the 'Book Publishers Citation Reports'. For this, we present a total of 19 rankings according to the different disciplines in Humanities & Arts and Social Sciences & Law with six indicators for scientific publishers
Optimizing Bi-directional Low-Latency Communication in Named Data Networking
Venue: arXiv cs.NI 2012
Year: 2012

Content-Centric Networking (CCN) is a concept being considered as a potential future alternative to, or replacement for, today's Internet IP-style packet-switched host-centric networking. One factor making CCN attractive is its focus on content distribution, which dominates current Internet traffic and which is arguably not well-served by IP. Named Data Networking (NDN) is a prominent example of CCN. It is also one of several on-going research efforts aiming to design and develop a full-blown candidate future Internet architecture. Although NDN's primary motivation is content distribution, it is envisioned to support other types of traffic, such as conferencing (audio, video) as well as more historical applications, such as remote login. However, it is unclear how suitable NDN is for applications that are not obviously content-centric. In this paper, we explore NDN in the context of a class of applications that involve low- latency bidirectional communication. Specifically, we propose a few architectural amendments to NDN that provide significantly better throughput and lower latency for this class of applications. The proposed approach is validated via both simulations and testbed experiments.
Predicate Generation for Learning-Based Quantifier-Free Loop Invariant Inference
Venue: arXiv cs.LO 2012
Year: 2012

We address the predicate generation problem in the context of loop invariant inference. Motivated by the interpolation-based abstraction refinement technique, we apply the interpolation theorem to synthesize predicates implicitly implied by program texts. Our technique is able to improve the effectiveness and efficiency of the learning-based loop invariant inference algorithm in [14]. We report experiment results of examples from Linux, SPEC2000, and Tar utility.
A Simple Quantifier-free Formula of Positive Semidefinite Cyclic Ternary Quartic Forms
Venue: arXiv cs.LO 2012
Year: 2012

Quantifier elimination of positive semidefinite cyclic ternary quartic forms is studied in this paper. We solve the problem by the theory of complete discrimination systems, function \RealTriangularize in Maple15 and the so-called Criterions on Equality of Symmetric Inequalities method. The equivalent simple quantifier-free formula is proposed and is difficult to obtain automatically by previous methods or quantifier elimination tools.
The Dynamics of Health Behavior Sentiments on a Large Online Social Network
Venue: arXiv cs.SI 2012
Year: 2012

Modifiable health behaviors, a leading cause of illness and death in many countries, are often driven by individual beliefs and sentiments about health and disease. Individual behaviors affecting health outcomes are increasingly modulated by social networks, for example through the associations of like-minded individuals - homophily - or through peer influence effects. Using a statistical approach to measure the individual temporal effects of a large number of variables pertaining to social network statistics, we investigate the spread of a health sentiment towards a new vaccine on Twitter, a large online social network. We find that the effects of neighborhood size and exposure intensity are qualitatively very different depending on the type of sentiment. Generally, we find that larger numbers of opinionated neighbors inhibit the expression of sentiments. We also find that exposure to negative sentiment is contagious - by which we merely mean predictive of future negative sentiment expression - while exposure to positive sentiments is generally not. In fact, exposure to positive sentiments can even predict increased negative sentiment expression. Our results suggest that the effects of peer influence and social contagion on the dynamics of behavioral spread on social networks are strongly content-dependent.
RIP Analysis of Modulated Sampling Schemes for Recovering Spectrally Sparse Signals
Venue: arXiv cs.IT 2012
Year: 2012

In this work, we analyze modulated sampling schemes, such as the Nyquist Folding Receiver, which are highly efficient, readily implementable, non-uniform sampling schemes that allows for the blind estimation of a narrow-band signal's spectral content and location in a wide-band environment. This non-uniform sampling, achieved by narrow-band modulation of the RF instantaneous sample rate, results in a frequency domain point spread function that is between the extremes obtained by uniform sampling and totally random sampling. As a result, while still preserving structured aliasing, the modulated sampling scheme is also useful in a compressive sensing (CS) setting. We estimate restricted isometry property (RIP) constants for CS matrices induced by such modulated sampling schemes and use those estimates to determine the amount of sparsity needed for signal recovery. This is followed by a demonstration and analysis of Orthogonal Matching Pursuit's ability to reconstruct signals from noisy non-uniform samples.
Keyword-aware Optimal Route Search
Venue: arXiv cs.DB 2012
Year: 2012

Identifying a preferable route is an important problem that finds applications in map services. When a user plans a trip within a city, the user may want to find "a most popular route such that it passes by shopping mall, restaurant, and pub, and the travel time to and from his hotel is within 4 hours." However, none of the algorithms in the existing work on route planning can be used to answer such queries. Motivated by this, we define the problem of keyword-aware optimal route query, denoted by KOR, which is to find an optimal route such that it covers a set of user-specified keywords, a specified budget constraint is satisfied, and an objective score of the route is optimal. The problem of answering KOR queries is NP-hard. We devise an approximation algorithm OSScaling with provable approximation bounds. Based on this algorithm, another more efficient approximation algorithm BucketBound is proposed. We also design a greedy approximation algorithm. Results of empirical studies show that all the proposed algorithms are capable of answering KOR queries efficiently, while the BucketBound and Greedy algorithms run faster. The empirical studies also offer insight into the accuracy of the proposed algorithms.
The Complexity of Social Coordination
Venue: arXiv cs.DB 2012
Year: 2012

Coordination is a challenging everyday task; just think of the last time you organized a party or a meeting involving several people. As a growing part of our social and professional life goes online, an opportunity for an improved coordination process arises. Recently, Gupta et al. proposed entangled queries as a declarative abstraction for data-driven coordination, where the difficulty of the coordination task is shifted from the user to the database. Unfortunately, evaluating entangled queries is very hard, and thus previous work considered only a restricted class of queries that satisfy safety (the coordination partners are fixed) and uniqueness (all queries need to be satisfied). In this paper we significantly extend the class of feasible entangled queries beyond uniqueness and safety. First, we show that we can simply drop uniqueness and still efficiently evaluate a set of safe entangled queries. Second, we show that as long as all users coordinate on the same set of attributes, we can give an efficient algorithm for coordination even if the set of queries does not satisfy safety. In an experimental evaluation we show that our algorithms are feasible for a wide spectrum of coordination scenarios.