OpenRaiser/Intern-Atlas huggingface dataset:
Where Graph Topology Matters: The Robust Subgraph Problem
Venue: arXiv cs.SI 2015
Year: 2015

Robustness is a critical measure of the resilience of large networked systems, such as transportation and communication networks. Most prior works focus on the global robustness of a given graph at large, e.g., by measuring its overall vulnerability to external attacks or random failures. In this paper, we turn attention to local robustness and pose a novel problem in the lines of subgraph mining: given a large graph, how can we find its most robust local subgraph (RLS)? We define a robust subgraph as a subset of nodes with high communicability among them, and formulate the RLS-PROBLEM of finding a subgraph of given size with maximum robustness in the host graph. Our formulation is related to the recently proposed general framework for the densest subgraph problem, however differs from it substantially in that besides the number of edges in the subgraph, robustness also concerns with the placement of edges, i.e., the subgraph topology. We show that the RLS-PROBLEM is NP-hard and propose two heuristic algorithms based on top-down and bottom-up search strategies. Further, we present modifications of our algorithms to handle three practical variants of the RLS-PROBLEM. Experiments on synthetic and real-world graphs demonstrate that we find subgraphs with larger robustness than the densest subgraphs even at lower densities, suggesting that the existing approaches are not suitable for the new problem setting.
HOG based Fast Human Detection
Venue: arXiv cs.RO 2015
Year: 2015

Objects recognition in image is one of the most difficult problems in computer vision. It is also an important step for the implementation of several existing applications that require high-level image interpretation. Therefore, there is a growing interest in this research area during the last years. In this paper, we present an algorithm for human detection and recognition in real-time, from images taken by a CCD camera mounted on a car-like mobile robot. The proposed technique is based on Histograms of Oriented Gradient (HOG) and SVM classifier. The implementation of our detector has provided good results, and can be used in robotics tasks.
New Hashing Algorithm for Use in TCP Reassembly Module of IPS
Venue: arXiv cs.DS 2015
Year: 2015

Since last decade, IDS/ IPS has gained popularity in protecting large networks. They can employ signature based techniques and/or flow-based techniques to prevent intrusion from outside/ inside the network they are trying to protect. Signature based IDS/ IPS can be stateless or stateful. Stateful IDS can store the state of the protocol and use it for better detection of malware. In the case of TCP/IP networks, an attacker can also launch an attack such that the malicious code is distributed over many packets. These packets pass through the traditional IDS/ IPS and reassemble inside the network. Once re-assembled inside the network by the TCP/IP layer, the malicious code launches an attack. The TCP state and a copy of last few packets for each active connection has to be maintained in IDS/IPS. In TCP re-assembly, packets are re-assembled at IDS/IPS and searched for signature matches. A connection table has to be maintained for active connections and their list of last few (atmost 11) packets that have already arrived. We need data structures for searching the connection that the latest incoming packet belongs to. Popular hashing algorithms like CRC, XOR, summing tuple, taking modulus are inefficient as hash keys are not evenly distributed in hash-key space. Thus we show how an algorithm based on cryptography concepts can be used for efficient hashing in network connection management. We also show how to use full four tuple for calculating hash key instead of simply summing the tuple and taking the modulus of the sum.
Introduction and Ranking Results of the ICSI 2014 Competition on Single Objective Optimization
Venue: arXiv cs.NE 2015
Year: 2015

This technical report includes the introduction and ranking results of the ICSI 2014 Competition on Single Objective Optimization.
Design and Implementation of rowe, a Web-Friendly Communication Library
Venue: arXiv cs.DC 2015
Year: 2015

The INDES project-team of Inria has been developing HOP, a multi-tier language for Web programming. As part of the RAPP FP7 European project, the team has set out to use HOP as the lingua franca of the robotics applications developed within that project. Part of the challenge lies in the integration of existing robotics code, written using ROS or custom libraries, with HOP-based application. This document reports on the implementation of rowe, a communication library designed the fill the gap between low-level robotics C components on one hand, and other C, C++, ROS, or HOP components on the other. The library aims to be a lightweight, high-performance, "Web-friendly" communication library. It implements a socket-like interface that allows programs to exchange JSON objects over WebSockets. We describe the rationale, design, and implementation of rowe.
Brief Announcement: Update Consistency in Partitionable Systems
Venue: arXiv cs.DC 2015
Year: 2015

