OpenRaiser/Intern-Atlas huggingface dataset:
Data Dissemination in Cognitive Radio Networks
Venue: arXiv cs.NI 2011
Year: 2011

In this report, we first describe the problem that we are dealing with i.e. data dissemination in multi-hop cognitive radio networks. To address this problem, we propose a channel selection strategy named 'SURF'. We evaluate the proposed channel selection strategy in both single-hop and multi-hop scenarios and compared it with relevant approaches. So far, one technical report and a poster is published as part of this work, while two publications are under review; one is in IEEE Communications Letters and the second one is in IEEE WoWMoM conference. In on-going works sections, we first mention some possible directions in the context of SURF. In addition to that, we mention different research problems that we are planning to deal during the course of this PhD dissertation.
Fast and Scalable Analysis of Massive Social Graphs
Venue: arXiv cs.SI 2011
Year: 2011

Graph analysis is a critical component of applications such as online social networks, protein interactions in biological networks, and Internet traffic analysis. The arrival of massive graphs with hundreds of millions of nodes, e.g. social graphs, presents a unique challenge to graph analysis applications. Most of these applications rely on computing distances between node pairs, which for large graphs can take minutes to compute using traditional algorithms such as breadth-first-search (BFS). In this paper, we study ways to enable scalable graph processing on today's massive graphs. We explore the design space of graph coordinate systems, a new approach that accurately approximates node distances in constant time by embedding graphs into coordinate spaces. We show that a hyperbolic embedding produces relatively low distortion error, and propose Rigel, a hyperbolic graph coordinate system that lends itself to efficient parallelization across a compute cluster. Rigel produces significantly more accurate results than prior systems, and is naturally parallelizable across compute clusters, allowing it to provide accurate results for graphs up to 43 million nodes. Finally, we show that Rigel's functionality can be easily extended to locate (near-) shortest paths between node pairs. After a one- time preprocessing cost, Rigel answers node-distance queries in 10's of microseconds, and also produces shortest path results up to 18 times faster than prior shortest-path systems with similar levels of accuracy.
Finite countermodels for safety verification of parameterized tree systems
Venue: arXiv cs.LO 2011
Year: 2011

In this paper we deal with verification of safety properties of parameterized systems with a tree topology. The verification problem is translated to a purely logical problem of finding a finite countermodel for a first-order formula, which further resolved by a generic finite model finding procedure. A finite countermodel method is shown is at least as powerful as regular tree model checking and as the methods based on monotonic abstraction and backwards symbolic reachability. The practical efficiency of the method is illustrated on a set of examples taken from the literature.
Matroidal Degree-Bounded Minimum Spanning Trees
Venue: arXiv cs.DS 2011
Year: 2011

We consider the minimum spanning tree (MST) problem under the restriction that for every vertex v, the edges of the tree that are adjacent to v satisfy a given family of constraints. A famous example thereof is the classical degree-constrained MST problem, where for every vertex v, a simple upper bound on the degree is imposed. Iterative rounding/relaxation algorithms became the tool of choice for degree-bounded network design problems. A cornerstone for this development was the work of Singh and Lau, who showed for the degree-bounded MST problem how to find a spanning tree violating each degree bound by at most one unit and with cost at most the cost of an optimal solution that respects the degree bounds. However, current iterative rounding approaches face several limits when dealing with more general degree constraints. In particular, when several constraints are imposed on the edges adjacent to a vertex v, as for example when a partition of the edges adjacent to v is given and only a fixed number of elements can be chosen out of each set of the partition, current approaches might violate each of the constraints by a constant, instead of violating all constraints together by at most a constant number of edges. Furthermore, it is also not clear how previous iterative rounding approaches can be used for degree constraints where some edges are in a super-constant number of constraints. We extend iterative rounding/relaxation approaches both on a conceptual level as well as aspects involving their analysis to address these limitations. This leads to an efficient algorithm for the degree-constrained MST problem where for every vertex v, the edges adjacent to v have to be independent in a given matroid. The algorithm returns a spanning tree T of cost at most OPT, such that for every vertex v, it suffices to remove at most 8 edges from T to satisfy the matroidal degree constraint at v.
An Anonymous Authentication and Communication Protocol for Wireless Mesh Networks
Venue: arXiv cs.CR 2011
Year: 2011

