OpenRaiser/Intern-Atlas huggingface dataset:
D-P2P-Sim+:A Novel Distributed Framework for P2P Protocols Performance Testing
Venue: arXiv cs.DB 2014
Year: 2014

In recent IoT (Internet of Things) and Web 2.0 technologies, a critical problem arises with respect to storing and processing the large amount of collected data. In this paper we develop and evaluate distributed infrastructures for storing and processing large amount of such data. We present a distributed framework that supports customized deployment of a variety of indexing engines over million-node overlays. The proposed framework provides the appropriate integrated set of tools that allows applications processing large amount of data, to evaluate and test the performance of various application protocols for very large scale deployments (multi million nodes - billions of keys). The key aim is to provide the appropriate environment that contributes in taking decisions regarding the choice of the protocol in storage P2P systems for a variety of big data applications. Using lightweight and efficient collection mechanisms, our system enables real-time registration of multiple measures, integrating support for real-life parameters such as node failure models and recovery strategies. Experiments have been performed at the PlanetLab network and at a typical research laboratory in order to verify scalability and show maximum re-usability of our setup. D-P2P-Sim+ framework is publicly available at http://code.google.com/p/d-p2p-sim/downloads/list.
On Defendability of Security Properties
Venue: arXiv cs.CR 2014
Year: 2014

We study the security of interaction protocols when incentives of participants are taken into account. We begin by formally defining correctness of a protocol, given a notion of rationality and utilities of participating agents. Based on that, we propose how to assess security when the precise incentives are unknown. Then, the security level can be defined in terms of defender sets, i.e., sets of participants who can effectively "defend" the security property as long as they are in favor of the property. We present some theoretical characterizations of defendable protocols under Nash equilibrium, first for bijective games (a standard assumption in game theory), and then for games with non-injective outcomes that better correspond to interaction protocols. Finally, we apply our concepts to analyze fairness in the ASW contract-signing protocol.
Nash Equilibria in Symmetric Games with Partial Observation
Venue: arXiv cs.GT 2014
Year: 2014

We investigate a model for representing large multiplayer games, which satisfy strong symmetry properties. This model is made of multiple copies of an arena; each player plays in his own arena, and can partially observe what the other players do. Therefore, this game has partial information and symmetry constraints, which make the computation of Nash equilibria difficult. We show several undecidability results, and for bounded-memory strategies, we precisely characterize the complexity of computing pure Nash equilibria (for qualitative objectives) in this game model.
A model-driven approach to broaden the detection of software performance antipatterns at runtime
Venue: arXiv cs.SE 2014
Year: 2014

Performance antipatterns document bad design patterns that have negative influence on system performance. In our previous work we formalized such antipatterns as logical predicates that predicate on four views: (i) the static view that captures the software elements (e.g. classes, components) and the static relationships among them; (ii) the dynamic view that represents the interaction (e.g. messages) that occurs between the software entities elements to provide the system functionalities; (iii) the deployment view that describes the hardware elements (e.g. processing nodes) and the mapping of the software entities onto the hardware platform; (iv) the performance view that collects specific performance indices. In this paper we present a lightweight infrastructure that is able to detect performance antipatterns at runtime through monitoring. The proposed approach precalculates such predicates and identifies antipatterns whose static, dynamic and deployment sub-predicates are validated by the current system configuration and brings at runtime the verification of performance sub-predicates. The proposed infrastructure leverages model-driven techniques to generate probes for monitoring the performance sub-predicates and detecting antipatterns at runtime.
Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency
Venue: arXiv cs.SI 2014
Year: 2014

Given a social network G and a constant k, the influence maximization problem asks for k nodes in G that (directly and indirectly) influence the largest number of nodes under a pre-defined diffusion model. This problem finds important applications in viral marketing, and has been extensively studied in the literature. Existing algorithms for influence maximization, however, either trade approximation guarantees for practical efficiency, or vice versa. In particular, among the algorithms that achieve constant factor approximations under the prominent independent cascade (IC) model or linear threshold (LT) model, none can handle a million-node graph without incurring prohibitive overheads. This paper presents TIM, an algorithm that aims to bridge the theory and practice in influence maximization. On the theory side, we show that TIM runs in O((k+\ell) (n+m) \log n / ε^2) expected time and returns a (1-1/e-ε)-approximate solution with at least 1 - n^{-\ell} probability. The time complexity of TIM is near-optimal under the IC model, as it is only a \log n factor larger than the Ω(m + n) lower-bound established in previous work (for fixed k, \ell, and ε). Moreover, TIM supports the triggering model, which is a general diffusion model that includes both IC and LT as special cases. On the practice side, TIM incorporates novel heuristics that significantly improve its empirical efficiency without compromising its asymptotic performance. We experimentally evaluate TIM with the largest datasets ever tested in the literature, and show that it outperforms the state-of-the-art solutions (with approximation guarantees) by up to four orders of magnitude in terms of running time. In particular, when k = 50, ε= 0.2, and \ell = 1, TIM requires less than one hour on a commodity machine to process a network with 41.6 million nodes and 1.4 billion edges.
Faster Shortest Paths in Dense Distance Graphs, with Applications
Venue: arXiv cs.DS 2014
Year: 2014