Data replication is essential to ensure reliability, availability and fault-tolerance of massive distributed applications over large scale systems such as the Internet. However, these systems are prone to partitioning, which by Brewer's CAP theorem [1] makes it impossible to use a strong consistency criterion like atomicity. Eventual consistency [2] guaranties that all replicas eventually converge to a common state when the participants stop updating. However, it fails to fully specify shared objects and requires additional non-intuitive and error-prone distributed specification techniques, that must take into account all possible concurrent histories of updates to specify this common state [3]. This approach, that can lead to specifications as complicated as the implementations themselves, is limited by a more serious issue. The concurrent specification of objects uses the notion of concurrent events. In message-passing systems, two events are concurrent if they are enforced by different processes and each process enforced its event before it received the notification message from the other process. In other words, the notion of concurrency depends on the implementation of the object, not on its specification. Consequently, the final user may not know if two events are concurrent without explicitly tracking the messages exchanged by the processes. A specification should be independent of the system on which it is implemented. We believe that an object should be totally specified by two facets: its abstract data type, that characterizes its sequential executions, and a consistency criterion, that defines how it is supposed to behave in a distributed environment. Not only sequential specification helps repeal the problem of intention, it also allows to use the well studied and understood notions of languages and automata. This makes possible to apply all the tools developed for sequential systems, from their simple definition using structures and classes to the most advanced techniques like model checking and formal verification. Eventual consistency (EC) imposes no constraint on the convergent state, that very few depends on the sequential specification. For example, an implementation that ignores all the updates is eventually consistent, as all replicas converge to the initial state. We propose a new consistency criterion, update consistency (UC), in which the convergent state must be obtained by a total ordering of the updates, that contains the sequential order of each
Efficient Computation by Three Counter Machines
Venue: arXiv cs.CC 2015
Year: 2015

We show that multiplication can be done in polynomial time on a three counter machine that receives its input as the contents of two counters. The technique is generalized to functions of two variables computable by deterministic Turing machines in linear space.
Range Queries on Uncertain Data
Venue: arXiv cs.CG 2015
Year: 2015

Given a set $P$ of $n$ uncertain points on the real line, each represented by its one-dimensional probability density function, we consider the problem of building data structures on $P$ to answer range queries of the following three types for any query interval $I$: (1) top-$1$ query: find the point in $P$ that lies in $I$ with the highest probability, (2) top-$k$ query: given any integer $k\leq n$ as part of the query, return the $k$ points in $P$ that lie in $I$ with the highest probabilities, and (3) threshold query: given any threshold $τ$ as part of the query, return all points of $P$ that lie in $I$ with probabilities at least $τ$. We present data structures for these range queries with linear or nearly linear space and efficient query time.
Delay Minimizing User Association in Cellular Networks via Hierarchically Well-Separated Trees
Venue: arXiv cs.IT 2015
Year: 2015

We study downlink delay minimization within the context of cellular user association policies that map mobile users to base stations. We note the delay minimum user association problem fits within a broader class of network utility maximization and can be posed as a non-convex quadratic program. This non-convexity motivates a split quadratic objective function that captures the original problem's inherent tradeoff: association with a station that provides the highest signal-to-interference-plus-noise ratio (SINR) vs. a station that is least congested. We find the split-term formulation is amenable to linearization by embedding the base stations in a hierarchically well-separated tree (HST), which offers a linear approximation with constant distortion. We provide a numerical comparison of several problem formulations and find that with appropriate optimization parameter selection, the quadratic reformulation produces association policies with sum delays that are close to that of the original network utility maximization. We also comment on the more difficult problem when idle base stations (those without associated users) are deactivated.
Enhancing Wireless Information and Power Transfer by Exploiting Multi-Antenna Techniques
Venue: arXiv cs.IT 2015
Year: 2015

This paper reviews emerging wireless information and power transfer (WIPT) technique with an emphasis on its performance enhancement employing multi-antenna techniques. Compared to traditional wireless information transmission, WIPT faces numerous challenges. First, it is more susceptible to channel fading and path loss, resulting in a much shorter power transfer distance. Second, it gives rise to the issue on how to balance spectral efficiency for information transmission and energy efficiency for power transfer in order to obtain an optimal tradeoff. Third, there exists a security issue for information transmission in order to improve power transfer efficiency. In this context, multi-antenna techniques, e.g., energy beamforming, are introduced to solve these problems by exploiting spatial degree of freedom. This article provides a tutorial on various aspects of multi-antenna based WIPT techniques, with a focus on tackling the challenges by parameter optimization and protocol design. In particular, we investigate the WIPT tradeoffs based on two typical multi-antenna techniques, namely limited feedback multi-antenna technique for short-distance transfer and large-scale multiple-input multiple-output (LS-MIMO, also known as massive MIMO) technique for long-distance transfer. Finally, simulation results validate the effectiveness of the proposed schemes.
A H-K Clustering Algorithm For High Dimensional Data Using Ensemble Learning
Venue: arXiv cs.DB 2015
Year: 2015

