OpenRaiser/Intern-Atlas huggingface dataset:
Real Time Position Location & Tracking (PL&T) using Prediction Filter and Integrated Zone Finding in OFDM Channel
Venue: arXiv cs.NI 2012
Year: 2012

The nature of pre-determined and on-demand mobile network fabrics can be exploited for real time Position Location and Tracking (PL&T) of radios and sensors (nodes) for Global Positioning System (GPS) denied or GPS-free systems. This issue is addressed by a novel system of integrated zone finding and triangulation method for determining the PL&T of nodes when mobile network fabrics are employed based on using directional antennas for radio communications. Each mobile node is switched dynamically between being a reference and a target node in PL&T operation to improve the PL&T accuracy of a target node. This paper presents the Baseline PL&T with predictive Kalman filter and Integrated Zone based PL&T algorithm design that integrates zone finding and triangulation method. The performance of the proposed algorithm is analysed using Interleaving-KV sample coding & error correction in Rayleigh and Rician channel using Orthogonal Frequency Division Multiplexing (OFDM) system under the severe multipath fading.
Automation of Mobile Pick and Place Robotic System for Small Food Industry
Venue: arXiv cs.ET 2012
Year: 2012

The use of robotics in food industry is becoming more popular in recent years. The trend seems to continue as long as the robotics technology meets diverse and challenging needs of the food producers. Rapid developments in digital computers and control systems technologies have significant impact in robotics like any other engineering fields. By utilizing new hardware and software tools, design of these complex systems that need strong integration of distinct disciplines is no longer difficult compared to the past. Therefore, the purpose of this paper is to design and implement a micro-controller based on reliable and high performance robotic system for food / biscuit manufacturing line. We propose a design of a vehicle. The robot is capable of picking unbaked biscuits tray and places them into furnace and then after baking it picks the biscuits tray from the furnace. A special gripper is designed to pick and place the biscuits tray with flexibility.
On the Hamming Distance between base-n representations of whole numbers
Venue: arXiv cs.DM 2012
Year: 2012

We first introduce the Hamming distance between two strings. Then, we apply this concept to the representations of whole numbers in base n for all positive integers n > 2. We claim that a simple formula exists for the sum of all Hamming distances between pairs of consec- utive integers from 1 to m, which we will derive. We also state and prove other interesting results concerning the aforementioned topic.
On the Boundaries of Trust and Security in Computing and Communications Systems
Venue: arXiv cs.CR 2012
Year: 2012

This article analyzes trust and security in computing and communications systems. While in human-life, trust usually has some kind of commonly understood meaning, in the realm of computing and communications systems, it could be interpreted differently in different environments and settings. On the other hand, security is about making sure that the participating entities are legitimate in a communication event or incident so that the core requirements of privacy, integrity, and authenticity are maintained. This notion is also true for our human life, even for example entering a house needs legitimacy of a person. Some boundary lines preserve the security; otherwise an unwanted access is called a 'security breach'. The intent of this article is to compare and discuss these two terms with our societal behavior and understanding amongst entities. To illustrate these issues especially in computing and communications world, some of the innovating and recent technologies are discussed which demand trust and security within their core operational structures. Alongside presenting generally established ideas, some critical points are mentioned that may be sometimes debatable within the research community.
A Novel Bluetooth Man-In-The-Middle Attack Based On SSP using OOB Association model
Venue: arXiv cs.CR 2012
Year: 2012

As an interconnection technology, Bluetooth has to address all traditional security problems, well known from the distributed networks. Moreover, as Bluetooth networks are formed by the radio links, there are also additional security aspects whose impact is yet not well understood. In this paper, we propose a novel Man-In-The-Middle (MITM) attack against Bluetooth enabled mobile phone that support Simple Secure Pairing(SSP). From the literature it was proved that the SSP association models such as Numeric comparison, Just works and passkey Entry are not more secure. Here we propose the Out Of Band (OOB) channeling with enhanced security than the previous methods.
A Local Approach for Identifying Clusters in Networks
Venue: arXiv cs.SI 2012
Year: 2012