Wireless mesh networks (WMNs) have emerged as a key technology for next generation wireless broadband networks showing rapid progress and inspiring numerous compelling applications. A WMN comprises of a set of mesh routers (MRs) and mesh clients (MCs), where MRs are connected to the Internet backbone through the Internet gateways (IGWs). The MCs are wireless devices and communicate among themselves over possibly multi-hop paths with or without the involvement of MRs. User privacy and security have been primary concerns in WMNs due to their peer-to-peer network topology, shared wireless medium, stringent resource constraints, and highly dynamic environment. Moreover, to support real-time applications, WMNs must also be equipped with robust, reliable and efficient communication protocols so as to minimize the end-to-end latency and packet drops. Design of a secure and efficient communication protocol for WMNs, therefore, is of paramount importance. In this paper, we propose a security and privacy protocol that provides security and user anonymity while maintaining communication efficiency in a WMN. The security protocol ensures secure authentication and encryption in access and the backbone networks. The user anonymity, authentication and data privacy is achieved by application of a protocol that is based on Rivest's ring signature scheme. Simulation results demonstrate that while the protocols have minimal storage and communication overhead, they are robust and provide high level of security and privacy to the users of the network services.
Efficient Instance Retrieval of Subgoals for Subsumptive Tabled Evaluation of Logic Programs
Venue: arXiv cs.PL 2011
Year: 2011

Tabled evaluation is an implementation technique that solves some problems of traditional Prolog systems in dealing with recursion and redundant computations. Most tabling engines determine if a tabled subgoal will produce or consume answers by using variant checks. A more refined method, named call subsumption, considers that a subgoal A will consume from a subgoal B if A is subsumed by (an instance of) B, thus allowing greater answer reuse. We recently developed an extension, called Retroactive Call Subsumption, that improves upon call subsumption by supporting bidirectional sharing of answers between subsumed/subsuming subgoals. In this paper, we present both an algorithm and an extension to the table space data structures to efficiently implement instance retrieval of subgoals for subsumptive tabled evaluation of logic programs. Experiments results using the YapTab tabling system show that our implementation performs quite well on some complex benchmarks and is robust enough to handle a large number of subgoals without performance degradation.
You Share, I Share: Network Effects and Economic Incentives in P2P File-Sharing Systems
Venue: arXiv cs.NI 2011
Year: 2011

We study the interaction between network effects and external incentives on file sharing behavior in Peer-to-Peer (P2P) networks. Many current or envisioned P2P networks reward individuals for sharing files, via financial incentives or social recognition. Peers weigh this reward against the cost of sharing incurred when others download the shared file. As a result, if other nearby nodes share files as well, the cost to an individual node decreases. Such positive network sharing effects can be expected to increase the rate of peers who share files. In this paper, we formulate a natural model for the network effects of sharing behavior, which we term the "demand model." We prove that the model has desirable diminishing returns properties, meaning that the network benefit of increasing payments decreases when the payments are already high. This result holds quite generally, for submodular objective functions on the part of the network operator. In fact, we show a stronger result: the demand model leads to a "coverage process," meaning that there is a distribution over graphs such that reachability under this distribution exactly captures the joint distribution of nodes which end up sharing. The existence of such distributions has advantages in simulating and estimating the performance of the system. We establish this result via a general theorem characterizing which types of models lead to coverage processes, and also show that all coverage processes possess the desirable submodular properties. We complement our theoretical results with experiments on several real-world P2P topologies. We compare our model quantitatively against more naïve models ignoring network effects. A main outcome of the experiments is that a good incentive scheme should make the reward dependent on a node's degree in the network.
On the Impact of Random Index-Partitioning on Index Compression
Venue: arXiv cs.IR 2011
Year: 2011

The performance of processing search queries depends heavily on the stored index size. Accordingly, considerable research efforts have been devoted to the development of efficient compression techniques for inverted indexes. Roughly, index compression relies on two factors: the ordering of the indexed documents, which strives to position similar documents in proximity, and the encoding of the inverted lists that result from the ordered stream of documents. Large commercial search engines index tens of billions of pages of the ever growing Web. The sheer size of their indexes dictates the distribution of documents among thousands of servers in a scheme called local index-partitioning, such that each server indexes only several millions pages. Due to engineering and runtime performance considerations, random distribution of documents to servers is common. However, random index-partitioning among many servers adversely impacts the resulting index sizes, as it decreases the effectiveness of document ordering schemes. We study the impact of random index-partitioning on document ordering schemes. We show that index-partitioning decreases the aggregated size of the inverted lists logarithmically with the number of servers, when documents within each server are randomly reordered. On the other hand, the aggregated partitioned index size increases logarithmically with the number of servers, when state-of-the-art document ordering schemes, such as lexical URL sorting and clustering with TSP, are applied. Finally, we justify the common practice of randomly distributing documents to servers, as we qualitatively show that despite its ill-effects on the ensuing compression, it decreases key factors in distributed query evaluation time by an order of magnitude as compared with partitioning techniques that compress better.
NEMO: Extraction and normalization of organization names from PubMed affiliation strings
Venue: arXiv cs.CL 2011
Year: 2011