Advances made to the traditional clustering algorithms solves the various problems such as curse of dimensionality and sparsity of data for multiple attributes. The traditional H-K clustering algorithm can solve the randomness and apriority of the initial centers of K-means clustering algorithm. But when we apply it to high dimensional data it causes the dimensional disaster problem due to high computational complexity. All the advanced clustering algorithms like subspace and ensemble clustering algorithms improve the performance for clustering high dimension dataset from different aspects in different extent. Still these algorithms will improve the performance form a single perspective. The objective of the proposed model is to improve the performance of traditional H-K clustering and overcome the limitations such as high computational complexity and poor accuracy for high dimensional data by combining the three different approaches of clustering algorithm as subspace clustering algorithm and ensemble clustering algorithm with H-K clustering algorithm.
A Comparative Study of Polar Code Constructions for the AWGN Channel
Venue: arXiv cs.IT 2015
Year: 2015

We present a comparative study of the performance of various polar code constructions in an additive white Gaussian noise (AWGN) channel. A polar code construction is any algorithm that selects $K$ best among $N$ possible polar bit-channels at the design signal-to-noise-ratio (design-SNR) in terms of bit error rate (BER). Optimal polar code construction is hard and therefore many suboptimal polar code constructions have been proposed at different computational complexities. Polar codes are also non-universal meaning the code changes significantly with the design-SNR. However, it is not known which construction algorithm at what design-SNR constructs the best polar codes. We first present a comprehensive survey of all the well-known polar code constructions along with their full implementations. We then propose a heuristic algorithm to find the best design-SNR for constructing best possible polar codes from a given construction algorithm. The proposed algorithm involves a search among several possible design-SNRs. We finally use our algorithm to perform a comparison of different construction algorithms using extensive simulations. We find that all polar code construction algorithms generate equally good polar codes in an AWGN channel, if the design-SNR is optimized.
Open-Source Software Implications in the Competitive Mobile Platforms Market
Venue: arXiv cs.SE 2015
Year: 2015

The era of the PC platform left a legacy of competitive strategies for the future technologies to follow. However, this notion became more complicated, once the future grew out to be a present with huge bundle of innovative technologies, Internet capabilities, communication possibilities, and ease in life. A major step of moving from a product phone to a smart phone, eventually to a mobile device has created a new industry with humongous potential for further developments. The current mobile platform market is witnessing a platforms-war with big players such as Apple, Google, Nokia and Microsoft in a major role. An important aspect of today's mobile platform market is the contributions made through open source initiatives which promote innovation. This paper gives an insight into the open-source software strategies of the leading players and its implications on the market. It first gives a precise overview of the past leading to the current mobile platform market share state. Then it briefs about the open-source software components used and released by Apple, Google and Nokia platforms, leading to their mobile platform strategies with regard to open source. Finally, the paper assesses the situation from the point of view of communities of software developers complementing each platform. The authors identified relevant implications of the open-source phenomenon in the mobile-industry.
Shield Synthesis: Runtime Enforcement for Reactive Systems
Venue: arXiv cs.LO 2015
Year: 2015

Scalability issues may prevent users from verifying critical properties of a complex hardware design. In this situation, we propose to synthesize a "safety shield" that is attached to the design to enforce the properties at run time. Shield synthesis can succeed where model checking and reactive synthesis fail, because it only considers a small set of critical properties, as opposed to the complex design, or the complete specification in the case of reactive synthesis. The shield continuously monitors the input/output of the design and corrects its erroneous output only if necessary, and as little as possible, so other non-critical properties are likely to be retained. Although runtime enforcement has been studied in other domains such as action systems, reactive systems pose unique challenges where the shield must act without delay. We thus present the first shield synthesis solution for reactive hardware systems and report our experimental results. This is an extended version of [5], featuring an additional appendix.
A Flexible Framework for Defining, Representing and Detecting Changes on the Data Web
Venue: arXiv cs.DB 2015
Year: 2015

The dynamic nature of Web data gives rise to a multitude of problems related to the identification, computation and management of the evolving versions and the related changes. In this paper, we consider the problem of change recognition in RDF datasets, i.e., the problem of identifying, and when possible give semantics to, the changes that led from one version of an RDF dataset to another. Despite our RDF focus, our approach is sufficiently general to engulf different data models that can be encoded in RDF, such as relational or multi-dimensional. In fact, we propose a flexible, extendible and data-model-independent methodology of defining changes that can capture the peculiarities and needs of different data models and applications, while being formally robust due to the satisfaction of the properties of completeness and unambiguity. Further, we propose an ontology of changes for storing the detected changes that allows automated processing and analysis of changes, cross-snapshot queries (spanning across different versions), as well as queries involving both changes and data. To detect changes and populate said ontology, we propose a customizable detection algorithm, which is applicable to different data models and applications requiring the detection of custom, user-defined changes. Finally, we provide a proof-of-concept application and evaluation of our framework for different data models.
Watermarking PDF Documents using Various Representations of Self-inverting Permutations
Venue: arXiv cs.MM 2015
Year: 2015

