OpenRaiser/Intern-Atlas huggingface dataset:
Simple, Fast, and Scalable Reachability Oracle
Venue: arXiv cs.DB 2013
Year: 2013

A reachability oracle (or hop labeling) assigns each vertex v two sets of vertices: Lout(v) and Lin(v), such that u reaches v iff Lout(u) \cap Lin(v) \neq \emptyset. Despite their simplicity and elegance, reachability oracles have failed to achieve efficiency in more than ten years since their introduction: the main problem is high construction cost, which stems from a set-cover framework and the need to materialize transitive closure. In this paper, we present two simple and efficient labeling algorithms, Hierarchical-Labeling and Distribution-Labeling, which can work onmassive real-world graphs: their construction time is an order of magnitude faster than the setcover based labeling approach, and transitive closure materialization is not needed. On large graphs, their index sizes and their query performance can now beat the state-of-the-art transitive closure compression and online search approaches.
Graph-Theoretic Characterization of The Feasibility of The Precoding-Based 3-Unicast Interference Alignment Scheme
Venue: arXiv cs.IT 2013
Year: 2013

A new precoding-based intersession network coding (NC) scheme has recently been proposed, which applies the interference alignment technique, originally devised for wireless interference channels, to the 3-unicast problem of directed acyclic networks. The main result of this work is a graph-theoretic characterization of the feasibility of the 3-unicast interference alignment scheme. To that end, we first investigate several key relationships between the point-to-point network channel gains and the underlying graph structure. Such relationships turn out to be critical when characterizing graph-theoretically the feasibility of precoding-based solutions.
Privacy Preserving Recommendation System Based on Groups
Venue: arXiv cs.IR 2013
Year: 2013

Recommendation systems have received considerable attention in the recent decades. Yet with the development of information technology and social media, the risk in revealing private data to service providers has been a growing concern to more and more users. Trade-offs between quality and privacy in recommendation systems naturally arise. In this paper, we present a privacy preserving recommendation framework based on groups. The main idea is to use groups as a natural middleware to preserve users' privacy. A distributed preference exchange algorithm is proposed to ensure the anonymity of data, wherein the effective size of the anonymity set asymptotically approaches the group size with time. We construct a hybrid collaborative filtering model based on Markov random walks to provide recommendations and predictions to group members. Experimental results on the MovieLens and Epinions datasets show that our proposed methods outperform the baseline methods, L+ and ItemRank, two state-of-the-art personalized recommendation algorithms, for both recommendation precision and hit rate despite the absence of personal preference information.
LZ-Compressed String Dictionaries
Venue: arXiv cs.DS 2013
Year: 2013

We show how to compress string dictionaries using the Lempel-Ziv (LZ78) data compression algorithm. Our approach is validated experimentally on dictionaries of up to 1.5 GB of uncompressed text. We achieve compression ratios often outperforming the existing alternatives, especially on dictionaries containing many repeated substrings. Our query times remain competitive.
Fast, Incremental Inverted Indexing in Main Memory for Web-Scale Collections
Venue: arXiv cs.IR 2013
Year: 2013

For text retrieval systems, the assumption that all data structures reside in main memory is increasingly common. In this context, we present a novel incremental inverted indexing algorithm for web-scale collections that directly constructs compressed postings lists in memory. Designing efficient in-memory algorithms requires understanding modern processor architectures and memory hierarchies: in this paper, we explore the issue of postings lists contiguity. Naturally, postings lists that occupy contiguous memory regions are preferred for retrieval, but maintaining contiguity increases complexity and slows indexing. On the other hand, allowing discontiguous index segments simplifies index construction but decreases retrieval performance. Understanding this tradeoff is our main contribution: We find that co-locating small groups of inverted list segments yields query evaluation performance that is statistically indistinguishable from fully-contiguous postings lists. In other words, it is not necessary to lay out in-memory data structures such that all postings for a term are contiguous; we can achieve ideal performance with a relatively small amount of effort.
Increasing Smart Meter Privacy Through Energy Harvesting and Storage Devices
Venue: arXiv cs.IT 2013
Year: 2013