Graph clustering is a fundamental problem that has been extensively studied both in theory and practice. The problem has been defined in several ways in literature and most of them have been proven to be NP-Hard. Due to their high practical relevancy, several heuristics for graph clustering have been introduced which constitute a central tool for coping with NP-completeness, and are used in applications of clustering ranging from computer vision, to data analysis, to learning. There exist many methodologies for this problem, however most of them are global in nature and are unlikely to scale well for very large networks. In this paper, we propose two scalable local approaches for identifying the clusters in any network. We further extend one of these approaches for discovering the overlapping clusters in these networks. Some experimentation results obtained for the proposed approaches are also presented.
Computational interpretation of classical logic with explicit structural rules
Venue: arXiv cs.LO 2012
Year: 2012

We present a calculus providing a Curry-Howard correspondence to classical logic represented in the sequent calculus with explicit structural rules, namely weakening and contraction. These structural rules introduce explicit erasure and duplication of terms, respectively. We present a type system for which we prove the type-preservation under reduction. A mutual relation with classical calculus featuring implicit structural rules has been studied in detail. From this analysis we derive strong normalisation property.
Very Short Literature Survey From Supervised Learning To Surrogate Modeling
Venue: arXiv cs.LG 2012
Year: 2012

The past century was era of linear systems. Either systems (especially industrial ones) were simple (quasi)linear or linear approximations were accurate enough. In addition, just at the ending decades of the century profusion of computing devices were available, before then due to lack of computational resources it was not easy to evaluate available nonlinear system studies. At the moment both these two conditions changed, systems are highly complex and also pervasive amount of computation strength is cheap and easy to achieve. For recent era, a new branch of supervised learning well known as surrogate modeling (meta-modeling, surface modeling) has been devised which aimed at answering new needs of modeling realm. This short literature survey is on to introduce surrogate modeling to whom is familiar with the concepts of supervised learning. Necessity, challenges and visions of the topic are considered.
Isomorphism of graph classes related to the circular-ones property
Venue: arXiv cs.DS 2012
Year: 2012

We give a linear-time algorithm that checks for isomorphism between two 0-1 matrices that obey the circular-ones property. This algorithm leads to linear-time isomorphism algorithms for related graph classes, including Helly circular-arc graphs, Γ-circular-arc graphs, proper circular-arc graphs and convex-round graphs.
On a New Method of Storing a Variable Size Array
Venue: arXiv cs.DS 2012
Year: 2012

This paper introduces a new data structure, log_vector, with the following properties: constant time random access to individual elements; constant time element addition to the end; constant time element removal from the end; constant time empty data structure creation; amortized constant space per individual elements; constant additional space used.
Achieving Congestion Diversity in Multi-hop Wireless Mesh Networks
Venue: arXiv cs.NI 2012
Year: 2012

