In this paper, we introduce a new data analysis problem that aims to decompose a set of univariate time series into a small set of k base curves of length at most l such that the sum of Fréchet distances of the time series to a "Fréchet combination" of the base curves is minimized. Here, a Fréchet combination allows to combine individually scaled base curves using a k-dimensional traversal. We call the problem of finding a set of optimal base curves the Fréchet decomposition problem and we consider two variants: (a) the base curves can be arbitrary curves of bounded length and (b) the curves come from a given finite set of candidate curves. We think of the Fréchet decomposition problem as a Fréchet variant of principal component analysis. For the case of a single base curve we develop a (1+ε)-approximation algorithm for the Fréchet decomposition problem. Additionally we give an exact algorithm for the projection distance problem that asks to compute the distance of one given time series to a given set of k base curves. This allows us to design an exact algorithm for the Fréchet decomposition problem for general k when curves come from a fixed candidate set.

Single-linkage clustering (SLC) is a fundamental method for hierarchical data analysis. In the distance setting, a $k$-clustering produced by SLC can be obtained by computing a minimum spanning tree (MST) and deleting its $k-1$ heaviest edges. This naturally induces a cost profile for the SLC hierarchy: for each $k\in[n]$, we define $\mathrm{cost}_k$ to be the weight of the resulting $k$-component spanning forest, equivalently, the minimum total weight of any spanning forest with exactly $k$ connected components. The corresponding \emph{SLC cost profile} is $(\mathrm{cost}_1,\ldots,\mathrm{cost}_n)$, and the scalar quantity $\mathrm{cost}(G)=\sum_{k=1}^{n}\mathrm{cost}_k$ is the area under this profile. We study the problem of approximating these quantities in sublinear time. We assume that the input is a weighted graph $G$ of average degree $d$ with edge weights in $\{1,\dots,W\}$, accessed through adjacency-list queries; missing edges are treated as having infinite distance. Our main result is a sampling-based algorithm that outputs a succinct sketch of the entire SLC cost profile in the distance setting. The algorithm runs in $\widetilde{O}(d\sqrt{W}/\varepsilon^3)$ time and returns a sketch from which one can derive estimates $(\widehat{\mathrm{cost}}_1,\ldots,\widehat{\mathrm{cost}}_n)$ satisfying $\sum_{k=1}^{n}\bigl|\widehat{\mathrm{cost}}_k-\mathrm{cost}_k\bigr| \le \varepsilon\,\mathrm{cost}(G)$. Thus, we obtain an $\ell_1$ approximation to the full profile whose error is at most an $\varepsilon$-fraction of the area under the true profile. In particular, this yields a $(1\pm\varepsilon)$-approximation to $\mathrm{cost}(G)$ within the same running time. We also prove a nearly matching lower bound of $Ω(d\sqrt{W}/\varepsilon^2)$ queries for estimating $\mathrm{cost}(G)$.

In the metric k-median problem we are given a finite metric space (X∪ Y, 𝐝) and the objective is to compute a set of k centers C ⊆ Y that minimizes ∑_{p ∈ X} min_{c ∈ C} 𝐝(p,c). In general metric spaces, the best polynomial time algorithm, which is due to Cohen-Addad, Grandoni, Lee, Schwiegelshohn, and Svensson [Vincent Cohen-Addad et al., 2025], computes a (2+ε)-approximation for arbitrary constant ε > 0. However, if the metric space has bounded doubling dimension, a near linear time (1+ε)-approximation algorithm is known due to the work of Cohen-Addad, Feldmann, and Saulpic [Vincent Cohen{-}Addad et al., 2021]. In this paper, we show that the (1+ε)-approximation algorithm can be generalized to the case when either X or Y has bounded doubling dimension (but the other set not). The case when X has bounded doubling dimension is motivated by the assumption that even though X is part of a high-dimensional space, it may be that it is close to a low-dimensional structure. The case when Y has bounded doubling dimension is perhaps more natural. It is motivated by specific clustering problems where the centers are low-dimensional. Specifically, our work in this setting implies the first near linear time approximation algorithm for the (k,𝓁)-median problem under discrete Fréchet distance when 𝓁 is constant. The latter problem is a version of the k-median problem under Fréchet distance when the input consists of time series of z reals and where the centers are time series of 𝓁 reals [Anne Driemel et al., 2016]. Previously, for this problem no (1+ε)-approximation algorithm with running time polynomial in k was known. We also introduce a novel complexity reduction for time series of real values that leads to a similar result for the case of discrete Fréchet distance. In order to solve the case when Y has a bounded doubling dimension, we introduce a form of dimension reduction that replaces points from X by sets of points in Y. To solve the case when X has a bounded doubling dimension, we generalize Talwar’s decomposition [Kunal Talwar, 2004] of doubling metrics to our setting. The running time of our algorithms is 2^{2^t} Õ(n+m) where t = O(ddim log ddim/ε) and where ddim is the doubling dimension of X (resp. Y). The results also extend to the metric (uncapacitated) facility location problem. We believe that our techniques are likely applicable to other problems.

We study the problem of recognizing the spectral cluster structure of a graph in the framework of property testing in the bounded degree model. A graph is defined to be \((k,\phi_{\textrm{in}},\phi_{\textrm{out}})\) - clusterable , if it can be partitioned into no more than \( k \) parts, such that the (inner) conductance of the induced subgraph on each part is at least \(\phi_{\textrm{in}}\) and the (outer) conductance of each part is at most \(\phi_{\textrm{out}}\) . Our main result is a sublinear algorithm with the running time \(\widetilde{O}_{d,k}(\sqrt{n}\cdot\mathrm{poly}(\phi,1/\varepsilon))\) that takes as input an \( n \) -vertex graph with maximum degree bounded by \( d \) , parameters \( k \) , \(\phi\) , \(\varepsilon\) , and with probability at least \(\frac{2}{3}\) , accepts the graph if it is \((k,\phi,O_{d,k}(\varepsilon^{4}\phi^{2}))\) -clusterable, and rejects the graph if it is \(\varepsilon\) -far from \((k,\phi^{*},\psi^{*})\) -clusterable for \(\phi^{*}=O_{d,k}(\frac{\phi^{2}\varepsilon^{4}}{\log n})\) and any \(\psi^{*}\geq 0\) . By the lower bound of \(\Omega(\sqrt{n})\) on the number of queries needed for testing graph expansion, which corresponds to \(k=1\) in our problem, our algorithm is asymptotically optimal up to polylogarithmic factors.

We study the $k$-center problem in the context of individual fairness. Let $P$ be a set of $n$ points in a metric space and $r_x$ be the distance between $x \in P$ and its $\lceil n/k \rceil$-th nearest neighbor. The problem asks to optimize the $k$-center objective under the constraint that, for every point $x$, there is a center within distance $r_x$. We give bicriteria $(\beta,\gamma)$-approximation algorithms that compute clusterings such that every point $x \in P$ has a center within distance $\beta r_x$ and the clustering cost is at most $\gamma$ times the optimal cost. Our main contributions are a deterministic $O(n^2+ kn \log n)$ time $(2,2)$-approximation algorithm and a randomized $O(nk\log(n/\delta)+k^2/\varepsilon)$ time $(10,2+\varepsilon)$-approximation algorithm, where $\delta$ denotes the failure probability. For the latter, we develop a randomized sampling procedure to compute constant factor approximations for the values $r_x$ for all $x\in P$ in subquadratic time; we believe this procedure to be of independent interest within the context of individual fairness.