We propose NEMO, a system for extracting organization names in the affiliation and normalizing them to a canonical organization name. Our parsing process involves multi-layered rule matching with multiple dictionaries. The system achieves more than 98% f-score in extracting organization names. Our process of normalization that involves clustering based on local sequence alignment metrics and local learning based on finding connected components. A high precision was also observed in normalization. NEMO is the missing link in associating each biomedical paper and its authors to an organization name in its canonical form and the Geopolitical location of the organization. This research could potentially help in analyzing large social networks of organizations for landscaping a particular topic, improving performance of author disambiguation, adding weak links in the co-author network of authors, augmenting NLM's MARS system for correcting errors in OCR output of affiliation field, and automatically indexing the PubMed citations with the normalized organization name and country. Our system is available as a graphical user interface available for download along with this paper.
Information, Utility & Bounded Rationality
Venue: arXiv cs.AI 2011
Year: 2011

Perfectly rational decision-makers maximize expected utility, but crucially ignore the resource costs incurred when determining optimal actions. Here we employ an axiomatic framework for bounded rational decision-making based on a thermodynamic interpretation of resource costs as information costs. This leads to a variational "free utility" principle akin to thermodynamical free energy that trades off utility and information costs. We show that bounded optimal control solutions can be derived from this variational principle, which leads in general to stochastic policies. Furthermore, we show that risk-sensitive and robust (minimax) control schemes fall out naturally from this framework if the environment is considered as a bounded rational and perfectly rational opponent, respectively. When resource costs are ignored, the maximum expected utility principle is recovered.
Three Applications to Rational Relations of the High Undecidability of the Infinite Post Correspondence Problem in a Regular omega-Language
Venue: arXiv cs.LO 2011
Year: 2011

It was noticed by Harel in [Har86] that "one can define $Σ_1^1$-complete versions of the well-known Post Correspondence Problem". We first give a complete proof of this result, showing that the infinite Post Correspondence Problem in a regular $ω$-language is $Σ_1^1$-complete, hence located beyond the arithmetical hierarchy and highly undecidable. We infer from this result that it is $Π_1^1$-complete to determine whether two given infinitary rational relations are disjoint. Then we prove that there is an amazing gap between two decision problems about $ω$-rational functions realized by finite state Büchi transducers. Indeed Prieur proved in [Pri01, Pri02] that it is decidable whether a given $ω$-rational function is continuous, while we show here that it is $Σ_1^1$-complete to determine whether a given $ω$-rational function has at least one point of continuity. Next we prove that it is $Π_1^1$-complete to determine whether the continuity set of a given $ω$-rational function is $ω$-regular. This gives the exact complexity of two problems which were shown to be undecidable in [CFS08].
An Algebraic Specification of the Semantic Web
Venue: arXiv cs.LO 2011
Year: 2011

We present a formal specification of the Semantic Web, as an extension of the World Wide Web using the well known algebraic specification language CafeOBJ. Our approach allows the description of the key elements of the Semantic Web technologies, in order to give a better understanding of the system, without getting involved with their implementation details that might not yet be standardized. This specification is part of our work in progress concerning the modeling the Social Semantic Web.
Reachability in Biochemical Dynamical Systems by Quantitative Discrete Approximation
Venue: arXiv cs.SY 2011
Year: 2011

In this paper a novel computational technique for finite discrete approximation of continuous dynamical systems suitable for a significant class of biochemical dynamical systems is introduced. The method is parameterized in order to affect the imposed level of approximation provided that with increasing parameter value the approximation converges to the original continuous system. By employing this approximation technique, we present algorithms solving the reachability problem for biochemical dynamical systems. The presented method and algorithms are evaluated on several exemplary biological models and on a real case study. This is a full version of the paper published in the proceedings of CompMod 2011.
Optimal, scalable forward models for computing gravity anomalies
Venue: arXiv cs.CE 2011
Year: 2011