This paper reports on the first systematic study of congestion-aware routing algorithms for wireless mesh networks to achieve an improved end-end delay performance. In particular, we compare 802.11 compatible implementations of a set of congestion-aware routing protocols against our implementation of state of the art shortest path routing protocol (SRCR). We implement congestion-aware routing algorithms Backpressure (BP), Enhanced-Backpressure (E-BP) adapted from [1], [2] suitably adjusted for 802.11 implementation. We then propose and implement Congestion Diversity Protocol (CDP) adapted from [3] recognizing the limitations of BP and E-BP for 802.11-based wireless networks. SRCR solely utilizes link qualities, while BP relies on queue differential to route packets. CDP and E-BP rely on distance metrics which take into account queue backlogs and link qualities in the network. E-BP computes its metric by summing the ETX and queue differential, while CDP determines its metric by calculating the least draining time to the destination. Our small testbed consisting of twelve 802.11g nodes enables us to empirically compare the performance of congestion-aware routing protocols (BP, E-BP and CDP) against benchmark SRCR. For medium to high load UDP traffic, we observe that CDP exhibits significant improvement with respect to both end-end delay and throughput over other protocols with no loss of performance for TCP traffic. Backpressure-based routing algorithms (BP and E-BP) show poorer performance for UDP and TCP traffic. Finally, we carefully study the effects of the modular approach to congestion-aware routing design in which the MAC layer is left intact
Multi-hop Analog Network Coding: An Amplify-and-Forward Approach
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we study the performance of an amplify-and-forward (AF) based analog network coding (ANC) relay scheme in a multi-hop wireless network under individual power constraints. In the first part, a unicast scenario is considered. The problem of finding the maximum achievable rate is formulated as an optimization problem. Rather than solving this non-concave maximization problem, we derive upper and lower bounds for the optimal rate. A cut-set like upper bound is obtained in a closed form for a layered relay network. A pseudo-optimal AF scheme is developed for a two-hop parallel network, which is different from the conventional scheme with all amplification gains chosen as the maximum possible values. The conditions under which either the novel scheme or the conventional one achieves a rate within half a bit of the upper bound are found. Then we provide an AF-based multi-hop ANC scheme with the two schemes for a layered relay network. It is demonstrated that the lower bound of the optimal rate can asymptotically achieve the upper bound when the network is in the generalized high-SNR regime. In the second part, the optimal rate region for a two-hop multiple access channel (MAC) via AF relays is investigated. In a similar manner, we first derive an outer bound for it and then focus on designing low complexity AF-based ANC schemes for different scenarios. Several examples are given and the numerical results indicate that the achievable rate region of the ANC schemes can perform close to the outer bound.
Work function algorithm can forget history without losing competitiveness
Venue: arXiv cs.DS 2012
Year: 2012

The Work Function Algorithm is the most effective deterministic on-line algorithm for the k-server problem. Koutsoupias and Papadimitriou proved WFA is (2k-1) competitive. However the best known implementation of WFA requires time O(i^2) to process request r_i and this makes WFA impractical for long sequences of requests. The O(i^2) time is spent to compute the work function on the whole history of past requests. In order to make constant the time to process a request, Rudec and Menger proposed to restrict the history to a moving window of fixed size. However WFA restricted to a moving window loses its competitiveness. Here we give a condition that allows WFA to forget the whole previous history and restart from scratch without losing competitiveness. Moreover for most of the metric spaces of practical interest (finite or bounded spaces) there is a constant bound on the length of the history before the condition is verified and this makes O(1) the time to process each request.
Advanced Programming Platform for efficient use of Data Parallel Hardware
Venue: arXiv cs.DC 2012
Year: 2012

Graphics processing units (GPU) had evolved from a specialized hardware capable to render high quality graphics in games to a commodity hardware for effective processing blocks of data in a parallel schema. This evolution is particularly interesting for scientific groups, which traditionally use mainly CPU as a work horse, and now can profit of the arrival of GPU hardware to HPC clusters. This new GPU hardware promises a boost in peak performance, but it is not trivial to use. In this article a programming platform designed to promote a direct use of this specialized hardware is presented. This platform includes a visual editor of parallel data flows and it is oriented to the execution in distributed clusters with GPUs. Examples of application in two characteristic problems, Fast Fourier Transform and Image Compression, are also shown.
CUDA implementation of Wagener's 2D convex hull PRAM algorithm
Venue: arXiv cs.DC 2012
Year: 2012

This paper describes a CUDA implementation of Wagener's PRAM convex hull algorithm in two dimensions. It is presented in Knuth's literate programming style.
USFD2: Annotating Temporal Expresions and TLINKs for TempEval-2
Venue: arXiv cs.CL 2012
Year: 2012