Property Testing is a formal framework to study the computational power and complexity of sampling from combinatorial objects. A central goal in standard graph property testing is to understand which graph properties are testable with sublinear query complexity. Here, a graph property P is testable with a sublinear query complexity if there is an algorithm that makes a sublinear number of queries to the input graph and accepts with probability at least 2/3, if the graph has property P, and rejects with probability at least 2/3 if it is $\varepsilon$-far from every graph that has property P. In this paper, we introduce a new variant of the bounded degree graph model. In this variant, in addition to the standard representation of a bounded degree graph, we assume that every vertex $v$ has a unique label num$(v)$ from $\{1, \dots, |V|\}$, and in addition to the standard queries in the bounded degree graph model, we also allow a property testing algorithm to query for the label of a vertex (but not for a vertex with a given label). Our new model is motivated by certain graph processes such as a DFS traversal, which assign consecutive numbers (labels) to the vertices of the graph. We want to study which of these numberings can be tested in sublinear time. As a first step in understanding such a model, we develop a \emph{property testing algorithm for discovery times of a DFS traversal} with query complexity $O(n^{1/3}/\varepsilon)$ and for constant $\varepsilon>0$ we give a matching lower bound.

Locality-sensitive hashing (Indyk-Motwani'98) is a classical data structure for approximate nearest neighbor search. It allows, after a close to linear time preprocessing of the input dataset, to find an approximately nearest neighbor of any fixed query in sublinear time in the dataset size. The resulting data structure is randomized and succeeds with high probability for every fixed query independent of the randomness of the data structure. In many modern applications of nearest neighbor search the queries are, however, chosen adaptively. In this paper, we study the robustness of locality-sensitive hashing in Hamming space to adaptive queries. We present a simple adversary that can, under mild assumptions on the initial point set, provably find a query to the approximate near neighbor search data structure that the data structure fails on. Crucially, our adaptive algorithm finds the hard query exponentially faster than random sampling.

Abstract. Let [Formula: see text] be an [Formula: see text]-point metric space. We assume that [Formula: see text] is given in the distance oracle model, that is, [Formula: see text] and for every pair of points [Formula: see text] from [Formula: see text] we can query their distance [Formula: see text] in constant time. A [Formula: see text]- nearest neighbor ([Formula: see text]-NN) graph for [Formula: see text] is a directed graph [Formula: see text] that has an edge to each of [Formula: see text]’s [Formula: see text] nearest neighbors. We use [Formula: see text] to denote the sum of edge weights of [Formula: see text]. In this paper, we study the problem of approximating [Formula: see text] in sublinear time when we are given oracle access to the metric space [Formula: see text] that defines [Formula: see text]. Our goal is to develop an algorithm that solves this problem faster than the time required to compute [Formula: see text]. We first present an algorithm that in [Formula: see text] time with probability at least [Formula: see text] approximates [Formula: see text] to within a factor of [Formula: see text]. Next, we present a more elaborate sublinear algorithm that in time [Formula: see text] computes an estimate [Formula: see text] of [Formula: see text] that satisfies with probability at least [Formula: see text] [Formula: see text], where [Formula: see text] denotes the cost of the minimum spanning tree of [Formula: see text]. Further, we complement these results with near matching lower bounds. We show that any algorithm that for a given metric space [Formula: see text] of size [Formula: see text], with probability at least [Formula: see text], estimates [Formula: see text] to within a [Formula: see text] factor requires [Formula: see text] time. Similarly, any algorithm that with probability at least [Formula: see text] estimates [Formula: see text] to within an additive error term [Formula: see text] requires [Formula: see text] time.

A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clustering, community detection, and analysis of biological and physical networks to name a few (Benson at al., Tsourakakis at al.). In these applications, the cut structure of motifs plays a crucial role as vertices are partitioned into clusters by cuts whose conductance is based on the number of instances of a particular motif, as opposed to just the number of edges, crossing the cuts.In this paper, we introduce the concept of a motif cut sparsifier. We show that one can compute in polynomial time a sparse weighted subgraph $G^{\prime}$ with only $\widetilde{O}\left(n / \epsilon^{2}\right)$ edges such that for every cut, the weighted number of copies of M crossing the cut in $G^{\prime}$ is within a $1+\epsilon$ factor of the number of copies of M crossing the cut in G, for every constant size motif M.Our work carefully combines the viewpoints of both graph sparsification and hypergraph sparsification. We sample edges which requires us to extend and strengthen the concept of cut sparsifiers introduced in the seminal works of Karger and Benczúr et al. to the motif setting. The task of adapting the importance sampling framework common to efficient graph sparsification algorithms to the motif setting turns out to be nontrivial due to the fact that cut sizes in a random subgraph of G depend non-linearly on the sampled edges. To overcome this, we adopt the viewpoint of hypergraph sparsification to define edge sampling probabilities which are derived from the strong connectivity values of a hypergraph whose hyperedges represent motif instances. Finally, an iterative sparsification primitive inspired by both viewpoints is used to reduce the number of edges in G to nearly linear.In addition, we present a strong lower bound ruling out a similar result for sparsification with respect to induced occurrences of motifs1.1The full version of the paper is found at https://arxiv.org/abs/2204.09951

As a fundamental unsupervised learning task, hierarchical clustering has been extensively studied in the past decade. In particular, standard metric formulations as hierarchical $k$-center, $k$-means, and $k$-median received a lot of attention and the problems have been studied extensively in different models of computation. Despite all this interest, not many efficient parallel algorithms are known for these problems. In this paper we introduce a new parallel algorithm for the Euclidean hierarchical $k$-median problem that, when using machines with memory $s$ (for $s\in \Omega(\log^2 (n+\Delta+d))$), outputs a hierarchical clustering such that for every fixed value of $k$ the cost of the solution is at most an $O(\min\{d, \log n\} \log \Delta)$ factor larger in expectation than that of an optimal solution. Furthermore, we also get that for all $k$ simultanuously the cost of the solution is at most an $O(\min\{d, \log n\} \log \Delta \log (\Delta d n))$ factor bigger that the corresponding optimal solution. The algorithm requires in $O\left(\log_{s} (nd\log(n+\Delta))\right)$ rounds. Here $d$ is the dimension of the data set and $\Delta$ is the ratio between the maximum and minimum distance of two points in the input dataset. To the best of our knowledge, this is the first \emph{parallel} algorithm for the hierarchical $k$-median problem with theoretical guarantees. We further complement our theoretical results with an empirical study of our algorithm that shows its effectiveness in practice.

Given a graph G that can be partitioned into k disjoint expanders with outer conductance upper bounded by ∊ « 1, can we efficiently construct a small space data structure that allows quickly classifying vertices of G according to the expander (cluster) they belong to? Formally, we would like an efficient local computation algorithm that misclassifies at most an O(∊) fraction of vertices in every expander. We refer to such a data structure as a spectral clustering oracle. Our main result is a spectral clustering oracle with query time O∗(n1/2+O(∊)) and preprocessing time that provides misclassification error O(∊ log k) per cluster for any ∊ « 1/log k. More generally, query time can be reduced at the expense of increasing the preprocessing time appropriately (as long as the product is about n1+O(∊)) – this in particular gives a nearly linear time spectral clustering primitive. The main technical contribution is a sublinear time oracle that provides dot product access to the spectral embedding of G by estimating distributions of short random walks from vertices in G. The distributions themselves provide a poor approximation to the spectral embedding, but we show that an appropriate linear transformation can be used to achieve high precision dot product access. We give an estimator for this linear transformation and analyze it using spectral perturbation bounds and a novel upper bound on the leverage scores of the spectral embedding matrix of a k-clusterable graph. We then show that dot product access to the spectral embedding is sufficient to design a clustering oracle. At a high level our approach amounts to hyperplane partitioning in the spectral embedding of G, but crucially operates on a nested sequence of carefully defined subspaces in the spectral embedding to achieve per cluster recovery guarantees.

We consider the fundamental question of understanding the relative power of two important computational models: property testing and data streaming. We present a novel framework closely linking these areas in the setting of general graphs in the context of constant-query complexity testing and constant-space streaming. Our main result is a generic transformation of a one-sided error property tester in the random-neighbor model with constant query complexity into a one-sided error property tester in the streaming model with constant space complexity. Previously such a generic transformation was only known for bounded-degree graphs.

$k$-means++ \cite{arthur2007k} is a widely used clustering algorithm that is easy to implement, has nice theoretical guarantees and strong empirical performance. Despite its wide adoption, $k$-means++ sometimes suffers from being slow on large data-sets so a natural question has been to obtain more efficient algorithms with similar guarantees. In this paper, we present such a near linear time algorithm for $k$-means++ seeding. Interestingly our algorithm obtains the same theoretical guarantees as $k$-means++ and significantly improves earlier results on fast $k$-means++ seeding. Moreover, we show empirically that our algorithm is significantly faster than $k$-means++ and obtains solutions of equivalent quality.

Let (X, d) be an n-point metric space. We assume that (X, d) is given in the distance oracle model, that is, X = {1, …, n} and for every pair of points x, y from X we can query their distance d(x, y) in constant time. A k-nearest neighbor (k-NN) graph for (X, d) is a directed graph G = (V, E) that has an edge to each of v's k nearest neighbors. We use cost(G) to denote the sum of edge weights of G. In this paper, we study the problem of approximating cost(G) in sublinear time, when we are given oracle access to the metric space (X, d) that defines G. Our goal is to develop an algorithm that solves this problem faster than the time required to compute G. We first present an algorithm that in Õ∊(n2/k) time with probability at least approximates cost(G) to within a factor of 1 + ∊. Next, we present a more elaborate sublinear algorithm that in time Õϵ(min{nk3/2, n2/k}) computes an estimate of cost(G) that satisfies with probability at least where mst(X) denotes the cost of the minimum spanning tree of (X, d). Further, we complement these results with near matching lower bounds. We show that any algorithm that for a given metric space (X, d) of size n, with probability at least estimates cost(G) to within a 1 + ∊ factor requires Ω(n2/k) time. Similarly, any algorithm that with probability at least estimates cost(G) to within an additive error term ϵ · (mst(X) + cost(X)) requires Ωϵ(min{nk3/2, n2/k}) time.

We develop and analyze a method to reduce the size of a very large set of data points in a high-dimensional Euclidean space $\mathbb{R}^d$ to a small set of weighted points such that the result of a predetermined data analysis task on the reduced set is approximately the same as that for the original point set. For example, computing the first $k$ principal components of the reduced set will return approximately the first $k$ principal components of the original set or computing the centers of a $k$-means clustering on the reduced set will return an approximation for the original set. Such a reduced set is also known as a coreset. The main new feature of our construction is that the cardinality of the reduced set is independent of the dimension $d$ of the input space and that the sets are mergeable [P. K. Agarwal et al., Proceedings of the 31 st ACM SIGMOD-SIGACT-SIGAI Symposium on Principals of Database Systems, 2012, pp. 23--34]. The latter property means that the union of two reduced sets is a reduced set for the union of the two original sets. It allows us to turn our methods into streaming or distributed algorithms using standard approaches. For problems such as $k$-means and subspace approximation the coreset sizes are also independent of the number of input points. Our method is based on data-dependently projecting the points on a low-dimensional subspace and reducing the cardinality of the points inside this subspace using known methods. The proposed approach works for a wide range of data analysis techniques including $k$-means clustering, principal component analysis, and subspace clustering. The main conceptual contribution is a new coreset definition that allows charging costs that appear for every solution to an additive constant.

The problem of characterizing testable graph properties (properties that can be tested with a number of queries independent of the input size) is a fundamental problem in the area of property testing. While there has been some extensive prior research characterizing testable graph properties in the dense graphs model and we have good understanding of the bounded degree graphs model, no similar characterization has been known for general graphs, with no degree bounds. In this paper we take on this major challenge and consider the problem of characterizing all testable graph properties in general planar graphs. We consider the model in which a general planar graph can be accessed by the random neighbor oracle that allows access to any given vertex and access to a random neighbor of a given vertex. We show that, informally, a graph property P is testable with one-sided error for general planar graphs if and only if testing P can be reduced to testing for a finite family of finite forbidden subgraphs. While our presentation focuses on planar graphs, our approach extends easily to general minor-free graphs. Our analysis of the necessary condition relies on a recent construction of canonical testers in the random neighbor oracle model that is applied here to the one-sided error model for testing in planar graphs. The sufficient condition in the characterization reduces the problem to the task of testing H-freeness in planar graphs, and is the main and most challenging technical contribution of the paper: we show that for planar graphs (with arbitrary degrees), the property of being H-free is testable with one-sided error for every finite graph H, in the random neighbor oracle model.

In this paper, we develop a new variant of k-means++ seeding that in expectation achieves a constant approximation guarantee. We obtain this result by a simple combination of k-means++ sampling with a local search strategy. We evaluate our algorithm empirically and show that it also improves the quality of a solution in practice.

One of the most fundamental questions in graph property testing is to characterize the combinatorial structure of properties that are testable with a constant number of queries. We work towards an answer to this question for the bounded-degree graph model introduced in [GR02], where the input graphs have maximum degree bounded by a constant d. In this model, it is known (among other results) that every hyperfinite property is constant-query testable [NS13], where, informally, a graph property is hyperfinite, if for every δ > 0 every graph in the property can be partitioned into small connected components by removing δn edges. In this paper we show that hyperfiniteness plays a role in every testable property, i.e. we show that every testable property is either finite (which trivially implies hyperfiniteness and testability) or contains an infinite hyperfinite subproperty. A simple consequence of our result is that no infinite graph property that only consists of expander graphs is constant-query testable. Based on the above findings, one could ask if every infinite testable non-hyperfinite property might contain an infinite family of expander (or near-expander) graphs. We show that this is not true. Motivated by our counterexample we develop a theorem that shows that we can partition the set of vertices of every bounded degree graph into a constant number of subsets and a separator set, such that the separator set is small and the distribution of k-discs on every subset of a partition class, is roughly the same as that of the partition class if the subset has small expansion.

We obtain the first strong coresets for the k-median and subspace approximation problems with sum of distances objective function, on n points in d dimensions, with a number of weighted points that is independent of both n and d; namely, our coresets have size poly(k/ε). A strong coreset (1+ε)-approximates the cost function for all possible sets of centers simultaneously. We also give efficient nnz(A) + (n+d) poly(k/ε) + exp(poly(k/ε)) time algorithms for computing these coresets. We obtain the result by introducing a new dimensionality reduction technique for coresets that significantly generalizes an earlier result of Feldman, Sohler and Schmidt [FSS13] for squared Euclidean distances to sums of P-th powers of Euclidean distances for constant p≥1.

Graph kernels are applied heavily for the classification of structured data. However, their expressivity is assessed almost exclusively from experimental studies and there is no theoretical justification why one kernel is in general preferable over another. We introduce a theoretical framework for investigating the expressive power of graph kernels, which is inspired by concepts from the area of property testing. We introduce the notion of distinguishability of a graph property by a graph kernel. For several established graph kernels we show that they cannot distinguish essential graph properties. In order to overcome this, we consider a kernel based on k-disc frequencies. We show that this efficiently computable kernel can distinguish fundamental graph properties. Finally, we obtain learning guarantees for nearest neighbor classifiers in our framework.

The spectrum of a network or graph $G=(V,E)$ with adjacency matrix A , consists of the eigenvalues of the normalized Laplacian $L= I - D^-1/2 A D^-1/2 $. This set of eigenvalues encapsulates many aspects of the structure of the graph, including the extent to which the graph posses community structures at multiple scales. We study the problem of approximating the spectrum, $łambda = (łambda_1,\dots,łambda_|V| )$, of G in the regime where the graph is too large to explicitly calculate the spectrum. We present a sublinear time algorithm that, given the ability to query a random node in the graph and select a random neighbor of a given node, computes a succinct representation of an approximation $\widetilde łambda = (\widetilde łambda_1,\dots,\widetilde łambda_|V| )$, such that $\|\widetilde łambda - łambda\|_1 łe ε |V|$. Our algorithm has query complexity and running time $exp(O(1/\eps))$, which is independent of the size of the graph, $|V|$. We demonstrate the practical viability of our algorithm on synthetically generated graphs, and on 15 different real-world graphs from the Stanford Large Network Dataset Collection, including social networks, academic collaboration graphs, and road networks. For the smallest of these graphs, we are able to validate the accuracy of our algorithm by explicitly calculating the true spectrum; for the larger graphs, such a calculation is computationally prohibitive. The spectra of these real-world networks reveal insights into the structural similarities and differences between them, illustrating the potential value of our algorithm for efficiently approximating the spectrum of large large networks.

Coresets are one of the central methods to facilitate the analysis of large data. We continue a recent line of research applying the theory of coresets to logistic regression. First, we show the negative result that no strongly sublinear sized coresets exist for logistic regression. To deal with intractable worst-case instances we introduce a complexity measure $\mu(X)$, which quantifies the hardness of compressing a data set for logistic regression. $\mu(X)$ has an intuitive statistical interpretation that may be of independent interest. For data sets with bounded $\mu(X)$-complexity, we show that a novel sensitivity sampling scheme produces the first provably sublinear $(1\pm\eps)$-coreset. We illustrate the performance of our method by comparing to uniform sampling as well as to state of the art methods in the area. The experiments are conducted on real world benchmark data for logistic regression.

We develop a new algorithmic technique that allows to transfer some constant time approximation algorithms for general graphs into random order streaming algorithms. We illustrate our technique by proving that in random order streams with probability at least 2/3, the number of connected components of G can be approximated up to an additive error of εn using space, the weight of a minimum spanning tree of a connected input graph with integer edges weights from {1, …, W} can be approximated within a multiplicative factor of 1 + ε using space, the size of a maximum independent set in planar graphs can be approximated within a multiplicative factor of 1+ε using space .

We initiate the study of network monitoring algorithms in a class of hybrid networks in which the nodes are connected by an external network and an internal network (as a short form for externally and internally controlled network). While the external network lies outside of the control of the nodes (or in our case, the monitoring protocol running in them) and might be exposed to continuous changes, the internal network is fully under the control of the nodes. As an example, consider a group of users with mobile devices having access to the cell phone infrastructure. While the network formed by the WiFi connections of the devices is an external network (as its structure is not necessarily under the control of the monitoring protocol), the connections between the devices via the cell phone infrastructure represent an internal network (as it can be controlled by the monitoring protocol). Our goal is to continuously monitor properties of the external network with the help of the internal network. We present scalable distributed algorithms that efficiently monitor the number of edges, the average node degree, the clustering coefficient, the bipartiteness, and the weight of a minimum spanning tree. Their performance bounds demonstrate that monitoring the external network state with the help of an internal network can be done much more efficiently than just using the external network, as is usually done in the literature.

We study which property testing and sublinear time algorithms can be transformed into graph streaming algorithms for random order streams. Our main result is that for bounded degree graphs, any property that is constant-query testable in the adjacency list model can be tested with constant space in a single-pass in random order streams. Our result is obtained by estimating the distribution of local neighborhoods of the vertices on a random order graph stream using constant space. We then show that our approach can also be applied to constant time approximation algorithms for bounded degree graphs in the adjacency list model: As an example, we obtain a constant-space single-pass random order streaming algorithms for approximating the size of a maximum matching with additive error epsilon n (n is the number of nodes). Our result establishes for the first time that a large class of sublinear algorithms can be simulated in random order streams, while Omega(n) space is needed for many graph streaming problems for adversarial orders.

We present data streaming algorithms for the $k$-median problem in high-dimensional dynamic geometric data streams, i.e. streams allowing both insertions and deletions of points from a discrete Euclidean space $\{1, 2, \ldots \Delta\}^d$. Our algorithms use $k \epsilon^{-2} \mathrm{poly}(d \log \Delta)$ space/time and maintain with high probability a small weighted set of points (a coreset) such that for every set of $k$ centers the cost of the coreset $(1+\epsilon)$-approximates the cost of the streamed point set. We also provide algorithms that guarantee only positive weights in the coreset with additional logarithmic factors in the space and time complexities. We can use this positively-weighted coreset to compute a $(1+\epsilon)$-approximation for the $k$-median problem by any efficient offline $k$-median algorithm. All previous algorithms for computing a $(1+\epsilon)$-approximation for the $k$-median problem over dynamic data streams required space and time exponential in $d$. Our algorithms can be generalized to metric spaces of bounded doubling dimension.

In this paper, we study testing of sequence properties that are defined by forbidden order patterns. A sequence f : {1,…, n} → ℝ of length n contains a pattern is the group of permutations of k elements), iff there are indices i1 < i2 < · · · < ik, such that f (ix) > f (iy) whenever π(χ) > π(y). If f does not contain π, we say f is π-free. For example, for π = (2,1), the property of being π-free is equivalent to being non-decreasing, i.e. monotone. The property of being (k,k — 1,…, 1)-free is equivalent to the property of having a partition into at most k - 1 non-decreasing subsequences. Let k constant, be a (forbidden) pattern. Assuming f is stored in an array, we consider the property testing problem of distinguishing the case that f is π-free from the case that f differs in more than en places from any π-free sequence. We show the following results: There is a clear dichotomy between the monotone patterns and the non-monotone ones: For monotone patterns of length k, i.e., (k,k - 1,…, 1) and (1, 2,…, k), we design non-adaptive one-sided error ε-tests of (∊−1 log n)O(k2) query complexity. For non-monotone patterns, we show that for any size-k non-monotone π, any non-adaptive one-sided error ε-test requires at least Ω(γ/η) queries. This general lower bound can be further strengthened for specific non-monotone k-length patterns to Ω(n1–2/(k+1)). On the other hand, there always exists a non- adaptive one-sided error ε-test for with O(e−1/kn1–1/k) query complexity Again, this general upper bound can be further strengthened for specific non-monotone patterns. E.g., for π = (1, 3, 2), we describe an ε-test with (almost tight) query complexity of Finally, we show that adaptivity can make a big difference in testing non-monotone patterns, and develop an adaptive algorithm that for any tests π-freeness by making (∊−1 logn)O(1) queries. For all algorithms presented here, the running times are linear in their query complexity.