This work provides to web users copyright protection of their Portable Document Format (PDF) documents by proposing efficient and easily implementable techniques for PDF watermarking; our techniques are based on the ideas of our recently proposed watermarking techniques for software, image, and audio, expanding thus the digital objects that can be efficiently watermarked through the use of self-inverting permutations. In particular, we present various representations of a self-inverting permutation $π^*$ namely 1D-representation, 2D-representation, and RPG-representation, and show that theses representations can be efficiently applied to PDF watermarking. Indeed, we first present an audio-based technique for marking a PDF document $T$ by exploiting the 1D-representation of a permutation $π^*$, and then, since pages of a PDF document $T$ are 2D objects, we present an image-based algorithm for encoding $π^*$ into $T$ by first mapping the elements of $π^*$ into a matrix $A^*$ and then using the information stored in $A^*$ to mark invisibly specific areas of PDF document $T$. Finally, we describe a graph-based watermarking algorithm for embedding a self-inverting permutation $π^*$ into the document structure of a PDF file $T$ by exploiting the RPG-representation of $π^*$ and the structure of a PDF document. We have evaluated the embedding and extracting algorithms by testing them on various and different in characteristics PDF documents.
Assessing Whole-Body Operational Space Control in a Point-Foot Series Elastic Biped: Balance on Split Terrain and Undirected Walking
Venue: arXiv cs.RO 2015
Year: 2015

In this paper we present advancements in control and trajectory generation for agile behavior in bipedal robots. We demonstrate that Whole-Body Operational Space Control (WBOSC), developed a few years ago, is well suited for achieving two types of agile behaviors, namely, balancing on a high pitch split terrain and achieving undirected walking on flat terrain. The work presented here is the first implementation of WBOSC on a biped robot, and more specifically a biped robot with series elastic actuators. We present and analyze a new algorithm that dynamically balances point foot robots by choosing footstep placements. Dealing with the naturally unstable dynamics of these type of systems is a difficult problem that requires both the controller and the trajectory generation algorithm to operate quickly and efficiently. We put forth a comprehensive development and integration effort: the design and construction of the biped system and experimental infrastructure, a customization of WBOSC for the agile behaviors, and new trajectory generation algorithms. Using this custom built controller, we conduct, for first time, an experiment in which a biped robot balances in a high pitch split terrain, demonstrating our ability to precisely regulate internal forces using force sensing feedback techniques. Finally, we demonstrate the stabilizing capabilities of our online trajectory generation algorithm in the physics-based simulator and through physical experiments with a planarized locomotion setup.
The Strategic Formation of Multi-Layer Networks
Venue: arXiv cs.GT 2015
Year: 2015

We study the strategic formation of multi-layer networks, where each layer represents a different type of relationship between the nodes in the network and is designed to maximize some utility that depends on the topology of that layer and those of the other layers. We start by generalizing distance-based network formation to the two-layer setting, where edges are constructed in one layer (with fixed cost per edge) to minimize distances between nodes that are neighbors in another layer. We show that designing an optimal network in this setting is NP-hard. Despite the underlying complexity of the problem, we characterize certain properties of the optimal networks. We then formulate a multi-layer network formation game where each layer corresponds to a player that is optimally choosing its edge set in response to the edge sets of the other players. We consider utility functions that view the different layers as strategic substitutes. By applying our results about optimal networks, we show that players with low edge costs drive players with high edge costs out of the game, and that hub-and-spoke networks that are commonly observed in transportation systems arise as Nash equilibria in this game.
Transport Protocols in Cognitive Radio Networks: A Survey
Venue: arXiv cs.NI 2015
Year: 2015

Cognitive radio networks (CRNs) have emerged as a promising solution to enhance spectrum utilization by using unused or less used spectrum in radio environments. The basic idea of CRNs is to allow secondary users (SUs) access to licensed spectrum, under the condition that the interference perceived by the primary users (PUs) is minimal. In CRNs, the channel availability is uncertainty due to the existence of PUs, resulting in intermittent communication. Transmission control protocol (TCP) performance may significantly degrade in such conditions. To address the challenges, some transport protocols have been proposed for reliable transmission in CRNs. In this paper we survey the state-of-the-art transport protocols for CRNs. We firstly highlight the unique aspects of CRNs, and describe the challenges of transport protocols in terms of PU behavior, spectrum sensing, spectrum changing and TCP mechanism itself over CRNs. Then, we provide a summary and comparison of existing transport protocols for CRNs. Finally, we discuss several open issues and research challenges. To the best of our knowledge, our work is the first survey on transport protocols for CRNs.