We describe the University of Sheffield system used in the TempEval-2 challenge, USFD2. The challenge requires the automatic identification of temporal entities and relations in text. USFD2 identifies and anchors temporal expressions, and also attempts two of the four temporal relation assignment tasks. A rule-based system picks out and anchors temporal expressions, and a maximum entropy classifier assigns temporal link labels, based on features that include descriptions of associated temporal signal words. USFD2 identified temporal expressions successfully, and correctly classified their type in 90% of cases. Determining the relation between an event and time expression in the same sentence was performed at 63% accuracy, the second highest score in this part of the challenge.
A Data Driven Approach to Query Expansion in Question Answering
Venue: arXiv cs.CL 2012
Year: 2012

Automated answering of natural language questions is an interesting and useful problem to solve. Question answering (QA) systems often perform information retrieval at an initial stage. Information retrieval (IR) performance, provided by engines such as Lucene, places a bound on overall system performance. For example, no answer bearing documents are retrieved at low ranks for almost 40% of questions. In this paper, answer texts from previous QA evaluations held as part of the Text REtrieval Conferences (TREC) are paired with queries and analysed in an attempt to identify performance-enhancing words. These words are then used to evaluate the performance of a query expansion method. Data driven extension words were found to help in over 70% of difficult questions. These words can be used to improve and evaluate query expansion methods. Simple blind relevance feedback (RF) was correctly predicted as unlikely to help overall performance, and an possible explanation is provided for its low value in IR for QA.
Parameterized Proof Complexity and W[1]
Venue: arXiv cs.LO 2012
Year: 2012

We initiate a program of parameterized proof complexity that aims to provide evidence that FPT is different from W[1]. A similar program already exists for the classes W[2] and W[SAT]. We contrast these programs and prove upper and lower bounds for W[1]-parameterized Resolution.
Public-Key Cryptography Based on Modular Lattices
Venue: arXiv cs.CR 2012
Year: 2012

We present an approach to generalization of practical Identity-Based Encryption scheme of Boneh and Franklin. In particular we show how the protocol could be used on finite modular lattices and as a special case on vector spaces over finite field. The original proof of security for this protocol does not hold in this general algebraic structure, thus this is still a work in progress.
Finding Connected Components on Map-reduce in Logarithmic Rounds
Venue: arXiv cs.DS 2012
Year: 2012

Given a large graph G = (V,E) with millions of nodes and edges, how do we compute its connected components efficiently? Recent work addresses this problem in map-reduce, where a fundamental trade-off exists between the number of map-reduce rounds and the communication of each round. Denoting d the diameter of the graph, and n the number of nodes in the largest component, all prior map-reduce techniques either require d rounds, or require about n|V| + |E| communication per round. We propose two randomized map-reduce algorithms -- (i) Hash-Greater-To-Min, which provably requires at most 3log(n) rounds with high probability, and at most 2(|V| + |E|) communication per round, and (ii) Hash-to-Min, which has a worse theoretical complexity, but in practice completes in at most 2log(d) rounds and 3(|V| + |E|) communication per rounds. Our techniques for connected components can be applied to clustering as well. We propose a novel algorithm for agglomerative single linkage clustering in map-reduce. This is the first algorithm that can provably compute a clustering in at most O(log(n)) rounds, where n is the size of the largest cluster. We show the effectiveness of all our algorithms through detailed experiments on large synthetic as well as real-world datasets.
BlinkDB: Queries with Bounded Errors and Bounded Response Times on Very Large Data
Venue: arXiv cs.DB 2012
Year: 2012