In this paper we develop streaming algorithms for the diameter problem and the k-center clustering problem in the sliding window model. In this model we are interested in maintaining a solution for the N most recent points of the stream. In the diameter problem we would like to maintain two points whose distance approximates the diameter of the point set in the window. Our algorithm computes a (3 + epsilon)-approximation and uses O(1/epsilon*ln(alpha)) memory cells, where alpha is the ratio of the largest and smallest distance and is assumed to be known in advance. We also prove that under reasonable assumptions obtaining a (3 - epsilon)-approximation requires Omega(N1/3) space. For the k-center problem, where the goal is to find k centers that minimize the maximum distance of a point to its nearest center, we obtain a (6 + epsilon)-approximation using O(k/epsilon*ln(alpha)) memory cells and a (4 + epsilon)-approximation for the special case k = 2. We also prove that any algorithm for the 2-center problem that achieves an approximation ratio of less than 4 requires Omega(N^{1/3}) space.

The Fréchet distance is a popular distance measure for curves. We study the problem of clustering time series under the Fréchet distance. In particular, we give (1 + ∊)-approximation algorithms for variations of the following problem with parameters k and ℓ. Given n univariate time series P, each of complexity at most m, we find k time series, not necessarily from P, which we call cluster centers and which each have complexity at most ℓ, such that (a) the maximum distance of an element of P to its nearest cluster center or (b) the sum of these distances is minimized. Our algorithms have running time near-linear in the input size for constant ∊, k and ℓ. To the best of our knowledge, our algorithms are the first clustering algorithms for the Fréchet distance which achieve an approximation factor of (1 + ∊) or better.

