145 research outputs found
Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing
No full textWe prove a tight lower bound for the exponent rho for data-dependent Locality-Sensitive Hashing schemes, recently used to
design efficient solutions for the c-approximate nearest neighbor search. In particular, our lower bound matches the bound of rho<= 1/(2c-1)+o(1) for the l_1 space, obtained via the recent algorithm from [Andoni-Razenshteyn, STOC'15].
In recent years it emerged that data-dependent hashing is strictly superior to the classical Locality-Sensitive Hashing, when
the hash function is data-independent. In the latter setting, the best exponent has been already known: for the l_1 space, the tight bound is rho=1/c, with the upper bound from [Indyk-Motwani,STOC'98] and the matching lower bound from [O'Donnell-Wu-Zhou,ITCS'11].
We prove that, even if the hashing is data-dependent, it must hold that rho>=1/(2c-1)-o(1). To prove the result, we need to
formalize the exact notion of data-dependent hashing that also captures the complexity of the hash functions (in addition to their collision properties). Without restricting such complexity, we would allow for obviously infeasible solutions such as the Voronoi diagram of a dataset. To preclude such solutions, we require our hash functions to be succinct. This condition is satisfied by all the known algorithmic results
Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity
No full textMany modern parallel systems, such as MapReduce, Hadoop and Spark, can be modeled well by the MPC model. The MPC model captures well coarse-grained computation on large data - data is distributed to processors, each of which has a sublinear (in the input data) amount of memory and we alternate between rounds of computation and rounds of communication, where each machine can communicate an amount of data as large as the size of its memory. This model is stronger than the classical PRAM model, and it is an intriguing question to design algorithms whose running time is smaller than in the PRAM model.
In this paper, we study two fundamental problems, 2-edge connectivity and 2-vertex connectivity (biconnectivity). PRAM algorithms which run in O(log n) time have been known for many years. We give algorithms using roughly log diameter rounds in the MPC model. Our main results are, for an n-vertex, m-edge graph of diameter D and bi-diameter D', 1) a O(log D log log_{m/n} n) parallel time 2-edge connectivity algorithm, 2) a O(log D log^2 log_{m/n}n+log D'log log_{m/n}n) parallel time biconnectivity algorithm, where the bi-diameter D' is the largest cycle length over all the vertex pairs in the same biconnected component. Our results are fully scalable, meaning that the memory per processor can be O(n^{delta}) for arbitrary constant delta>0, and the total memory used is linear in the problem size. Our 2-edge connectivity algorithm achieves the same parallel time as the connectivity algorithm of [Andoni et al., 2018]. We also show an Omega(log D') conditional lower bound for the biconnectivity problem
Two Party Distribution Testing: Communication and Security
No full textWe study the problem of discrete distribution testing in the two-party setting. For example, in the standard closeness testing problem, Alice and Bob each have t samples from, respectively, distributions a and b over [n], and they need to test whether a=b or a,b are epsilon-far (in the l_1 distance). This is in contrast to the well-studied one-party case, where the tester has unrestricted access to samples of both distributions. Despite being a natural constraint in applications, the two-party setting has previously evaded attention.
We address two fundamental aspects of the two-party setting: 1) what is the communication complexity, and 2) can it be accomplished securely, without Alice and Bob learning extra information about each other’s input. Besides closeness testing, we also study the independence testing problem, where Alice and Bob have t samples from distributions a and b respectively, which may be correlated; the question is whether a,b are independent or epsilon-far from being independent. Our contribution is three-fold: 1) We show how to gain communication efficiency given more samples, beyond the information-theoretic bound on t. The gain is polynomially better than what one would obtain via adapting one-party algorithms. 2) We prove tightness of our trade-off for the closeness testing, as well as that the independence testing requires tight Omega(sqrt{m}) communication for unbounded number of samples. These lower bounds are of independent interest as, to the best of our knowledge, these are the first 2-party communication lower bounds for testing problems, where the inputs are a set of i.i.d. samples. 3) We define the concept of secure distribution testing, and provide secure versions of the above protocols with an overhead that is only polynomial in the security parameter
THE COMPUTATIONAL HARDNESS OF ESTIMATING EDIT DISTANCE
No full textWe prove the first nontrivial communication complexity lower bound for the problem of estimating the edit distance (aka Levenshtein distance) between two strings. To the best of our knowledge, this is the first computational setting in which the complexity of estimating the edit distance is provably larger than that of Hamming distance. Our lower bound exhibits a trade-off between approximation and communication, asserting, for example, that protocols with bits of communication can obtain only approximation , where is the length of the input strings. This case of communication is of particular importance since it captures constant-size sketches as well as embeddings into spaces like and squared-, two prevailing algorithmic approaches for dealing with edit distance. Indeed, the known nontrivial communication upper bounds are all derived from embeddings into . By excluding low-communication protocols for edit distance, we rule out a strictly richer class of algorithms than previous results. Furthermore, our lower bound holds not only for strings over a binary alphabet but also for strings that are permutations (aka the Ulam metric). For this case, our bound nearly matches an upper bound known via embedding the Ulam metric into . Our proof uses a new technique that relies on Fourier analysis in a rather elementary way
Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost
No full textTransportation cost metrics, also known as the Wasserstein distances W_p, are a natural choice for defining distances between two pointsets, or distributions, and have been applied in numerous fields. From the computational perspective, there has been an intensive research effort for understanding the W_p metrics over R^k, with work on the W_1 metric (a.k.a earth mover distance) being most successful in terms of theoretical guarantees. However, the W_2 metric, also known as the root-mean square (RMS) bipartite matching distance, is often a more suitable choice in many application areas, e.g. in graphics. Yet, the geometry of this metric space is currently poorly understood, and efficient algorithms have been elusive. For example, there are no known non-trivial algorithms for nearest-neighbor search or sketching for this metric.
In this paper we take the first step towards explaining the lack of efficient algorithms for the W_2 metric, even over the three-dimensional Euclidean space R^3. We prove that there are no meaningful embeddings of W_2 over R^3 into a wide class of normed spaces, as well as that there are no efficient sketching algorithms for W_2 over R^3 achieving constant approximation. For example, our results imply that: 1) any embedding into L1 must incur a distortion of Omega(sqrt(log(n))) for pointsets of size n equipped with the W_2 metric; and 2) any sketching algorithm of size s must incur Omega(sqrt(log(n))/sqrt(s)) approximation. Our results follow from a more general statement, asserting that W_2 over R^3 contains the 1/2-snowflake of all finite metric spaces with a uniformly bounded distortion. These are the first non-embeddability/non-sketchability results for W_2
Communication Complexity of Inner Product in Symmetric Normed Spaces
No full textWe introduce and study the communication complexity of computing the inner
product of two vectors, where the input is restricted w.r.t. a norm on the
space . Here, Alice and Bob hold two vectors such that
and , where is the dual norm. They want
to compute their inner product up to an
additive term. The problem is denoted by .
We systematically study , showing the following results:
- For any symmetric norm , given and
there is a randomized protocol for using
bits -- we will denote this by
.
- One way communication complexity
, and a nearly matching lower bound
for .
- One way communication complexity for a
symmetric norm is governed by embeddings into .
Specifically, while a small distortion embedding easily implies a lower bound
, we show that, conversely, non-existence of such an embedding
implies protocol with communication .
- For arbitrary origin symmetric convex polytope , we show
, where is the unique norm for which is a unit ball,
and is the extension complexity of .Comment: Accepted to ITCS 202
On Solving Linear Systems in Sublinear Time
No full textWe study sublinear algorithms that solve linear systems locally. In the classical version of this problem the input is a matrix S in R^{n x n} and a vector b in R^n in the range of S, and the goal is to output x in R^n satisfying Sx=b. For the case when the matrix S is symmetric diagonally dominant (SDD), the breakthrough algorithm of Spielman and Teng [STOC 2004] approximately solves this problem in near-linear time (in the input size which is the number of non-zeros in S), and subsequent papers have further simplified, improved, and generalized the algorithms for this setting.
Here we focus on computing one (or a few) coordinates of x, which potentially allows for sublinear algorithms. Formally, given an index u in [n] together with S and b as above, the goal is to output an approximation x^_u for x^*_u, where x^* is a fixed solution to Sx=b.
Our results show that there is a qualitative gap between SDD matrices and the more general class of positive semidefinite (PSD) matrices. For SDD matrices, we develop an algorithm that approximates a single coordinate x_{u} in time that is polylogarithmic in n, provided that S is sparse and has a small condition number (e.g., Laplacian of an expander graph). The approximation guarantee is additive | x^_u-x^*_u | 0. We further prove that the condition-number assumption is necessary and tight.
In contrast to the SDD matrices, we prove that for certain PSD matrices S, the running time must be at least polynomial in n (for the same additive approximation), even if S has bounded sparsity and condition number
External Sampling
No full text36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part IWe initiate the study of sublinear-time algorithms in the external memory model [1]. In this model, the data is stored in blocks of a certain size B, and the algorithm is charged a unit cost for each block access. This model is well-studied, since it reflects the computational issues occurring when the (massive) input is stored on a disk. Since each block access operates on B data elements in parallel, many problems have external memory algorithms whose number of block accesses is only a small fraction (e.g. 1/B) of their main memory complexity.
However, to the best of our knowledge, no such reduction in complexity is known for any sublinear-time algorithm. One plausible explanation is that the vast majority of sublinear-time algorithms use random sampling and thus exhibit no locality of reference. This state of affairs is quite unfortunate, since both sublinear-time algorithms and the external memory model are important approaches to dealing with massive data sets, and ideally they should be combined to achieve best performance.
In this paper we show that such combination is indeed possible. In particular, we consider three well-studied problems: testing of distinctness, uniformity and identity of an empirical distribution induced by data. For these problems we show random-sampling-based algorithms whose number of block accesses is up to a factor of 1/√B smaller than the main memory complexity of those problems. We also show that this improvement is optimal for those problems.
Since these problems are natural primitives for a number of sampling-based algorithms for other problems, our tools improve the external memory complexity of other problems as well.David & Lucile Packard Foundation (Fellowship)Center for Massive Data Algorithmics (MADALGO)Marie Curie (International Reintegration Grant 231077)National Science Foundation (U.S.) (Grant 0514771)National Science Foundation (U.S.) (Grant 0728645)National Science Foundation (U.S.) (Grant 0732334)Symantec Research Labs (Research Fellowship
Efficient Sketches for Earth-Mover Distance, with Applications
No full textWe provide the first sub-linear sketching algorithm for estimating the planar Earth-Mover Distance with a constant approximation. For sets living in the two-dimensional grid [Δ][superscript 2], we achieve space ΔE for approximation O(1/E), for any desired 0 < E < 1. Our sketch has immediate applications to the streaming and nearest neighbor search problems.National Science Foundation (U.S.) (CAREER award CCR-0133849)Alfred P. Sloan FoundationDavid and Lucile Packard Foundatio
Approximate nearest neighbor problem in high dimensions
No full textThesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005.Includes bibliographical references (p. 47-49).We investigate the problem of finding the approximate nearest neighbor when the data set points are the substrings of a given text T. The exact version of this problem is defined as follows. Given a text T of length n, we want to build a data structure that supports the following operation: given a pattern P, find the substring of T that is the closest to P. Since the exact version of this problem is surprisingly difficult, we address the approximate version, in which we are allowed to return a substring of T that is at most c times further than the actual closest substring of T. This problem occurs, for example, in computational biology [4, 5]. In particular, we study the case where the length of the pattern P, denoted by m, is not known in advance, which is the most natural scenario. We present a data structure that uses O(n1+1/c) space and has 0 (nl/c + mn⁰(l)) query time' when the distance between two strings is the Hamming distance. These bounds essentially match the earlier bounds of [12], which assumed that the pattern length m is fixed in advance. Furthermore, our data structure can be constructed in O (n1+1/c + n1+⁰(1)M1/3) time, where M is an upper bound for m. This time essentially matches the preprocessing time of [12] as long as the term O(n1+1/c) dominates the running time, which is the case when, for example, c < 3. We also extend our results to the case where the distances are measured according to the lI distance. The query time and the space bound are essentially the same, while the preprocessing time becomes 6 (n'+/c + nl+o(l)M2/3) (We use notation f(n) = O(g(n)) to denote f(n) = g(n) logO(1) g(n)).by Alexandr Andoni.M.Eng
- …
