OpenRaiser/Intern-Atlas huggingface dataset:
Implicit Coordination of Caches in Small Cell Networks under Unknown Popularity Profiles
Venue: arXiv cs.NI 2018
Year: 2018

We focus on a dense cellular network, in which a limited-size cache is available at every Base Station (BS). In order to optimize the overall performance of the system in such scenario, where a significant fraction of the users is covered by several BSs, a tight coordination among nearby caches is needed. To this end, this pape introduces a class of simple and fully distributed caching policies, which require neither direct communication among BSs, nor a priori knowledge of content popularity. Furthermore, we propose a novel approximate analytical methodology to assess the performance of interacting caches under such policies. Our approach builds upon the well known characteristic time approximation and provides predictions that are surprisingly accurate (hardly distinguishable from the simulations) in most of the scenarios. Both synthetic and trace-driven results show that the our caching policies achieve excellent performance (in some cases provably optimal). They outperform state-of-the-art dynamic policies for interacting caches, and, in some cases, also the greedy content placement, which is known to be the best performing polynomial algorithm under static and perfectly-known content popularity profiles.
Large Scale Local Online Similarity/Distance Learning Framework based on Passive/Aggressive
Venue: arXiv cs.LG 2018
Year: 2018

Similarity/Distance measures play a key role in many machine learning, pattern recognition, and data mining algorithms, which leads to the emergence of metric learning field. Many metric learning algorithms learn a global distance function from data that satisfy the constraints of the problem. However, in many real-world datasets that the discrimination power of features varies in the different regions of input space, a global metric is often unable to capture the complexity of the task. To address this challenge, local metric learning methods are proposed that learn multiple metrics across the different regions of input space. Some advantages of these methods are high flexibility and the ability to learn a nonlinear mapping but typically achieves at the expense of higher time requirement and overfitting problem. To overcome these challenges, this research presents an online multiple metric learning framework. Each metric in the proposed framework is composed of a global and a local component learned simultaneously. Adding a global component to a local metric efficiently reduce the problem of overfitting. The proposed framework is also scalable with both sample size and the dimension of input data. To the best of our knowledge, this is the first local online similarity/distance learning framework based on PA (Passive/Aggressive). In addition, for scalability with the dimension of input data, DRP (Dual Random Projection) is extended for local online learning in the present work. It enables our methods to be run efficiently on high-dimensional datasets, while maintains their predictive performance. The proposed framework provides a straightforward local extension to any global online similarity/distance learning algorithm based on PA.
Optimal Control of Networks in the presence of Attackers and Defenders
Venue: arXiv cs.SY 2018
Year: 2018