We study property testing algorithms in directed graphs (digraphs) with maximum indegree and maximum outdegree upper bounded by d. For directed graphs with bounded degree, there are two different models in property testing introduced by Bender and Ron (2002). In the bidirectional model, one can access both incoming and outgoing edges while in the unidirectional model one can only access outgoing edges. In our paper we provide a new relation between the two models: we prove that if a property can be tested with constant query complexity in the bidirectional model, then it can be tested with sublinear query complexity in the unidirectional model. A corollary of this result is that in the unidirectional model (the model allowing only queries to the outgoing neighbors), every property in hyperfinite digraphs is testable with sublinear query complexity.

Let G=(V,E) be an undirected graph with maximum degree d. The k-disc of a vertex v is defined as the rooted subgraph that is induced by all vertices whose distance to v is at most k. The k-disc frequency vector of G, freq(G), is a vector indexed by all isomorphism types of k-discs. For each such isomorphism type Gamma, the k-disc frequency vector counts the fraction of vertices that have k-disc isomorphic to Gamma. Thus, the frequency vector freq(G) of G captures the local structure of G. A natural question is whether one can construct a much smaller graph H such that H has a similar local structure. N. Alon proved that for any epsilon>0 there always exists a graph H whose size is independent of |V| and whose frequency vector satisfies ||freq(G) - freq(G)||_1 <= epsilon. However, his proof is only existential and neither gives an explicit bound on the size of H nor an efficient algorithm. He gave the open problem to find such explicit bounds. In this paper, we solve this problem for the special case of high girth graphs. We show how to efficiently compute a graph H with the above properties when G has girth at least 2k+2 and we give explicit bounds on the size of H.

