In the standard Freeze-Tag Problem (FTP), an initially awake robot (the source) is in charge of waking up a swarm of sleeping robots by moving towards them, given that all the awake robots can participate in the awakening process. The goal is to minimize the makespan to wake up all robots assuming they move at unit speed. In this paper we introduce the Freeze-Tag-with-Return Problem (FTRP) variant, where the robots must eventually return to their initial positions. In the Euclidean plane with n sleeping robots lying on the unit disk centered at the initial position of the source, we show a non-trivial relationship between FTP and FTRP by proving that the difference between the optimal makespan of both problems never exceeds 1.959, and is at least 1.732 in the worst-case. We also present several upper and lower bounds on the optimal makespan. In particular, we show that if the sleeping robots are in convex positions, then the optimal makespan is at most 2 + 2√2, which is achieved by some instances. From an algorithmic point-of-view, we present single-exponential algorithms for general distance functions. In metric spaces, these algorithms are asymptotically optimal under the ETH, which we show via an NP-hardness reduction on unweighted graphs.

The Freeze-Tag Problem consists in waking up a swarm of robots starting with one initially awake robot. While there exists a wide literature on the centralized setting, where the locations of the robots are known in advance, we focus on the distributed version where the locations of the robots, P, are unknown, and where awake robots only detect other robots up to distance 1. Assuming that moving at distance δ takes a time δ, we show that waking up the whole swarm takes O(ρ + ℓ2 log(ρ/ℓ)), where ρ is the largest distance from the initial robot to any point of P, and ℓ is the connectivity threshold of P. Moreover, the result is complemented by a matching lower bound. We also provide other distributed algorithms, complemented with lower bounds, whenever each robot has a bounded amount of energy.