We describe three approaches for computing a gravity signal from a density anomaly. The first approach consists of the classical "summation" technique, whilst the remaining two methods solve the Poisson problem for the gravitational potential using either a Finite Element (FE) discretization employing a multilevel preconditioner, or a Green's function evaluated with the Fast Multipole Method (FMM). The methods utilizing the PDE formulation described here differ from previously published approaches used in gravity modeling in that they are optimal, implying that both the memory and computational time required scale linearly with respect to the number of unknowns in the potential field. Additionally, all of the implementations presented here are developed such that the computations can be performed in a massively parallel, distributed memory computing environment. Through numerical experiments, we compare the methods on the basis of their discretization error, CPU time and parallel scalability. We demonstrate the parallel scalability of all these techniques by running forward models with up to $10^8$ voxels on 1000's of cores.
Input-Output Finite-Time Stability
Venue: arXiv cs.SY 2011
Year: 2011

This paper introduces the extension of Finite-Time Stability (FTS) to the input-output case, namely the Input-Output FTS (IO-FTS). The main differences between classic IO stability and IO-FTS are that the latter involves signals defined over a finite time interval, does not necessarily require the inputs and outputs to belong to the same class of signals, and that quantitative bounds on both inputs and outputs must be specified. This paper revises some recent results on IO-FTS, both in the context of linear systems and in the context of switching systems. In the final example the proposed methodology is used to minimize the maximum displacement and velocity of a building subject to an earthquake of given magnitude.
Snap-Stabilizing Message Forwarding Algorithm on Tree Topologies
Venue: arXiv cs.DC 2011
Year: 2011

In this paper, we consider the message forwarding problem that consists in managing the network resources that are used to forward messages. Previous works on this problem provide solutions that either use a significant number of buffers (that is n buffers per processor, where n is the number of processors in the network) making the solution not scalable or, they reserve all the buffers from the sender to the receiver to forward only one message %while using D buffers (where D refers to the diameter of the network) . The only solution that uses a constant number of buffers per link was introduced in [1]. However the solution works only on a chain networks. In this paper, we propose a snap-stabilizing algorithm for the message forwarding problem that uses the same complexity on the number of buffers as [1] and works on tree topologies.
Explicit Solution of Worst-Case Secrecy Rate for MISO Wiretap Channels with Spherical Uncertainty
Venue: arXiv cs.IT 2011
Year: 2011

A multiple-input single-output (MISO) wiretap channel model is considered, that includes a multi-antenna transmitter, a single-antenna legitimate receiver and a single-antenna eavesdropper. For the scenario in which spherical uncertainty for both the legitimate and the eavesdropper channels is included, the problem of finding the optimal input covariance that maximizes the worst-case secrecy rate subject to a power constraint, is considered, and an explicit expression for the maximum worst-case secrecy rate is provided.
A Verified Algebra for Linked Data
Venue: arXiv cs.LO 2011
Year: 2011

A foundation is investigated for the application of loosely structured data on the Web. This area is often referred to as Linked Data, due to the use of URIs in data to establish links. This work focuses on emerging W3C standards which specify query languages for Linked Data. The approach is to provide an abstract syntax to capture Linked Data structures and queries, which are then internalised in a process calculus. An operational semantics for the calculus specifies how queries, data and processes interact. A labelled transition system is shown to be sound with respect to the operational semantics. Bisimulation over the labelled transition system is used to verify an algebra over queries. The derived algebra is a contribution to the application domain. For instance, the algebra may be used to rewrite a query to optimise its distribution across a cluster of servers. The framework used to provide the operational semantics is powerful enough to model related calculi for the Web.
Adaptive Drift Analysis
Venue: arXiv cs.DS 2011
Year: 2011

We show that, for any c>0, the (1+1) evolutionary algorithm using an arbitrary mutation rate p_n = c/n finds the optimum of a linear objective function over bit strings of length n in expected time Theta(n log n). Previously, this was only known for c at most 1. Since previous work also shows that universal drift functions cannot exist for c larger than a certain constant, we instead define drift functions which depend crucially on the relevant objective functions (and also on c itself). Using these carefully-constructed drift functions, we prove that the expected optimisation time is Theta(n log n). By giving an alternative proof of the multiplicative drift theorem, we also show that our optimisation-time bound holds with high probability.
Observational equivalences for linear logic CC languages
Venue: arXiv cs.PL 2011
Year: 2011

Linear logic Concurrent Constraint programming (LCC) is an extension of concurrent constraint programming (CC) where the constraint system is based on Girard's linear logic instead of the classical logic. In this paper we address the problem of program equivalence for this programming framework. For this purpose, we present a structural operational semantics for LCC based on a label transition system and investigate different notions of observational equivalences inspired by the state of art of process algebras. Then, we demonstrate that the asynchronous π-calculus can be viewed as simple syntactical restrictions of LCC. Finally we show LCC observational equivalences can be transposed straightforwardly to classical Concurrent Constraint languages and Constraint Handling Rules, and investigate the resulting equivalences.