We study the problem of recognizing the cluster structure of a graph in the framework of property testing in the bounded degree model. Given a parameter ε, a d-bounded degree graph is defined to be (k, φ)-clusterable, if it can be partitioned into no more than k parts, such that the (inner) conductance of the induced subgraph on each part is at least φ and the (outer) conductance of each part is at most cd,kε4φ2, where cd,k depends only on d,k. Our main result is a sublinear algorithm with the running time ~O(√n ⋅ poly(φ,k,1/ε)) that takes as input a graph with maximum degree bounded by d, parameters k, φ, ε, and with probability at least 2/3, accepts the graph if it is (k,φ)-clusterable and rejects the graph if it is ε-far from (k, φ*)-clusterable for φ* = c'd,kφ2 ε4}/log n, where c'd,k depends only on d,k. By the lower bound of Ω(√n) on the number of queries needed for testing graph expansion, which corresponds to k=1 in our problem, our algorithm is asymptotically optimal up to polylogarithmic factors.

This paper deals with computing the smallest enclosing ball of a set of points subject to probabilistic data. In our setting, any of the n points may not or may occur at one of finitely many locations, following its own discrete probability distribution. The objective is therefore considered to be a random variable and we aim at finding a center minimizing the expected maximum distance to the points according to their distributions. Our main contribution presented in this paper is the first polynomial time (1 + ϵ)-approximation algorithm for the probabilistic smallest enclosing ball problem with extensions to the streaming setting.

We consider the Euclidean facility location problem with uniform opening cost. In this problem, we are given a set of n points P sube ℝ2 and an opening cost f ∊ ℝ+, and we want to find a set of facilities F ⊆ ℝ2 that minimizes where d(p, q) is the Euclidean distance between p and q. We obtain two main results: A (1 + ε)-approximation algorithm with running time which is (n log2 n log log n) for any constant ε. The first (1 + ε)-approximation algorithm for the cost of the facility location problem for dynamic geometric data streams, i.e., when the stream consists of insert and delete operations of points from a discrete space {1, …, Δ}2. The streaming algorithm uses space. Our PTAS is significantly faster than any previously known (1 + ε)-approximation algorithm for the problem, and is also relatively simple. Our algorithm for dynamic geometric data streams is the first (1 + ε)-approximation algorithm for the cost of the facility location problem with polylogarithmic space, and it resolves an open problem in the streaming area. Both algorithms are based on a novel and simple decomposition of an input point set P into small subsets Pi, such that: the cost of solving the facility location problem for each Pi is small (which means that for each Pi one needs to open only a small, polylogarithmic number of facilities), Σi OPT(Pi) ≤ (1 + ε) · OPT(P), where for a point set P, OPT(P) denotes the cost of an optimal solution for P. The decomposition can be used directly to obtain the PTAS by splitting the point set in the subsets and efficiently solve the problem for each subset independently. By combining our partitioning with techniques to process dynamic data streams of sampling from the cells of the partition and estimating the cost from the sample, we obtain our data streaming algorithm.

We prove that the sum of the squared Euclidean distances from the n rows of an n × d matrix A to any compact set that is spanned by k vectors in ℝd can be approximated up to (1+ε)-factor, for an arbitrary small ε > 0, using the O(k/ε2)-rank approximation of A and a constant. This implies, for example, that the optimal k-means clustering of the rows of A is (1 + ε)-approximated by an optimal k-means clustering of their projection on the O(k/ε2) first right singular vectors (principle components) of A. A (j, k)-coreset for projective clustering is a small set of points that yields a (1 + ε)-approximation to the sum of squared distances from the n rows of A to any set of k affine subspaces, each of dimension at most j. Our embedding yields (0, k)-coresets of size (k) for handling k-means queries, (j, 1)-coresets of size (j) for PCA queries, and (j, k)-coresets of size (log n) (jk) for any j, k ≥ 1 and constant ε ∊ (0, 1/2). Previous coresets usually have a size which is linearly or even exponentially dependent of d, which makes them useless when d ∼ n. Using our coresets with the merge-and-reduce approach, we obtain embarrassingly parallel streaming algorithms for problems such as k-means, PCA and projective clustering. These algorithms use update time per point and memory that is polynomial in log n and only linear in d. For cost functions other than squared Euclidean distances we suggest a simple recursive coreset construction that produces coresets of size for k-means and a special class of bregman divergences that is less dependent on the properties of the squared Euclidean distance.

A $k$-disc around a vertex $v$ of a graph $G=(V,E)$ is the subgraph induced by all vertices of distance at most $k$ from $v$. We show that the structure of a planar graph on $n$ vertices, and with constant maximum degree $d$, is determined, up to the modification (insertion or deletion) of at most $\epsilon d n$ edges, by the frequency of $k$-discs for certain $k=k(\epsilon,d)$ that is independent of the size of the graph. We can replace planar graphs by any hyperfinite class of graphs, which includes, for example, every graph class that does not contain a set of forbidden minors. A pure combinatorial consequence of this result is that two $d$-bounded degree graphs that have similar frequency vectors (that is, the $\ell_1$ difference between the frequency vectors is small) are close to isomorphic (where close here means that by inserting or deleting not too many edges in one of them, it becomes isomorphic to the other). We also obtain the following new results in the area of property testing, which are essentially equivalent to the above statement. We prove that (a) graph isomorphism is testable for every class of hyperfinite graphs, (b) every graph property is testable for every class of hyperfinite graphs, (c) every hyperfinite graph property is testable in the bounded degree graph model, (d) A large class of graph parameters is approximable for hyperfinite graphs. Our results also give a partial explanation of the success of motifs in the analysis of complex networks.