We show how to combine two techniques for efficiently computing shortest paths in directed planar graphs. The first is the linear-time shortest-path algorithm of Henzinger, Klein, Subramanian, and Rao [STOC'94]. The second is Fakcharoenphol and Rao's algorithm [FOCS'01] for emulating Dijkstra's algorithm on the dense distance graph (DDG). A DDG is defined for a decomposition of a planar graph $G$ into regions of at most $r$ vertices each, for some parameter $r < n$. The vertex set of the DDG is the set of $Θ(n/\sqrt r)$ vertices of $G$ that belong to more than one region (boundary vertices). The DDG has $Θ(n)$ arcs, such that distances in the DDG are equal to the distances in $G$. Fakcharoenphol and Rao's implementation of Dijkstra's algorithm on the DDG (nicknamed FR-Dijkstra) runs in $O(n\log(n) r^{-1/2} \log r)$ time, and is a key component in many state-of-the-art planar graph algorithms for shortest paths, minimum cuts, and maximum flows. By combining these two techniques we remove the $\log n$ dependency in the running time of the shortest-path algorithm, making it $O(n r^{-1/2} \log^2r)$. This work is part of a research agenda that aims to develop new techniques that would lead to faster, possibly linear-time, algorithms for problems such as minimum-cut, maximum-flow, and shortest paths with negative arc lengths. As immediate applications, we show how to compute maximum flow in directed weighted planar graphs in $O(n \log p)$ time, where $p$ is the minimum number of edges on any path from the source to the sink. We also show how to compute any part of the DDG that corresponds to a region with $r$ vertices and $k$ boundary vertices in $O(r \log k)$ time, which is faster than has been previously known for small values of $k$.
You are What you Eat (and Drink): Identifying Cultural Boundaries by Analyzing Food & Drink Habits in Foursquare
Venue: arXiv cs.SI 2014
Year: 2014

Food and drink are two of the most basic needs of human beings. However, as society evolved, food and drink became also a strong cultural aspect, being able to describe strong differences among people. Traditional methods used to analyze cross-cultural differences are mainly based on surveys and, for this reason, they are very difficult to represent a significant statistical sample at a global scale. In this paper, we propose a new methodology to identify cultural boundaries and similarities across populations at different scales based on the analysis of Foursquare check-ins. This approach might be useful not only for economic purposes, but also to support existing and novel marketing and social applications. Our methodology consists of the following steps. First, we map food and drink related check-ins extracted from Foursquare into users' cultural preferences. Second, we identify particular individual preferences, such as the taste for a certain type of food or drink, e.g., pizza or sake, as well as temporal habits, such as the time and day of the week when an individual goes to a restaurant or a bar. Third, we show how to analyze this information to assess the cultural distance between two countries, cities or even areas of a city. Fourth, we apply a simple clustering technique, using this cultural distance measure, to draw cultural boundaries across countries, cities and regions.
Dynamic Windows Scheduling with Reallocation
Venue: arXiv cs.DS 2014
Year: 2014

We consider the Windows Scheduling problem. The problem is a restricted version of Unit-Fractions Bin Packing, and it is also called Inventory Replenishment in the context of Supply Chain. In brief, the problem is to schedule the use of communication channels to clients. Each client ci is characterized by an active cycle and a window wi. During the period of time that any given client ci is active, there must be at least one transmission from ci scheduled in any wi consecutive time slots, but at most one transmission can be carried out in each channel per time slot. The goal is to minimize the number of channels used. We extend previous online models, where decisions are permanent, assuming that clients may be reallocated at some cost. We assume that such cost is a constant amount paid per reallocation. That is, we aim to minimize also the number of reallocations. We present three online reallocation algorithms for Windows Scheduling. We evaluate experimentally these protocols showing that, in practice, all three achieve constant amortized reallocations with close to optimal channel usage. Our simulations also expose interesting trade-offs between reallocations and channel usage. We introduce a new objective function for WS with reallocations, that can be also applied to models where reallocations are not possible. We analyze this metric for one of the algorithms which, to the best of our knowledge, is the first online WS protocol with theoretical guarantees that applies to scenarios where clients may leave and the analysis is against current load rather than peak load. Using previous results, we also observe bounds on channel usage for one of the algorithms.
An Efficient Two-Stage Sparse Representation Method
Venue: arXiv cs.CV 2014
Year: 2014

There are a large number of methods for solving under-determined linear inverse problem. Many of them have very high time complexity for large datasets. We propose a new method called Two-Stage Sparse Representation (TSSR) to tackle this problem. We decompose the representing space of signals into two parts, the measurement dictionary and the sparsifying basis. The dictionary is designed to approximate a sub-Gaussian distribution to exploit its concentration property. We apply sparse coding to the signals on the dictionary in the first stage, and obtain the training and testing coefficients respectively. Then we design the basis to approach an identity matrix in the second stage, to acquire the Restricted Isometry Property (RIP) and universality property. The testing coefficients are encoded over the basis and the final representing coefficients are obtained. We verify that the projection of testing coefficients onto the basis is a good approximation of the signal onto the representing space. Since the projection is conducted on a much sparser space, the runtime is greatly reduced. For concrete realization, we provide an instance for the proposed TSSR. Experiments on four biometrics databases show that TSSR is effective and efficient, comparing with several classical methods for solving linear inverse problem.
Scalable Planning and Learning for Multiagent POMDPs: Extended Version
Venue: arXiv cs.AI 2014
Year: 2014

Online, sample-based planning algorithms for POMDPs have shown great promise in scaling to problems with large state spaces, but they become intractable for large action and observation spaces. This is particularly problematic in multiagent POMDPs where the action and observation space grows exponentially with the number of agents. To combat this intractability, we propose a novel scalable approach based on sample-based planning and factored value functions that exploits structure present in many multiagent settings. This approach applies not only in the planning case, but also in the Bayesian reinforcement learning setting. Experimental results show that we are able to provide high quality solutions to large multiagent planning and learning problems.
AIS-MACA- Z: MACA based Clonal Classifier for Splicing Site, Protein Coding and Promoter Region Identification in Eukaryotes
Venue: arXiv cs.CE 2014
Year: 2014

Bioinformatics incorporates information regarding biological data storage, accessing mechanisms and presentation of characteristics within this data. Most of the problems in bioinformatics and be addressed efficiently by computer techniques. This paper aims at building a classifier based on Multiple Attractor Cellular Automata (MACA) which uses fuzzy logic with version Z to predict splicing site, protein coding and promoter region identification in eukaryotes. It is strengthened with an artificial immune system technique (AIS), Clonal algorithm for choosing rules of best fitness. The proposed classifier can handle DNA sequences of lengths 54,108,162,252,354. This classifier gives the exact boundaries of both protein and promoter regions with an average accuracy of 90.6%. This classifier can predict the splicing site with 97% accuracy. This classifier was tested with 1, 97,000 data components which were taken from Fickett & Toung , EPDnew, and other sequences from a renowned medical university.
Unified Performance Analysis of Mixed Line of Sight RF-FSO Fixed Gain Dual-Hop Transmission Systems
Venue: arXiv cs.IT 2014
Year: 2014

In this work, we carry out a unified performance analysis of a dual-hop fixed gain relay system over asymmetric links composed of both radio-frequency (RF) and unified free-space optics (FSO) under the effect of pointing errors. The RF link is modeled by the Nakagami-$m$ fading channel and the FSO link by the Gamma-Gamma fading channel subject to both types of detection techniques (i.e. heterodyne detection and intensity modulation with direct detection (IM/DD)). In particular, we derive new unified closed-form expressions for the cumulative distribution function, the probability density function, the moment generation function, and the moments of the end-to-end signal-to-noise ratio of these systems in terms of the Meijer's G function. Based on these formulas, we offer exact closed-form expressions for the outage probability, the higher-order amount of fading, and the average bit-error rate of a variety of binary modulations in terms of the Meijer's G function. Further, an exact closed-form expression for the end-to-end ergodic capacity for the Nakagami-$m$-unified FSO relay links is derived in terms of the bivariate G function. All the given results are verified via Computer-based Monte-Carlo simulations.
Lattices over Eisenstein Integers for Compute-and-Forward
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider the use of lattice codes over Eisenstein integers for implementing a compute-and-forward protocol in wireless networks when channel state information is not available at the transmitter. We extend the compute-and-forward paradigm of Nazer and Gastpar to decoding Eisenstein integer combinations of transmitted messages at relays by proving the existence of a sequence of pairs of nested lattices over Eisenstein integers in which the coarse lattice is good for covering and the fine lattice can achieve the Poltyrev limit. Using this result, we show that both the outage performance and error-correcting performance of nested lattice codebooks over Eisenstein integers surpasses lattice codebooks over integers considered by Nazer and Gastpar with no additional computational complexity.
Efficient Task Replication for Fast Response Times in Parallel Computation
Venue: arXiv cs.DC 2014
Year: 2014

One typical use case of large-scale distributed computing in data centers is to decompose a computation job into many independent tasks and run them in parallel on different machines, sometimes known as the "embarrassingly parallel" computation. For this type of computation, one challenge is that the time to execute a task for each machine is inherently variable, and the overall response time is constrained by the execution time of the slowest machine. To address this issue, system designers introduce task replication, which sends the same task to multiple machines, and obtains result from the machine that finishes first. While task replication reduces response time, it usually increases resource usage. In this work, we propose a theoretical framework to analyze the trade-off between response time and resource usage. We show that, while in general, there is a tension between response time and resource usage, there exist scenarios where replicating tasks judiciously reduces completion time and resource usage simultaneously. Given the execution time distribution for machines, we investigate the conditions for a scheduling policy to achieve optimal performance trade-off, and propose efficient algorithms to search for optimal or near-optimal scheduling policies. Our analysis gives insights on when and why replication helps, which can be used to guide scheduler design in large-scale distributed computing systems.
Studying Social Networks at Scale: Macroscopic Anatomy of the Twitter Social Graph
Venue: arXiv cs.SI 2014
Year: 2014

Twitter is one of the largest social networks using exclusively directed links among accounts. This makes the Twitter social graph much closer to the social graph supporting real life communications than, for instance, Facebook. Therefore, understanding the structure of the Twitter social graph is interesting not only for computer scientists, but also for researchers in other fields, such as sociologists. However, little is known about how the information propagation in Twitter is constrained by its inner structure. In this paper, we present an in-depth study of the macroscopic structure of the Twitter social graph unveiling the highways on which tweets propagate, the specific user activity associated with each component of this macroscopic structure, and the evolution of this macroscopic structure with time for the past 6 years. For this study, we crawled Twitter to retrieve all accounts and all social relationships (follow links) among accounts; the crawl completed in July 2012 with 505 million accounts interconnected by 23 billion links. Then, we present a methodology to unveil the macroscopic structure of the Twitter social graph. This macroscopic structure consists of 8 components defined by their connectivity characteristics. Each component group users with a specific usage of Twitter. For instance, we identified components gathering together spammers, or celebrities. Finally, we present a method to approximate the macroscopic structure of the Twitter social graph in the past, validate this method using old datasets, and discuss the evolution of the macroscopic structure of the Twitter social graph during the past 6 years.
Non-Asymptotic Mean-Field Games
Venue: arXiv cs.GT 2014
Year: 2014

Mean-field games have been studied under the assumption of very large number of players. For such large systems, the basic idea consists to approximate large games by a stylized game model with a continuum of players. The approach has been shown to be useful in some applications. However, the stylized game model with continuum of decision-makers is rarely observed in practice and the approximation proposed in the asymptotic regime is meaningless for networks with few entities. In this paper we propose a mean-field framework that is suitable not only for large systems but also for a small world with few number of entities. The applicability of the proposed framework is illustrated through various examples including dynamic auction with asymmetric valuation distributions, and spiteful bidders.
An Enhanced Multi-Pager Environment Support for Second Generation Microkernels
Venue: arXiv cs.OS 2014
Year: 2014

The main objective of this paper is to present a mechanism of enhanced paging support for the second generation microkernels in the form of explicit support of multi-pager environment for the tasks running in the system. Proposed mechanism is based on the intra-kernel high granularity pagers assignments per virtual address space, which allow efficient and simple dispatching of page faults to the appropriate pagers. The paging is one of the major features of the virtual memory, which is extensively used by advanced operating systems to provide an illusion of elastic memory. Original and present second generation microkernels provide only limited, inflexible and unnatural support for paging. Furthermore, facilities provided by current solutions for multi-pager support on the runtime level introduce an overhead in terms of mode switches and thread context switches which can be significantly reduced. Limited paging support limits the attractiveness of the second generation microkernel based systems use in real-life applications, in which processes usually have concurrent servicing of multiple paging servers. The purpose of this paper is to present a facilities for the efficient and flexible support of multi-pager environments for the second generation microkernels. A comparison of the proposed solution to the present architecture L4 + L4Re has been made and overhead of the page fault handling critical path has been evaluated. Proposed solution is simple enough and provides a natural and flexible support of multi-pager environments for second generation microkernels in efficient way. It introduces a third less overhead in terms of the mode switches and thread context switches in comparison to the present L4 + L4Re solution implemented in the Fiasco.OC.
Icon Based Information Retrieval and Disease Identification in Agriculture
Venue: arXiv cs.HC 2014
Year: 2014

Recent developments in the ICT industry in past few decades has enabled the quick and easy access to the information available on the internet. But, digital literacy is the pre-requisite for its use. The main purpose of this paper is to provide an interface for digitally illiterate users, especially farmers to efficiently and effectively retrieve information through Internet. In addition, to enable the farmers to identify the disease in their crop, its cause and symptoms using digital image processing and pattern recognition instantly without waiting for an expert to visit the farms and identify the disease.