The Freeze-Tag Problem, introduced in Arkin et al. (SODA'02) consists of waking up a swarm of n robots, starting from a single active robot. In the basic geometric version, every robot is given coordinates in the plane. As soon as a robot is awakened, it can move towards inactive robots to wake them up. The goal is to minimize the makespan of the last robot, the makespan. Despite significant progress on the computational complexity of this problem and on approximation algorithms, the characterization of exact bounds on the makespan remains one of the main open questions. In this paper, we settle this question for the 𝓁₁-norm, showing that a makespan of at most 5r can always be achieved, where r is the maximum distance between the initial active robot and any sleeping robot. Moreover, a schedule achieving a makespan of at most 5r can be computed in time O(n). Both bounds, the time and the makespan are optimal. Our results also imply for the 𝓁₂-norm a new upper bound of 5√2r ≈ 7.07r on the makespan, improving the best known bound of (5+2√2+√5)r ≈ 10.06r. Along the way, we introduce new linear time wake-up strategies, that apply to any norm and show that an optimal bound on the makespan can always be achieved by a schedule computable in linear time.

This paper deals with the computation of d-dimensional multicriteria shortest paths. In a weighted graph with arc weights represented by vectors, the cost of a path is the vector sum of the weights of its arcs. For a given pair consisting of a source s and a destination t, a path P dominates a path Q if and only if P’s cost is component-wise smaller than or equal to Q’s cost. The set of Pareto paths, or Pareto set, from s to t is the set of paths that are not dominated. The computation time of the Pareto paths can be prohibitive whenever the set of Pareto paths is large. We propose in this article new algorithms to compute approximated Pareto paths in any dimension. For d = 2, we exhibit the first approximation algorithm, called Frame, whose output is guaranteed to be always a subset of the Pareto set. Finally, we provide a small experimental study in order to confirm the relevance of our Frame algorithm.

Heatmap visualization is a well-known type of visualization to alleviate the overplot problem of point visualization. As such, it is well suited to visualize Big Data. In order to tackle the velocity problem of Big Data, one has to leverage streaming computations. Recently, canopy clustering was shown to be well suited for Big Data heatmap visualization. In this article, we present how to design a streaming algorithm to compute canopy clustering using Apache Spark. This result is directly applicable to be included into a lambda architecture.

Given a table T with a set of dimensions D, the skycube of T is the union of all skylines obtained by considering each of the subsets of D (subspaces). The number of these skylines is exponential w.r.t D. To make the skycube practically useful, two lines of research have been pursued so far: the first one aims to propose efficient algorithms for computing it and the second one considers either that the skycube is too large to be computed in a reasonable time or it requires too much memory space to be stored. They therefore propose skycube summarization techniques to reduce time and space consumption. Intuitively, previous efforts have been devoted to compute or summarize the following information: ``for every tuple t, list the skylines where t belongs to". In this paper, we consider the complementary statement, i.e., ``for every tuple t, list the skylines where t does not belong to". This is what we call the negative skycube. Despite the apparent equivalence between these two statements, our analysis and extensive experiments show that these two points of views do not lead to the same behavior of the related algorithms. More specifically, our proposal shows that (i) the negative summary can be obtained much faster than state of the art techniques for positive summaries, (ii) in general, it consumes less space, (iii) skyline queries evaluation using this summary are much faster, (iv) the positive skycube can be obtained much more rapidly than state of the art algorithms, and (v) it can be used for a larger class of queries, namely k-domination skylines.

Let T be a table of n points described by a set of d attributes/dimensions. Let p, q ∈ T. p dominates q iff it is better than q in every dimension and there exists at least one attribute for which p is strictly better than p. p is a skyline point of T iff it is not dominated by any point of T. A skyline query returns the set of all skyline points. In order to integrate Skyline queries into database management systems, deriving an estimation of the skyline cardinality is important for query optimization purposes. We propose techniques for estimating skyline cardinality when data distribution is known. We first provide an unbiased estimator which requires one traversal of the whole data which is much faster than computing the exact skyline. Then, we show that this estimator can be used on a sample of the underlying data while preserving the estimation quality, i.e., it is still unbiased. Next, we provide a convergent estimator which does not require any data access but the data distribution. It estimates skyline cardinality expectation for those data sets respecting data distribution. The advantages of these solutions are their ease of implementation and, by contrast to other proposals, no costly subskyline queries are required. Our solutions are implemented and some experiments are reported showing both the accuracy of the estimations and the execution time efficiency by which they are obtained.

Given a table T ( Id , D 1 , …, D d ), the skycube of T is the set of skylines with respect to to all nonempty subsets (subspaces) of the set of all dimensions { D 1 , …, D d }. To optimize the evaluation of any skyline query, the solutions proposed so far in the literature either (i) precompute all of the skylines or (ii) use compression techniques so that the derivation of any skyline can be done with little effort. Even though solutions (i) are appealing because skyline queries have optimal execution time, they suffer from time and space scalability because the number of skylines to be materialized is exponential with respect to d . On the other hand, solutions (ii) are attractive in terms of memory consumption, but as we show, they also have a high time complexity. In this article, we make contributions to both kinds of solutions. We first observe that skyline patterns are monotonic. This property leads to a simple yet efficient solution for full and partial skycube materialization when the skyline with respect to all dimensions, the topmost skyline, is small. On the other hand, when the topmost skyline is large relative to the size of the input table, it turns out that functional dependencies, a fundamental concept in databases, uncover a monotonic property between skylines. Equipped with this information, we show that closed attributes sets are fundamental for partial and full skycube materialization. Extensive experiments with real and synthetic datasets show that our solutions generally outperform state-of-the-art algorithms.

This paper investigates compact routing schemes that are very efficient with respect to the memory used to store routing tables in internet-like graphs. We propose a new compact name-independent routing scheme whose theoretically proven average memory per node is upper-bounded by nγ, with constant γ < 1/2, while the maximum memory of any node is bounded by √n and the maximum stretch of any route is bounded by 5. These bounds are given for the Random Power Low Graphs (RPLG) and hold with high probability. Moreover, we experimentally show that our scheme is very efficient in terms of stretch and memory in internet-like graphs (CAIDA and other maps). We complete this study by comparing our analytic and experimental results to several compact routing schemes. In particular, we show that the average memory requirements is better by at least one order of magnitude than previous schemes for CAIDA maps on 16K nodes.

The border concept has been introduced by Mannila and Toivonen in their seminal paper [20]. This concept finds many applications, e.g maximal frequent itemsets, minimal functional dependencies, emerging patterns between consecutive database instances and materialized view selection. For large transactions and relational databases defined on n items or attributes, the running time of any border computations are mainly dominated by the time T (for standard sequential algorithms) required to test the interestingness, in general the frequencies, of sets of candidates.

We study the problem of finding a destination node t by a mobile agent in an unreliable network having the structure of an unweighted graph, in a model first proposed by Hanusse et al [20, 21]. Each node of the network is able to give advice concerning the next node to visit so as to go closer to the target t. Unfortunately, exactly k of the nodes, called liars, give advice which is incorrect. It is known that for an n-node graph G of maximum degree Δ ≥ 3, reaching a target at a distance of d from the initial location may require an expected time of 2Ω(min d,k}), for any d,k = O(log n), even when G is a tree.