We consider the problem of a dynamical network whose dynamics is subject to external perturbations (`attacks') locally applied at a subset of the network nodes. We assume that the network has an ability to defend itself against attacks with appropriate countermeasures, which we model as actuators located at (another) subset of the network nodes. We derive the optimal defense strategy as an optimal control problem. We see that the network topology, as well as the distribution of attackers and defenders over the network affect the optimal control solution and the minimum control energy. We study the optimal control defense strategy for several network topologies, including chain networks, star networks, ring networks, and scale free networks.
Global Cryptodemocracy is Possible and Desirable
Venue: arXiv cs.CY 2018
Year: 2018

A contribution to a Globalcit debate entitled: Cloud Communities: The Dawn of Global Citizenship?
Spatio-temporal Trajectory Dataset Privacy Based on Network Traffic Control
Venue: arXiv cs.CR 2018
Year: 2018

Collection of user's location and trajectory information that contains rich personal privacy in mobile social networks has become easier for attackers. Network traffic control is an important network system which can solve some security and privacy problems. In this paper, we consider a network traffic control system as a trusted third party and use differential privacy for protecting more personal trajectory data. We studied the influence of the high dimensionality and sparsity of trajectory data sets based on the availability of the published results. Based on similarity point aggregation reconstruction ideas and a prefix tree model, we proposed a hybrid publishing method of differential privacy spatiotemporal trajectory data sets APTB.
Low Complexity Secure Code (LCSC) Design for Big Data in Cloud Storage Systems
Venue: arXiv cs.IT 2018
Year: 2018

In the era of big data, reducing the computational complexity of servers in data centers will be an important goal. We propose Low Complexity Secure Codes (LCSCs) that are specifically designed to provide information theoretic security in cloud distributed storage systems. Unlike traditional coding schemes that are designed for error correction capabilities, these codes are only designed to provide security with low decoding complexity. These sparse codes are able to provide (asymptotic) perfect secrecy similar to Shannon cipher. The simultaneous promise of low decoding complexity and perfect secrecy make these codes very desirable for cloud storage systems with large amount of data. The design is particularly suitable for large size archival data such as movies and pictures. The complexity of these codes are compared with traditional encryption techniques.
Red-Black Trees with Constant Update Time
Venue: arXiv cs.DS 2018
Year: 2018

We show how a few modifications to the red-black trees allow for $O(1)$ worst-case update time (once the position of the inserted or deleted element is known). The resulting structure is based on relaxing some of the properties of the red-black trees while guaranteeing that the height remains logarithmic with respect to the number of nodes. Compared to the other search trees with constant update time, our tree is the first to provide a tailored deletion procedure without using the global rebuilding technique. In addition, our structure is very simple to implement and allows for a simpler proof of correctness than those alternative trees.
Automatic Prediction of Building Age from Photographs
Venue: arXiv cs.CV 2018
Year: 2018

We present a first method for the automated age estimation of buildings from unconstrained photographs. To this end, we propose a two-stage approach that firstly learns characteristic visual patterns for different building epochs at patch-level and then globally aggregates patch-level age estimates over the building. We compile evaluation datasets from different sources and perform an detailed evaluation of our approach, its sensitivity to parameters, and the capabilities of the employed deep networks to learn characteristic visual age-related patterns. Results show that our approach is able to estimate building age at a surprisingly high level that even outperforms human evaluators and thereby sets a new performance baseline. This work represents a first step towards the automated assessment of building parameters for automated price prediction.
Energy Minimization for Wireless Communication with Rotary-Wing UAV
Venue: arXiv cs.IT 2018
Year: 2018

This paper studies unmanned aerial vehicle (UAV) enabled wireless communication, where a rotarywing UAV is dispatched to send/collect data to/from multiple ground nodes (GNs). We aim to minimize the total UAV energy consumption, including both propulsion energy and communication related energy, while satisfying the communication throughput requirement of each GN. To this end, we first derive an analytical propulsion power consumption model for rotary-wing UAVs, and then formulate the energy minimization problem by jointly optimizing the UAV trajectory and communication time allocation among GNs, as well as the total mission completion time. The problem is difficult to be optimally solved, as it is non-convex and involves infinitely many variables over time. To tackle this problem, we first consider the simple fly-hover-communicate design, where the UAV successively visits a set of hovering locations and communicates with one corresponding GN when hovering at each location. For this design, we propose an efficient algorithm to optimize the hovering locations and durations, as well as the flying trajectory connecting these hovering locations, by leveraging the travelling salesman problem (TSP) and convex optimization techniques. Next, we consider the general case where the UAV communicates also when flying. We propose a new path discretization method to transform the original problem into a discretized equivalent with a finite number of optimization variables, for which we obtain a locally optimal solution by applying the successive convex approximation (SCA) technique. Numerical results show the significant performance gains of the proposed designs over benchmark schemes, in achieving energy-efficient communication with rotary-wing UAVs.
A Holistic Approach for Soundness Verification of Decision-Aware Process Models (extended version)
Venue: arXiv cs.LO 2018
Year: 2018

The last decade has witnessed an increasing transformation in the design, engineering, and mining of processes, moving from a pure control-flow perspective to more integrated models where also data and decisions are explicitly considered. This calls for methods and techniques able to ascertain the correctness of such integrated models. Differently from previous approaches, which mainly focused on the local interplay between decisions and their corresponding outgoing branches, we introduce a holistic approach to verify the end-to-end soundness of a Petri net-based process model, enriched with case data and decisions. In particular, we present an effective, implemented technique that verifies soundness by translating the input net into a colored Petri net with bounded color domains, which can then be analyzed using conventional tools. We prove correctness and termination of this technique. In addition, we relate our contribution to recent results on decision-aware soundness, showing that our approach can be readily applied there.
Formal Ways for Measuring Relations between Concepts in Conceptual Spaces
Venue: arXiv cs.AI 2018
Year: 2018

The highly influential framework of conceptual spaces provides a geometric way of representing knowledge. Instances are represented by points in a high-dimensional space and concepts are represented by regions in this space. In this article, we extend our recent mathematical formalization of this framework by providing quantitative mathematical definitions for measuring relations between concepts: We develop formal ways for computing concept size, subsethood, implication, similarity, and betweenness. This considerably increases the representational capabilities of our formalization and makes it the most thorough and comprehensive formalization of conceptual spaces developed so far.
Coding of Graphs with Application to Graph Anomaly Detection
Venue: arXiv cs.IT 2018
Year: 2018

This paper has dual aims. First is to develop practical universal coding methods for unlabeled graphs. Second is to use these for graph anomaly detection. The paper develops two coding methods for unlabeled graphs: one based on the degree distribution, the second based on the triangle distribution. It is shown that these are efficient for different types of random graphs, and on real-world graphs. These coding methods is then used for detecting anomalous graphs, based on structure alone. It is shown that anomalous graphs can be detected with high probability.
Complexity of the CNF-satisfiability problem
Venue: arXiv cs.CC 2018
Year: 2018

This paper is devoted to the complexity of the Boolean satisfiability problem. We consider a version of this problem, where the Boolean formula is specified in the conjunctive normal form. We prove an unexpected result that the CNF-satisfiability problem can be solved by a deterministic Turing machine in polynomial time.
A Performance Analysis Model of TCP over Multiple Heterogeneous Paths for 5G Mobile Services
Venue: arXiv cs.NI 2018
Year: 2018

Driven by the primary requirement of emerging 5G mobile services, the demand for concurrent multipath transfer (CMT) is still prominent. Yet, multipath transport protocols are not widely adopted and TCP-based CMT schemes will still be in dominant position in 5G. However, the performance of TCP flow transferred over multiple heterogeneous paths is prone to the link quality asymmetry, the extent of which was revealed to be significant by our field investigation. In this paper, we present a performance analysis model for TCP over multiple heterogeneous paths in 5G scenarios, where both bandwidth and delay asymmetry are taken into consideration. The evaluation adopting parameters from field investigation shows that the proposed model can achieve high accuracy in practical environments. Some interesting inferences can be drawn from the proposed model, such as the dominant factor that affect the performance of TCP over heterogeneous networks, and the criteria of determining the appropriate number of links to be used under different circumstances of path heterogeneity. Thus, the proposed model can provide a guidance to the design of TCP-based CMT solutions for 5G mobile services.
Bus Trajectory-Based Street-Centric Routing for Message Delivery in Urban Vehicular Ad hoc Networks
Venue: arXiv cs.NI 2018
Year: 2018

This paper focuses on the routing algorithm for the communications between vehicles and places in urban VANET. As one of the basic transportation facilities in an urban setting, buses periodically run along their fixed routes and widely cover city streets. The trajectory of bus lines can be seen as a sub map of a city. Based on the characters of bus networks, we propose a bus trajectory-based street-centric routing algorithm (BTSC), which uses bus as main relay to deliver message. In BTSC, we build a routing graph based on the trajectories of bus lines by analyzing the probability of bus appearing on every street. We propose two novel concepts, i.e. the probability of street consistency (PSC) and the probability of path consistency (PPC) which is used as metrics to determine routing paths for message delivery. This aims to choose the best path with higher density of busses and lower probability of transmission direction deviating from the routing path. In order to improve the bus forwarding opportunity, we design a bus-based forwarding strategy with ant colony optimization (FACO) to find a reliable and steady multi-hop link between two relay buses in order to decrease end-to-end delay. BTSC makes the improvements in the selection of routing path and the strategy of message forwarding. Simulation results show that our proposed routing algorithm has a better performance in transmission ratio, transmission delay and adaptability to different networks.
Efficient Reciprocal Collision Avoidance between Heterogeneous Agents Using CTMAT
Venue: arXiv cs.AI 2018
Year: 2018

We present a novel algorithm for reciprocal collision avoidance between heterogeneous agents of different shapes and sizes. We present a novel CTMAT representation based on medial axis transform to compute a tight fitting bounding shape for each agent. Each CTMAT is represented using tuples, which are composed of circular arcs and line segments. Based on the reciprocal velocity obstacle formulation, we reduce the problem to solving a low-dimensional linear programming between each pair of tuples belonging to adjacent agents. We precompute the Minkowski Sums of tuples to accelerate the runtime performance. Finally, we provide an efficient method to update the orientation of each agent in a local manner. We have implemented the algorithm and highlight its performance on benchmarks corresponding to road traffic scenarios and different vehicles. The overall runtime performance is comparable to prior multi-agent collision avoidance algorithms that use circular or elliptical agents. Our approach is less conservative and results in fewer false collisions.
Tight Lower Bounds for List Edge Coloring
Venue: arXiv cs.DS 2018
Year: 2018

The fastest algorithms for edge coloring run in time $2^m n^{O(1)}$, where $m$ and $n$ are the number of edges and vertices of the input graph, respectively. For dense graphs, this bound becomes $2^{Θ(n^2)}$. This is a somewhat unique situation, since most of the studied graph problems admit algorithms running in time $2^{O(n\log n)}$. It is a notorious open problem to either show an algorithm for edge coloring running in time $2^{o(n^2)}$ or to refute it, assuming Exponential Time Hypothesis (ETH) or other well established assumption. We notice that the same question can be asked for list edge coloring, a well-studied generalization of edge coloring where every edge comes with a set (often called a list) of allowed colors. Our main result states that list edge coloring for simple graphs does not admit an algorithm running in time $2^{o(n^2)}$, unless ETH fails. Interestingly, the algorithm for edge coloring running in time $2^m n^{O(1)}$ generalizes to the list version without any asymptotic slow-down. Thus, our lower bound is essentially tight. This also means that in order to design an algorithm running in time $2^{o(n^2)}$ for edge coloring, one has to exploit its special features compared to the list version.
Two attacks on rank metric code-based schemes: RankSign and an Identity-Based-Encryption scheme
Venue: arXiv cs.CR 2018
Year: 2018

RankSign [GRSZ14a] is a code-based signature scheme proposed to the NIST competition for quantum-safe cryptography [AGHRZ17] and, moreover, is a fundamental building block of a new Identity-Based-Encryption (IBE) [GHPT17a]. This signature scheme is based on the rank metric and enjoys remarkably small key sizes, about 10KBytes for an intended level of security of 128 bits. Unfortunately we will show that all the parameters proposed for this scheme in [AGHRZ17] can be broken by an algebraic attack that exploits the fact that the augmented LRPC codes used in this scheme have very low weight codewords. Therefore, without RankSign the IBE cannot be instantiated at this time. As a second contribution we will show that the problem is deeper than finding a new signature in rank-based cryptography, we also found an attack on the generic problem upon which its security reduction relies. However, contrarily to the RankSign scheme, it seems that the parameters of the IBE scheme could be chosen in order to avoid our attack. Finally, we have also shown that if one replaces the rank metric in the [GHPT17a] IBE scheme by the Hamming metric, then a devastating attack can be found.
Multi-Level Steiner Trees
Venue: arXiv cs.DS 2018
Year: 2018

In the classical Steiner tree problem, given an undirected, connected graph $G=(V,E)$ with non-negative edge costs and a set of \emph{terminals} $T\subseteq V$, the objective is to find a minimum-cost tree $E' \subseteq E$ that spans the terminals. The problem is APX-hard; the best known approximation algorithm has a ratio of $ρ= \ln(4)+\varepsilon < 1.39$. In this paper, we study a natural generalization, the \emph{multi-level Steiner tree} (MLST) problem: given a nested sequence of terminals $T_{\ell} \subset \dots \subset T_1 \subseteq V$, compute nested trees $E_{\ell}\subseteq \dots \subseteq E_1\subseteq E$ that span the corresponding terminal sets with minimum total cost. The MLST problem and variants thereof have been studied under various names including Multi-level Network Design, Quality-of-Service Multicast tree, Grade-of-Service Steiner tree, and Multi-Tier tree. Several approximation results are known. We first present two simple $O(\ell)$-approximation heuristics. Based on these, we introduce a rudimentary composite algorithm that generalizes the above heuristics, and determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio using at most $2\ell$ Steiner tree computations. We compare these heuristics experimentally on various instances of up to 500 vertices using three different network generation models. We also present various integer linear programming (ILP) formulations for the MLST problem, and compare their running times on these instances. To our knowledge, the composite algorithm achieves the best approximation ratio for up to $\ell=100$ levels, which is sufficient for most applications such as network visualization or designing multi-level infrastructure.
The Communication Complexity of Local Search
Venue: arXiv cs.GT 2018
Year: 2018

We study the following communication variant of local search. There is some fixed, commonly known graph $G$. Alice holds $f_A$ and Bob holds $f_B$, both are functions that specify a value for each vertex. The goal is to find a local maximum of $f_A+f_B$ with respect to $G$, i.e., a vertex $v$ for which $(f_A+f_B)(v)\geq (f_A+f_B)(u)$ for every neighbor $u$ of $v$. Our main result is that finding a local maximum requires polynomial (in the number of vertices) bits of communication. The result holds for the following families of graphs: three dimensional grids, hypercubes, odd graphs, and degree 4 graphs. Moreover, we provide an \emph{optimal} communication bound of $Ω(\sqrt{N})$ for the hypercube, and for a constant dimensional greed, where $N$ is the number of vertices in the graph. We provide applications of our main result in two domains, exact potential games and combinatorial auctions. First, we show that finding a pure Nash equilibrium in $2$-player $N$-action exact potential games requires polynomial (in $N$) communication. We also show that finding a pure Nash equilibrium in $n$-player $2$-action exact potential games requires exponential (in $n$) communication. The second domain that we consider is combinatorial auctions, in which we prove that finding a local maximum in combinatorial auctions requires exponential (in the number of items) communication even when the valuations are submodular. Each one of the results demonstrates an exponential separation between the non-deterministic communication complexity and the randomized communication complexity of a total search problem.
Fast Single Image Rain Removal via a Deep Decomposition-Composition Network
Venue: arXiv cs.CV 2018
Year: 2018

Rain effect in images typically is annoying for many multimedia and computer vision tasks. For removing rain effect from a single image, deep leaning techniques have been attracting considerable attentions. This paper designs a novel multi-task leaning architecture in an end-to-end manner to reduce the mapping range from input to output and boost the performance. Concretely, a decomposition net is built to split rain images into clean background and rain layers. Different from previous architectures, our model consists of, besides a component representing the desired clean image, an extra component for the rain layer. During the training phase, we further employ a composition structure to reproduce the input by the separated clean image and rain information for improving the quality of decomposition. Experimental results on both synthetic and real images are conducted to reveal the high-quality recovery by our design, and show its superiority over other state-of-the-art methods. Furthermore, our design is also applicable to other layer decomposition tasks like dust removal. More importantly, our method only requires about 50ms, significantly faster than the competitors, to process a testing image in VGA resolution on a GTX 1080 GPU, making it attractive for practical use.