Smart meters are key elements for the operation of smart grids. By providing near realtime information on the energy consumption of individual users, smart meters increase the efficiency in generation, distribution and storage of energy in a smart grid. The ability of the utility provider to track users energy consumption inevitably leads to important threats to privacy. In this paper, privacy in a smart metering system is studied from an information theoretic perspective in the presence of energy harvesting and storage units. It is shown that energy harvesting provides increased privacy by diversifying the energy source, while a storage device can be used to increase both the energy efficiency and the privacy of the user. For given input load and energy harvesting rates, it is shown that there exists a trade-off between the information leakage rate, which is used to measure the privacy of the user, and the wasted energy rate, which is a measure of the energy-efficiency. The impact of the energy harvesting rate and the size of the storage device on this trade-off is also studied.
Equations for lower bounds on border rank
Venue: arXiv cs.CC 2013
Year: 2013

We present new methods for determining polynomials in the ideal of the variety of bilinear maps of border rank at most r. We apply these methods to several cases including the case r = 6 in the space of bilinear maps C^4 x C^4 -> C^4. This space of bilinear maps includes the matrix multiplication operator M_2 for two by two matrices. We show these newly obtained polynomials do not vanish on the matrix multiplication operator M_2, which gives a new proof that the border rank of the multiplication of 2 x 2 matrices is seven. Other examples are considered along with an explanation of how to implement the methods.
Off-Path Hacking: The Illusion of Challenge-Response Authentication
Venue: arXiv cs.CR 2013
Year: 2013