In the (k, d)-Function-SAT problem we are given a set of n variables {X1, ... , Xn} that can take values from the set {1, . .. , d} and a set of Boolean constraints on these variables, where each constraint is of the form f : {1, ... , d}k→ {0, 1}, i.e. the constraint depends on exactly k of these variables. We will treat k and d as constants. The goal is to determine whether the set of constraints has a satisfying assignment, i.e. an assignment to the variables such that all constraints simultanuously map to 1. In this paper, we study (k, d)-Function-SAT in the property testing model for dense instances. We call an instance ε-far from satisfiable, if every assignment violates more than εnkconstraints. A property testing algorithm is a randomized algorithm that, given oracle access to the set of constraints, must accept with probability at least 3/4 all satisfiable inputs and rejects with probability at least 3/4 all inputs, which are ε-far from satisfiable. We analyze the canonical non-adaptive property testing algorithm with one-sided error: Sample r variables and accept, if and only if the induced set of constraints has a satisfying assignment. The value of r will be called the sample commlexity of the algorithm. We show that there is an r0= O(1/ε) such that for any instance that is ε-far from satisfiable, the probability, that a random sample on r ≥ r0 variables is satisfiable, is at most 1/4. This implies that the above algorithm is a property tester. The obtained sample complexity is nearly optimal for canonical testers as a lower bound of Ω(1/ε) on the sample complexity is known. Previously, a tester with sample complexity o(1/ε2) was only known for the very special case of testing bipartiteness in the dense graph model [3]. Our new general result improves the best previous result for testing satisfiability (and even for the special case of 3-colorability in graphs) from sample complexity Õ(1/ε2) to Õ(1/ε). It also slightly improves the sample complexity for the special case of bipartiteness. Improving the sample complexity for (k, d)-Function-SAT (or special cases of it) had been posed in several papers as an open problem [3], [4], [17]. This paper solves this problem nearly optimally for canonical testers and, in the case of k = 2, also for nonadaptive testers as there is a lower bound of Ω(1/ε2) on the query complexity of non-adaptive testers for bipartiteness in the dense graph model [6], where the query complexity denotes the number of queries asked about the graph (for a canonical tester in graphs, the query complexity is the square of its sample complexity). As a byproduct, we obtain an algorithm, which, given a satisfiable set of constraints, computes in time O(n/εO(1)+ 2Õ(1/ε)) a solution, which violates at most εnkconstraints.

A left-to-right maximum in a sequence of n numbers s 1 , …, s n is a number that is strictly larger than all preceding numbers. In this article we present a smoothed analysis of the number of left-to-right maxima in the presence of additive random noise. We show that for every sequence of n numbers s i ∈ [0,1] that are perturbed by uniform noise from the interval [-ϵ,ϵ], the expected number of left-to-right maxima is Θ(√ n /ϵ + log n ) for ϵ>1/ n . For Gaussian noise with standard deviation σ we obtain a bound of O ((log 3/2 n )/σ + log n ). We apply our results to the analysis of the smoothed height of binary search trees and the smoothed number of comparisons in the quicksort algorithm and prove bounds of Θ(√ n /ϵ + log n ) and Θ( n /ϵ+1√ n /ϵ + n log n ), respectively, for uniform random noise from the interval [-ϵ,ϵ]. Our results can also be applied to bound the smoothed number of points on a convex hull of points in the two-dimensional plane and to smoothed motion complexity, a concept we describe in this article. We bound how often one needs to update a data structure storing the smallest axis-aligned box enclosing a set of points moving in d -dimensional space.

We initiate the study of the testability of properties in arbitrary planar graphs. We prove that bipartiteness can be tested in constant time. The previous bound for this class of graphs was O(√n), and the constant-time testability was only known for planar graphs with bounded degree. Previously used transformations of unbounded-degree sparse graphs into bounded- degree sparse graphs cannot be used to reduce the problem to the testability of bounded-degree planar graphs. Our approach extends to arbitrary minor-free graphs. Our algorithm is based on random walks. The challenge here is to analyze random walks for a class of graphs that has good separators, i.e., bad expansion. Standard techniques that use a fast convergence to a uniform distribution do not work in this case. Roughly speaking, our analysis technique self-reduces the problem of finding an odd-length cycle in a multigraph G induced by a collection of cycles to another multigraph G' induced by a set of shorter odd-length cycles, in such a way that when a random walks finds a cycle in G' with probability p >; 0, then it does so with probability λ(p) >; 0 in G. This reduction is applied until the cycles collapse to self-loops that can be easily detected.

The diameter k-clustering problem is the problem of partitioning a finite subset of R^d into k subsets called clusters such that the maximum diameter of the clusters is minimized. One early clustering algorithm that computes a hierarchy of approximate solutions to this problem for all values of k is the agglomerative clustering algorithm with the complete linkage strategy. For decades this algorithm has been widely used by practitioners. However, it is not well studied theoretically. In this paper we analyze the agglomerative complete linkage clustering algorithm. Assuming that the dimension dis a constant, we show that for any k the solution computed by this algorithm is an O(log k)-approximation to the diameter k-clustering problem. Moreover, our analysis does not only hold for the Euclidean distance but for any metric that is based on a norm.

A property testing algorithm for a property Π in the bounded degree graph model[7] is an algorithm that, given access to the adjacency list representation of a graph G=(V,E) with maximum degree at most d, accepts G with probability at least 2/3 if G has property Π, and rejects G with probability at least 2/3, if it differs on more than ε dn edges from every d-degree bounded graph with property Π. A property is testable, if for every ε,d and n, there is a property testing algorithm Aε,n,d that makes at most q(ε,d) queries to an input graph of n vertices, that is, a non-uniform algorithm that makes a number of queries that is independent of the graph size.

We show there is a distribution over linear mappings R:l1n -> l1O(d log d), such that with arbitrarily large constant probability, for any fixed d-dimensional subspace L, for all x ∈ L we have |x|1 ≤ |Rx|1 = O(d log d)|x|1. This provides the first analogue of the ubiquitous subspace Johnson-Lindenstrauss embedding for the l1-norm. Importantly, the target dimension and distortion are independent of the ambient dimension n. We give several applications of this result. First, we give a faster algorithm for computing well-conditioned bases. Our algorithm is simple, avoiding the linear programming machinery required of previous algorithms. We also give faster algorithms for least absolute deviation regression and l1-norm best fit hyperplane problems, as well as the first single pass streaming algorithms with low space for these problems. These results are motivated by practical problems in image analysis, spam detection, and tatistics, where the l1-norm is used in studies where outliers may be safely and effectively ignored. This is because the l1-norm is more robust to outliers than the l2-norm.

We develop a new k-means clustering algorithm for data streams, which we call StreamKM++. Our algorithm computes a small weighted sample of the data stream and solves the problem on the sample using the k-means++ algorithm [1]. To compute the small sample, we propose two new techniques. First, we use a non-uniform sampling approach similar to the k-means++ seeding procedure to obtain small core-sets from the data stream. This construction is rather easy to implement and, unlike other coreset constructions, its running time has only a low dependency on the dimensionality of the data. Second, we propose a new data structure which we call a coreset tree. The use of these coreset trees significantly speeds up the time necessary for the non-uniform sampling during our coreset construction. We compare our algorithm experimentally with two well-known streaming implementations (BIRCH [16] and StreamLS [4, 9]). In terms of quality (sum of squared errors), our algorithm is comparable with StreamLS and significantly better than BIRCH (up to a factor of 2). In terms of running time, our algorithm is slower than BIRCH. Comparing the running time with StreamLS, it turns out that our algorithm scales much better with increasing number of centers. We conclude that, if the first priority is the quality of the clustering, then our algorithm provides a good alternative to BIRCH and StreamLS, in particular, if the number of cluster centers is large. We also give a theoretical justification of our approach by proving that our sample set is a small coreset in low dimensional spaces.