A view selection algorithm takes as input a fact table and computes a set of views to store in order to speed up queries. The performance of view selection algorithm is usually measured by three criteria: (1) the amount of memory to store the selected views, (2) the query response time and (3) the time complexity of this algorithm. The two first measurements deal with the output of the algorithm. No existing solutions give good trade-off between amount of memory and queries cost with a small time complexity. We propose in this paper an algorithm guaranteeing a constant approximation factor of queries response time with respect to the optimal solution. Moreover, the time complexity for a D-dimensional fact table is O (D * 2D) corresponding to the fastest known algorithm. We provide an experimental comparison with two other well known algorithms showing that our approach also gives good performance in terms of memory.

No abstract available.

In this paper, we present I-PACK, a deterministic layout algorithm for embedding a data set X in 2D provided that distances (duv)u,v?X between data items are given or can be computed. The layout reflects well similarities and dissimilarities between items and it is computed in quasi-linear time. Experimental comparisons with other multidimensional scaling algorithms show that : i) our algorithmhas similar performance when the aspect ratio A = \frac{{\max _{u,v} (\delta uv)}} {{\min _{u,v} (\delta uv)}} is small (i.e. log2A \lt 10) and ii) the larger the aspect ratio, the better I-PACK performs with respect to otherMDS algorithms. This is also true when data can be “naturally” clustered.

We investigate the problem of optimizing the routing performance of a virtual network by adding extra random links. Our asynchronous and distributed algorithm ensures, by adding a single extra link per node, that the resulting network is a navigable small world, i.e., in which greedy routing, using the distance in the original network, computes paths of polylogarithmic length between any pair of nodes with probability 1-O(1/n). Previously known small world augmentation processes require the global knowledge of the network and centralized computations, which is unrealistic for large decentralized networks. Our algorithm, based on a careful multi-layer sampling of the nodes and the construction of a light overlay network, bypasses these limitations. For bounded growth graphs, i.e., graphs where, for any node u and any radius r the number of nodes within distance 2r from u is at most a constant times the number of nodes within distance r, our augmentation process proceeds with high probability in O(log n log D) communication rounds, with O(log n log D) messages of size O(log n) bits sent per node and requiring only O(log n log D) bit space in each node, where n is the number of nodes, and D the diameter. In particular, with the only knowledge of original distances, greedy routing computes, between any pair of nodes in the augmented network, a path of length at most O(log2 n log2 D) with probability 1 - O(1/n), and of expected length O(log n log2 D). Hence, we provide a distributed scheme to augment any bounded growth graph into a small world with high probability in polylogarithmic time while requiring polylogarithmic memory. We consider that the existence of such a lightweight process might be a first step towards the definition of a more general construction process that would validate Kleinberg's model as a plausible explanation for the small world phenomenon in large real interaction networks.