Everyone is concerned about the Internet security, yet most traffic is not cryptographically protected. The usual justification is that most attackers are only off-path and cannot intercept traffic; hence, challenge-response mechanisms suffice to ensure authenticity. Usually, the challenges re-use existing `unpredictable' header fields to protect widely-deployed protocols such as TCP and DNS. We argue that this practice may often only give an illusion of security. We present recent off-path TCP injection and DNS poisoning attacks, enabling attackers to circumvent existing challenge-response defenses. Both TCP and DNS attacks are non-trivial, yet very efficient and practical. The attacks foil widely deployed security mechanisms, such as the Same Origin Policy, and allow a wide range of exploits, e.g., long-term caching of malicious objects and scripts. We hope that this article will motivate adoption of cryptographic mechanisms such as SSL/TLS, IPsec and DNSSEC, and of correct, secure challenge-response mechanisms.
Nonlinearity Computation for Sparse Boolean Functions
Venue: arXiv cs.IT 2013
Year: 2013

An algorithm for computing the nonlinearity of a Boolean function from its algebraic normal form (ANF) is proposed. By generalizing the expression of the weight of a Boolean function in terms of its ANF coefficients, a formulation of the distances to linear functions is obtained. The special structure of these distances can be exploited to reduce the task of nonlinearity computation to solving an associated binary integer programming problem. The proposed algorithm can be used in cases where applying the Fast Walsh transform is infeasible, typically when the number of input variables exceeds 40.
Interference Aware Channel Assignmnet Using Edge Coloring in Multi-Channel Multi-Radio Wireless Mesh Networks
Venue: arXiv cs.NI 2013
Year: 2013

Recently multi-channel multi-radio wireless mesh networks are considered a reliable and cost effective way for internet access in wide area. A major research challenge in this network is selecting least interference channel from available channel and then assigning it to radio efficiently. Many algorithms and methods have been developed for channel assignment to maximize network throughput using orthogonal channels. Recent research and testbed experiments proved that POC based channel assignment allows more flexibility in wireless spectrum sharing. In this paper, we represent the channel assignment as a graph edge coloring problem using POC. The signal-to-noise interference ratio is measured to avoid interference from neighbouring transmission, when we assign channel to link. Simulation result shows that our proposed method improves network throughput and performance. Keywords: Wireless Mesh Networks, Multi-Radio, Multi-Channel, Partially Overlapping Channels, Signal-to-noise interference
Maximum-Bandwidth Node-Disjoint Paths
Venue: arXiv cs.NI 2013
Year: 2013

This paper presents a new method for finding the node-disjoint paths with maximum combined bandwidth in communication networks. This problem is an NP-complete problem which can be optimally solved in exponential time using integer linear programming (ILP). The presented method uses a maximum-cost variant of Dijkstra algorithm and a virtual-node representation to obtain the maximum-bandwidth node-disjoint path. Through several simulations, we compare the performance of our method to a modern heuristic technique and to the ILP solution. We show that, in a polynomial execution time, our proposed method produces results that are almost identical to ILP in a significantly lower execution time.
Intelligent Agent Based Semantic Web in Cloud Computing Environment
Venue: arXiv cs.IR 2013
Year: 2013

Considering today's web scenario, there is a need of effective and meaningful search over the web which is provided by Semantic Web. Existing search engines are keyword based. They are vulnerable in answering intelligent queries from the user due to the dependence of their results on information available in web pages. While semantic search engines provides efficient and relevant results as the semantic web is an extension of the current web in which information is given well defined meaning. MetaCrawler is a search tool that uses several existing search engines and provides combined results by using their own page ranking algorithm. This paper proposes development of a meta-semantic-search engine called SemanTelli which works within cloud. SemanTelli fetches results from different semantic search engines such as Hakia, DuckDuckGo, SenseBot with the help of intelligent agents that eliminate the limitations of existing search engines.
Opportunistic Third-Party Backhaul for Cellular Wireless Networks
Venue: arXiv cs.NI 2013
Year: 2013

With high capacity air interfaces and large numbers of small cells, backhaul -- the wired connectivity to base stations -- is increasingly becoming the cost driver in cellular wireless networks. One reason for the high cost of backhaul is that capacity is often purchased on leased lines with guaranteed rates provisioned to peak loads. In this paper, we present an alternate \emph{opportunistic backhaul} model where third parties provide base stations and backhaul connections and lease out excess capacity in their networks to the cellular provider when available, presumably at significantly lower costs than guaranteed connections. We describe a scalable architecture for such deployments using open access femtocells, which are small plug-and-play base stations that operate in the carrier's spectrum but can connect directly into the third party provider's wired network. Within the proposed architecture, we present a general user association optimization algorithm that enables the cellular provider to dynamically determine which mobiles should be assigned to the third-party femtocells based on the traffic demands, interference and channel conditions and third-party access pricing. Although the optimization is non-convex, the algorithm uses a computationally efficient method for finding approximate solutions via dual decomposition. Simulations of the deployment model based on actual base station locations are presented that show that large capacity gains are achievable if adoption of third-party, open access femtocells can reach even a small fraction of the current market penetration of WiFi access points.
Context Aware Computing for The Internet of Things: A Survey
Venue: arXiv cs.SE 2013
Year: 2013

As we are moving towards the Internet of Things (IoT), the number of sensors deployed around the world is growing at a rapid pace. Market research has shown a significant growth of sensor deployments over the past decade and has predicted a significant increment of the growth rate in the future. These sensors continuously generate enormous amounts of data. However, in order to add value to raw sensor data we need to understand it. Collection, modelling, reasoning, and distribution of context in relation to sensor data plays critical role in this challenge. Context-aware computing has proven to be successful in understanding sensor data. In this paper, we survey context awareness from an IoT perspective. We present the necessary background by introducing the IoT paradigm and context-aware fundamentals at the beginning. Then we provide an in-depth analysis of context life cycle. We evaluate a subset of projects (50) which represent the majority of research and commercial solutions proposed in the field of context-aware computing conducted over the last decade (2001-2011) based on our own taxonomy. Finally, based on our evaluation, we highlight the lessons to be learnt from the past and some possible directions for future research. The survey addresses a broad range of techniques, methods, models, functionalities, systems, applications, and middleware solutions related to context awareness and IoT. Our goal is not only to analyse, compare and consolidate past research work but also to appreciate their findings and discuss their applicability towards the IoT.
Hybridization of Otsu Method and Median Filter for Color Image Segmentation
Venue: arXiv cs.CV 2013
Year: 2013

In this article a novel algorithm for color image segmentation has been developed. The proposed algorithm based on combining two existing methods in such a novel way to obtain a significant method to partition the color image into significant regions. On the first phase, the traditional Otsu method for gray channel image segmentation were applied for each of the R,G, and B channels separately to determine the suitable automatic threshold for each channel. After that, the new modified channels are integrated again to formulate a new color image. The resulted image suffers from some kind of distortion. To get rid of this distortion, the second phase is arise which is the median filter to smooth the image and increase the segmented regions. This process looks very significant by the ocular eye. Experimental results were presented on a variety of test images to support the proposed algorithm.
Subsquares Approach - Simple Scheme for Solving Overdetermined Interval Linear Systems
Venue: arXiv cs.NA 2013
Year: 2013

In this work we present a new simple but efficient scheme - Subsquares approach - for development of algorithms for enclosing the solution set of overdetermined interval linear systems. We are going to show two algorithms based on this scheme and discuss their features. We start with a simple algorithm as a motivation, then we continue with a sequential algorithm. Both algorithms can be easily parallelized. The features of both algorithms will be discussed and numerically tested.
On Rational Closure in Description Logics of Typicality
Venue: arXiv cs.AI 2013
Year: 2013

We define the notion of rational closure in the context of Description Logics extended with a tipicality operator. We start from ALC+T, an extension of ALC with a typicality operator T: intuitively allowing to express concepts of the form T(C), meant to select the "most normal" instances of a concept C. The semantics we consider is based on rational model. But we further restrict the semantics to minimal models, that is to say, to models that minimise the rank of domain elements. We show that this semantics captures exactly a notion of rational closure which is a natural extension to Description Logics of Lehmann and Magidor's original one. We also extend the notion of rational closure to the Abox component. We provide an ExpTime algorithm for computing the rational closure of an Abox and we show that it is sound and complete with respect to the minimal model semantics.
How to Collaborate between Threshold Schemes
Venue: arXiv cs.CR 2013
Year: 2013

Threshold schemes have been used to protect secrets by distributing shares to participants. To protect two secrets, we can use two separate traditional schemes, say, a (t1, n1) scheme and a (t2, n2) scheme. If there are u (<=min(t1, t2)) participants involved in both schemes, each of these u participants must keep two different shares. This paper proposes a method that allows each common participant to keep only one share. Our method constructs two polynomials with u common crossover points. We give theoretical details and two demonstrative examples. This algorithm can also handle the collaboration between more than two schemes.
A Computer Vision System for Attention Mapping in SLAM based 3D Models
Venue: arXiv cs.CV 2013
Year: 2013

The study of human factors in the frame of interaction studies has been relevant for usability engi-neering and ergonomics for decades. Today, with the advent of wearable eye-tracking and Google glasses, monitoring of human factors will soon become ubiquitous. This work describes a computer vision system that enables pervasive mapping and monitoring of human attention. The key contribu-tion is that our methodology enables full 3D recovery of the gaze pointer, human view frustum and associated human centred measurements directly into an automatically computed 3D model in real-time. We apply RGB-D SLAM and descriptor matching methodologies for the 3D modelling, locali-zation and fully automated annotation of ROIs (regions of interest) within the acquired 3D model. This innovative methodology will open new avenues for attention studies in real world environments, bringing new potential into automated processing for human factors technologies.
Multi-Objective AI Planning: Comparing Aggregation and Pareto Approaches
Venue: arXiv cs.AI 2013
Year: 2013

Most real-world Planning problems are multi-objective, trying to minimize both the makespan of the solution plan, and some cost of the actions involved in the plan. But most, if not all existing approaches are based on single-objective planners, and use an aggregation of the objectives to remain in the single-objective context. Divide and Evolve (DaE) is an evolutionary planner that won the temporal deterministic satisficing track at the last International Planning Competitions (IPC). Like all Evolutionary Algorithms (EA), it can easily be turned into a Pareto-based Multi-Objective EA. It is however important to validate the resulting algorithm by comparing it with the aggregation approach: this is the goal of this paper. The comparative experiments on a recently proposed benchmark set that are reported here demonstrate the usefulness of going Pareto-based in AI Planning.
Canonical Forms and Automorphisms in the Projective Space
Venue: arXiv cs.IT 2013
Year: 2013

Let $\C$ be a sequence of multisets of subspaces of a vector space $\F_q^k$. We describe a practical algorithm which computes a canonical form and the stabilizer of $\C$ under the group action of the general semilinear group. It allows us to solve canonical form problems in coding theory, i.e. we are able to compute canonical forms of linear codes, $\F_{q}$-linear block codes over the alphabet $\F_{q^s}$ and random network codes under their natural notion of equivalence. The algorithm that we are going to develop is based on the partition refinement method and generalizes a previous work by the author on the computation of canonical forms of linear codes.
New Alignment Methods for Discriminative Book Summarization
Venue: arXiv cs.CL 2013
Year: 2013

We consider the unsupervised alignment of the full text of a book with a human-written summary. This presents challenges not seen in other text alignment problems, including a disparity in length and, consequent to this, a violation of the expectation that individual words and phrases should align, since large passages and chapters can be distilled into a single summary phrase. We present two new methods, based on hidden Markov models, specifically targeted to this problem, and demonstrate gains on an extractive book summarization task. While there is still much room for improvement, unsupervised alignment holds intrinsic value in offering insight into what features of a book are deemed worthy of summarization.
A Differential Equations Approach to Optimizing Regret Trade-offs
Venue: arXiv cs.LG 2013
Year: 2013

We consider the classical question of predicting binary sequences and study the {\em optimal} algorithms for obtaining the best possible regret and payoff functions for this problem. The question turns out to be also equivalent to the problem of optimal trade-offs between the regrets of two experts in an "experts problem", studied before by \cite{kearns-regret}. While, say, a regret of $Θ(\sqrt{T})$ is known, we argue that it important to ask what is the provably optimal algorithm for this problem --- both because it leads to natural algorithms, as well as because regret is in fact often comparable in magnitude to the final payoffs and hence is a non-negligible term. In the basic setting, the result essentially follows from a classical result of Cover from '65. Here instead, we focus on another standard setting, of time-discounted payoffs, where the final "stopping time" is not specified. We exhibit an explicit characterization of the optimal regret for this setting. To obtain our main result, we show that the optimal payoff functions have to satisfy the Hermite differential equation, and hence are given by the solutions to this equation. It turns out that characterization of the payoff function is qualitatively different from the classical (non-discounted) setting, and, namely, there's essentially a unique optimal solution.
A new framework for optimal classifier design
Venue: arXiv cs.CV 2013
Year: 2013

The use of alternative measures to evaluate classifier performance is gaining attention, specially for imbalanced problems. However, the use of these measures in the classifier design process is still unsolved. In this work we propose a classifier designed specifically to optimize one of these alternative measures, namely, the so-called F-measure. Nevertheless, the technique is general, and it can be used to optimize other evaluation measures. An algorithm to train the novel classifier is proposed, and the numerical scheme is tested with several databases, showing the optimality and robustness of the presented classifier.