We study the task of testing properties of probability distributions. We consider a scenario in which we have access to independent samples of an unknown distribution with infinite (perhaps even uncountable) support. Our goal is to test whether has a given property or it is ε-far from it (in the statistical distance, with the L1-distance measure). It is not difficult to see that for many natural distributions on infinite or uncountable domains, no testing algorithm can exist and the central objective of our study is to understand if there are any nontrivial distributions that can be efficiently tested. For example, it is easy to see that there is no testing algorithm that tests if a given probability distribution on [0, 1] is uniform. We show however, that if some additional information about the input distribution is known, testing uniform distribution is possible. We extend the recent result about testing uniformity for monotone distributions on Boolean n-dimensional cubes by Rubinfeld and Servedio (STOC'2005) to the case of continuous [0, l]n cubes. We show that if a distribution on [0, l]n is monotone, then one can test if is uniform with the sample complexity (n/ε2). This result is optimal up to a polylogarithmic factor.

We consider the problem of approximating a set P of n points in ℝd by a j-dimensional subspace under the ℓp measure, in which we wish to minimize the sum of ℓp distances from each point of P to this subspace. More generally, the Fq (ℓp)-subspace approximation problem asks for a j-subspace that minimizes the sum of qth powers of ℓp-distances to this subspace, up to a multiplicative factor of (1 + ε). We develop techniques for subspace approximation, regression, and matrix approximation that can be used to deal with massive data sets in high dimensional spaces. In particular, we develop coresets and sketches, i.e. small space representations that approximate the input point set P with respect to the subspace approximation problem. Our results are: A dimensionality reduction method that can be applied to Fq (ℓp)-clustering and shape fitting problems, such as those in [8, 15]. The first strong coreset for F1 (ℓ2)-subspace approximation in high-dimensional spaces, i.e. of size polynomial in the dimension of the space. This coreset approximates the distances to any j-subspace (not just the optimal one). A (1 + ε)-approximation algorithm for the j-dimensional F1 (ℓ2)-subspace approximation problem with running time nd(j/ε)O(1) + (n + d)2poly(j/ε). A streaming algorithm that maintains a coreset for the F1 (ℓ2)-subspace approximation problem and uses a space of (weighted) points. Streaming algorithms for the above problems with bounded precision in the turnstile model, i.e, when coordinates appear in an arbitrary order and undergo multiple updates. We show that bounded precision can lead to further improvements. We extend results of [7] for approximate linear regression, distances to subspace approximation, and optimal rank-j approximation, to error measures other than the Frobenius norm.

We study a generalization of the k -median problem with respect to an arbitrary dissimilarity measure D. Given a finite set P of size n , our goal is to find a set C of size k such that the sum of errors D( P,C ) = ∑ p ∈ P min c ∈ C {D( p,c )} is minimized. The main result in this article can be stated as follows: There exists a (1+ϵ)-approximation algorithm for the k -median problem with respect to D, if the 1-median problem can be approximated within a factor of (1+ϵ) by taking a random sample of constant size and solving the 1-median problem on the sample exactly. This algorithm requires time n 2 O ( mk log( mk /ϵ)), where m is a constant that depends only on ϵ and D. Using this characterization, we obtain the first linear time (1+ϵ)-approximation algorithms for the k -median problem in an arbitrary metric space with bounded doubling dimension, for the Kullback-Leibler divergence (relative entropy), for the Itakura-Saito divergence, for Mahalanobis distances, and for some special cases of Bregman divergences. Moreover, we obtain previously known results for the Euclidean k -median problem and the Euclidean k -means problem in a simplified manner. Our results are based on a new analysis of an algorithm of Kumar et al. [2004].

In this paper we present a sublinear-time $(1+\varepsilon)$-approximation randomized algorithm to estimate the weight of the minimum spanning tree of an n-point metric space. The running time of the algorithm is $\widetilde{\mathcal{O}}(n/\varepsilon^{\mathcal{O}(1)})$. Since the full description of an n-point metric space is of size $\Theta(n^2)$, the complexity of our algorithm is sublinear with respect to the input size. Our algorithm is almost optimal as it is not possible to approximate in $o(n)$ time the weight of the minimum spanning tree to within any factor. We also show that no deterministic algorithm can achieve a B-approximation in $o(n^2/B^3)$ time. Furthermore, it has been previously shown that no $o(n^2)$ algorithm exists that returns a spanning tree whose weight is within a constant times the optimum.

We study graph properties that are testable for bounded-degree graphs in time independent of the input size. Our goal is to distinguish between graphs having a predetermined graph property and graphs that are far from every graph having that property. It is well known that in the bounded-degree graph model (where two graphs are considered “far” if they differ in $\varepsilon n$ edges for a positive constant $\varepsilon$), many graph properties cannot be tested even with a constant or even with a polylogarithmic number of queries. Therefore in this paper we focus our attention on testing graph properties for special classes of graphs. Specifically, we show that every hereditary graph property is testable with a constant number of queries provided that every sufficiently large induced subgraph of the input graph has poor expansion. This result implies that, for example, any hereditary property (e.g., k-colorability, H-freeness, etc.) is testable in the bounded-degree graph model for planar graphs, graphs with bounded genus, interval graphs, etc. No such results have been known before, and prior to our work, very few graph properties have been known to be testable with a constant number of queries for general graph classes in the bounded-degree graph model.

Given a Euclidean graph G over a set P of n points in the plane, we are interested in verifying whether G is a Euclidean minimum spanning tree (EMST) of P or G differs from it in more than ϵ n edges. We assume that G is given in adjacency list representation and the point/vertex set P is given in an array. We present a property testing algorithm that accepts graph G if it is an EMST of P and that rejects with probability at least 2/3 if G differs from every EMST of P in more than ϵ, n edges. Our algorithm runs in O(√ n /ϵ ⋅ log 2 ( n /ϵ)) time and has a query complexity of O(√ n /ϵ ⋅ log ( n /ϵ)).

Given a point set P ⊆ Rd the k-means clustering problem is to find a set C=(c1,...,ck) of k points and a partition of P into k clusters C1,...,Ck such that the sum of squared errors ∑i=1k ∑p ∈ Ci |p -ci |22 is minimized. For given centers this cost function is minimized byassigning points to the nearest center.The k-means cost function is probably the most widely used cost function in the area of clustering.In this paper we show that every unweighted point set P has a weak (ε, k)-coreset of size Poly(k,1/ε) for the k-means clustering problem, i.e. its size is independent of the cardinality |P| of the point set and the dimension d of the Euclidean space Rd. A weak coreset is a weighted set S ⊆ P together with a set T such that T contains a (1+ε)-approximation for the optimal cluster centers from P and for every set of kcenters from T the cost of the centers for S is a (1±ε)-approximation of the cost for P.We apply our weak coreset to obtain a PTAS for the k-means clustering problem with running time O(nkd + d · Poly(k/ε) + 2Õ(k/ε)).

We consider the problem of testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion: an alpha-expander is a graph G = (V, E) in which even-subset U sube V of at most |V|/2 vertices has a neighborhood of size at least alphaldr|U|. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time O tilde(radicn). We prove that the property testing algorithm proposed by Goldreich and Ron (2000) with appropriately set parameters accepts every alpha-expander with probability at least 2/3 and rejects every graph that is epsiv-far from an alpha*-expander with probability at least 2/3, where alpha*=Theta(alpha2/(d2log (n/epsiv))) and d is the maximum degree of the graphs. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is O(d2(radicn log (n/epsiv))/alpha2epsiv3).

In this paper we develop an efficient implementation for a k-means clustering algorithm. Our algorithm is a variant of KMHybrid [28, 20], i.e. it uses a combination of Lloyd-steps and random swaps, but as a novel feature it uses coresets to speed up the algorithm. A coreset is a small weighted set of points that approximates the original point set with respect to the considered problem. The main strength of the algorithm is that it can quickly determine clusterings of the same point set for many values of k. This is necessary in many applications, since, typically, one does not know a good value for k in advance. Once we have clusterings for many different values of k we can determine a good choice of k using a quality measure of clusterings that is independent of k, for example the average silhouette coefficient. The average silhouette coefficient can be approximated using coresets.To evaluate the performance of our algorithm we compare it with algorithm KMHybrid [28] on typical 3D data sets for an image compression application and on artificially created instances. Our data sets consist of 300,000 to 4.9 million points. We show that our algorithm significantly outperforms KMHybrid on most of these input instances. Additionally, the quality of the solutions computed by our algorithm deviates less than that of KMHybrid.We also computed clusterings and approximate average silhouette coefficient for k=1,…,100 for our input instances and discuss the performance of our algorithm in detail.

We present two space bounded random sampling algorithms that compute an approximation of the number of triangles in an undirected graph given as a stream of edges. Our first algorithm does not make any assumptions on the order of edges in the stream. It uses space that is inversely related to the ratio between the number of triangles and the number of triples with at least one edge in the induced subgraph, and constant expected update time per edge. Our second algorithm is designed for incidence streams (all edges incident to the same vertex appear consecutively). It uses space that is inversely related to the ratio between the number of triangles and length 2 paths in the graph and expected update time O(log |V |·(1+s ·|V |/|E|)), where s is the space requirement of the algorithm. These results significantly improve over previous work [20, 8]. Since the space complexity depends only on the structure of the input graph and not on the number of nodes, our algorithms scale very well with increasing graph size and so they provide a basic tool to analyze the structure of large graphs. They have many applications, for example, in the discovery of Web communities, the computation of clustering and transitivity coefficient, and discovery of frequent patterns in large graphs. We have implemented both algorithms and evaluated their performance on networks from different application domains. The sizes of the considered graphs varied from about 8, 000 nodes and 40, 000 edges to 135 million nodes and more than 1 billion edges. For both algorithms we run experiments with parameter s = 1, 000, 10, 000, 100, 000, 1, 000, 000 to evaluate running time and approximation guarantee. Both algorithms appear to be time efficient for these sample sizes. The approximation quality of the first algorithm was varying significantly and even for s = 1, 000, 000 we had more than 10% deviation for more than half of the instances. The second algorithm performed much better and even for s = 10, 000 we had an average deviation of less than 6% (taken over all but the largest instance for which we could not compute the number of triangles exactly). Copyright 2006 ACM.

In this paper, we present a randomized constant factor approximation algorithm for the metric minimum facility location problem with uniform costs and demands in a distributed setting, in which every point can open a facility. In particular, our distributed algorithm uses three communication rounds with message sizes bounded to O(log n) bits where n is the number of points. We also extend our algorithm to constant powers of metric spaces, where we also obtain a randomized constant factor approximation algorithm.

A dynamic geometric data stream is a sequence of m Add/Remove operations of points from a discrete geometric space (1,...,Δ)d [21]. Add(p) inserts a point p from (1,...,Δ)d into the current point set, Remove(p) deletes p from P. We develop low-storage data structures to (i) maintain ε-approximations of range spaces of P with constant VC-dimension and (ii) maintain an ε-approximation of the weight of the Euclidean minimum spanning tree of P. Our data structures use O(log3ε • log3(1/ε) • log(1/ε)/ε2) and O(log (1/δ) • (log Δ/ε)O(d)) bits of memory, respectively (we assume that the dimension d is a constant), and they are correct with probability 1-δ. These results are based on a new data structure that maintains a set of elements chosen (almost) uniformly at random from P.

A dynamic geometric data stream consists of a sequence of m insert/delete operations of points from the discrete space 1,…,Δd [26]. We develop streaming (1 + e)-approximation algorithms for k-median, k-means, MaxCut, maximum weighted matching (MaxWM), maximum travelling salesperson (MaxTSP), maximum spanning tree (MaxST), and average distance over dynamic geometric data streams. Our algorithms maintain a small weighted set of points(a coreset) that approximates with probability 2/3 the current point set with respect to the considered problem during the m insert/delete operations of the data stream. They use poly (e-1, log m, log Δ) space and update time per insert/delete operation for constant k and dimension dHaving a coreset one only needs a fast approximation algorithm for the weighted problem to compute a solution quickly. In fact, even an exponential algorithm is sometimes feasible as its running time may still be polynomial in n. For example one can compute in poly(log n, exp(O((1+log (1⁄e)⁄e)d-1))) time a solution to k-median and k-means [21] where n is the size of the current point set and k and d are constants. Finding an implicit solution to MaxCut can be done in poly(log n, exp((1⁄e)O(1))) time. For MaxST and average distance we require poly(log n, e-1) time and for MaxWM we require O(n3) time to do this.

We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in $\mathbb R^d$. We focus on the setting where the input point set is supported by certain basic (and commonly used) geometric data structures that can provide efficient access to the input in a structured way. We present an algorithm that estimates with high probability the weight of a Euclidean minimum spanning tree of a set of points to within $1 + \eps$ using only $\widetilde{\O}(\sqrt{n} \, \text{poly} (1/\eps))$ queries for constant d. The algorithm assumes that the input is supported by a minimal bounding cube enclosing it, by orthogonal range queries, and by cone approximate nearest neighbor queries.

Property testing is a relaxation of classical decision problems which aims at distinguishing between functions having a predetermined property and functions being far from any function having the property. In this paper we present a novel framework for analyzing property testing algorithms. Our framework is based on a connection of property testing and a new class of problems which we call abstract combinatorial programs. We show that if the problem of testing a property can be reduced to an abstract combinatorial program of small dimension, then the property has an efficient tester. We apply our framework to a variety of problems. We present efficient property testing algorithms for geometric clustering problems, for the reversaldistance problem, and for graph and hypergraph coloring problems. We also prove that, informally, any hereditary graph property can be efficiently tested if and only if it can be reduced to an abstract combinatorial program of small size. Our framework allows us to analyze all our testers in a unified way, and the obtained complexity bounds either match or improve the previously known bounds. Furthermore, even if the asymptotic complexity of the testers is not improved, the obtained proofs are significantly simpler than the previous ones. We believe that our framework will help to understand the structure of efficiently testable properties.

In this paper we present a sublinear time (1 + ε)-approximation randomized algorithm to estimate the weight of the minimum spanning tree of an n-point metric space. The running time of the algorithm is Û(n/εO(1)). Since the full description of an n-point metric space is of size Θ(n2), the complexity of our algorithm is sublinear with respect to the input size. Our algorithm is almost optimal as it is not possible to approximate in o(n) time the weight of the minimum spanning tree to within any factor. Furthermore, it has been previously shown that no o(n2) algorithm exists that returns a spanning tree whose weight is within a constant times the optimum.

Property testing is a relaxation of classical decision problems which aims at distinguishing between functions having a predetermined property and functions being far from any function having the property. In this paper we present a novel framework for analyzing property testing algorithms with one-sided error. Our framework is based on a connection of property testing and a new class of problems which we call abstract combinatorial programs. We show that if the problem of testing a property can be reduced to an abstract combinatorial program of small dimension, then the property has an efficient tester. We apply our framework to a variety of classical combinatorial problems. Among others, we present efficient property testing algorithms for geometric clustering problems, the reversal distance problem, and graph and hypergraph coloring problems. We also prove that, informally, any hereditary graph property can be efficiently tested if and only if it can be reduced to an abstract combinatorial program of small size. Our framework allows us to analyze all our testers in a unified way and the obtained complexity bounds either match or improve the previously known bounds. We believe that our framework will help to better understand the structure of efficiently testable properties.