In this paper, we present BlinkDB, a massively parallel, sampling-based approximate query engine for running ad-hoc, interactive SQL queries on large volumes of data. The key insight that BlinkDB builds on is that one can often make reasonable decisions in the absence of perfect answers. For example, reliably detecting a malfunctioning server using a distributed collection of system logs does not require analyzing every request processed by the system. Based on this insight, BlinkDB allows one to trade-off query accuracy for response time, enabling interactive queries over massive data by running queries on data samples and presenting results annotated with meaningful error bars. To achieve this, BlinkDB uses two key ideas that differentiate it from previous work in this area: (1) an adaptive optimization framework that builds and maintains a set of multi-dimensional, multi-resolution samples from original data over time, and (2) a dynamic sample selection strategy that selects an appropriately sized sample based on a query's accuracy and/or response time requirements. We have built an open-source version of BlinkDB and validated its effectiveness using the well-known TPC-H benchmark as well as a real-world analytic workload derived from Conviva Inc. Our experiments on a 100 node cluster show that BlinkDB can answer a wide range of queries from a real-world query trace on up to 17 TBs of data in less than 2 seconds (over 100\times faster than Hive), within an error of 2 - 10%.
Exploring Text Virality in Social Networks
Venue: arXiv cs.CL 2012
Year: 2012

This paper aims to shed some light on the concept of virality - especially in social networks - and to provide new insights on its structure. We argue that: (a) virality is a phenomenon strictly connected to the nature of the content being spread, rather than to the influencers who spread it, (b) virality is a phenomenon with many facets, i.e. under this generic term several different effects of persuasive communication are comprised and they only partially overlap. To give ground to our claims, we provide initial experiments in a machine learning framework to show how various aspects of virality can be independently predicted according to content features.
Causal conditioning and instantaneous coupling in causality graphs
Venue: arXiv cs.IT 2012
Year: 2012

The paper investigates the link between Granger causality graphs recently formalized by Eichler and directed information theory developed by Massey and Kramer. We particularly insist on the implication of two notions of causality that may occur in physical systems. It is well accepted that dynamical causality is assessed by the conditional transfer entropy, a measure appearing naturally as a part of directed information. Surprisingly the notion of instantaneous causality is often overlooked, even if it was clearly understood in early works. In the bivariate case, instantaneous coupling is measured adequately by the instantaneous information exchange, a measure that supplements the transfer entropy in the decomposition of directed information. In this paper, the focus is put on the multivariate case and conditional graph modeling issues. In this framework, we show that the decomposition of directed information into the sum of transfer entropy and information exchange does not hold anymore. Nevertheless, the discussion allows to put forward the two measures as pillars for the inference of causality graphs. We illustrate this on two synthetic examples which allow us to discuss not only the theoretical concepts, but also the practical estimation issues.
On the Application of Noisy Network Coding to the Relay-Eavesdropper Channel
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we consider the design of a new secrecy transmission scheme for a four-node relay-eavesdropper channel. The key idea of the proposed scheme is to combine noisy network coding with the interference assisted strategy for wiretap channel with a helping interferer. A new achievable secrecy rate is characterized for both discrete memoryless and Gaussian channels. Such a new rate can be viewed as a general framework, where the existing interference assisted schemes such as noisy-forwarding and cooperative jamming approaches can be shown as special cases of the proposed scheme. In addition, under some channel condition where the existing schemes can only achieve zero secrecy rate, the proposed secrecy scheme can still offer significant performance gains.
Network Formation: Heterogeneous Traffic, Bilateral Contracting and Myopic Dynamics
Venue: arXiv cs.GT 2012
Year: 2012

We study a network formation game where nodes wish to send traffic to other nodes. Nodes can contract bilaterally other nodes to form bidirectional links as well as nodes can break unilaterally contracts to eliminate the corresponding links. Our model is an extension of the model considered in Arcaute et al. The novelty is that we do no require the traffic to be uniform all-to-all. Each node specifies the amount of traffic that it wants to send to any other node. We characterize stable topologies under a static point of view and we also study the game under a myopic dynamics. We show its convergence to stable networks under some natural assumptions on the contracting functions. Finally we consider the efficiency of pairwise Nash topologies from a social point of view and we show that the problem of deciding the existence stable topologies of a given price is $\NP$-complete.