Piotr Indyk

ICML Conference 2025 Conference Paper

Contradiction Retrieval via Contrastive Learning with Sparsity

• Haike Xu
• Zongyu Lin
• Kai-Wei Chang 0001
• Yizhou Sun
• Piotr Indyk

Contradiction retrieval refers to identifying and extracting documents that explicitly disagree with or refute the content of a query, which is important to many downstream applications like fact checking and data cleaning. To retrieve contradiction argument to the query from large document corpora, existing methods such as similarity search and cross-encoder models exhibit different limitations. To address these challenges, we introduce a novel approach: SparseCL that leverages specially trained sentence embeddings designed to preserve subtle, contradictory nuances between sentences. Our method utilizes a combined metric of cosine similarity and a sparsity function to efficiently identify and retrieve documents that contradict a given query. This approach dramatically enhances the speed of contradiction detection by reducing the need for exhaustive document comparisons to simple vector calculations. We conduct contradiction retrieval experiments on Arguana, MSMARCO, and HotpotQA, where our method produces an average improvement of $11. 0%$ across different models. We also validate our method on downstream tasks like natural language inference and cleaning corrupted corpora. This paper outlines a promising direction for non-similarity-based information retrieval which is currently underexplored.

ICML Conference 2025 Conference Paper

Graph-Based Algorithms for Diverse Similarity Search

• Piyush Anand
• Piotr Indyk
• Ravishankar Krishnaswamy
• Sepideh Mahabadi
• Vikas C. Raykar
• Kirankumar Shiragur
• Haike Xu

Nearest neighbor search is a fundamental data structure problem with many applications. Although the main objective of the data structure is to quickly report data points that are closest to a given query, it has long been noted that without additional constraints the reported answers can be redundant and/or duplicative. This issue is typically addressed in two stages: in the first stage, the algorithm retrieves a (large) number $r$ of points closest to the query, while in the second stage, the $r$ points are post-processed and a small subset is selected to maximize the desired diversity objective. Although popular, this method suffers from a fundamental efficiency bottleneck, as the set of points retrieved in the first stage often needs to be much larger than the final output. In this paper we present provably efficient algorithms for approximate nearest neighbor search with diversity constraints that bypass this two stage process. Our algorithms are based on popular graph-based methods, which allows us to “piggy-back” on the existing efficient implementations. These are the first graph-based algorithms for nearest neighbor search with diversity constraints. For data sets with low intrinsic dimension, our data structures report a diverse set of $k$ points approximately closest to the query, in time that only depends on $k$ and $\log \Delta$, where $\Delta$ is the ratio of the diameter to the closest pair distance in the data set. This bound is qualitatively similar to the best known bounds for standard (non-diverse) graph-based algorithms. Our experiments show that the search time of our algorithms is substantially lower than that using the standard two-stage approach.

ICLR Conference 2025 Conference Paper

Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions

• Piotr Indyk
• Michael Kapralov
• Kshiteej Sheth
• Tal Wagner

Motivated by the problem of fast processing of attention matrices, we study fast algorithms for computing matrix-vector products for asymmetric Gaussian Kernel matrices $K\in \mathbb{R}^{n\times n}$. $K$'s columns are indexed by a set of $n$ keys $k_1,k_2\ldots, k_n\in \mathbb{R}^d$, rows by a set of $n$ queries $q_1,q_2,\ldots,q_n\in \mathbb{R}^d $, and its $i,j$ entry is $K_{ij} = e^{-\|q_i-k_j\|_2^2/2\sigma^2}$ for some bandwidth parameter $\sigma>0$. Given a vector $x\in \mathbb{R}^n$ and error parameter $\epsilon>0$, our task is to output a $y\in \mathbb{R}^n$ such that $\|Kx-y\|_2\leq \epsilon \|x\|_2$ in time subquadratic in $n$ and linear in $d$. Our algorithms rely on the following modelling assumption about the matrices $K$: the sum of the entries of $K$ scales linearly in $n$, as opposed to worst case quadratic growth. We validate this assumption experimentally, for Gaussian kernel matrices encountered in various settings such as fast attention computation in LLMs. Under this assumption, we obtain the first subquadratic time algorithm for kernel matrix-vector multiplication for unrestricted vectors.

NeurIPS Conference 2024 Conference Paper

Optimal Algorithms for Augmented Testing of Discrete Distributions

• Maryam Aliakbarpour
• Piotr Indyk
• Ronitt Rubinfeld
• Sandeep Silwal

We consider the problem of hypothesis testing for discrete distributions. In the standard model, where we have sample access to an underlying distribution $p$, extensive research has established optimal bounds for uniformity testing, identity testing (goodness of fit), and closeness testing (equivalence or two-sample testing). We explore these problems in a setting where a predicted data distribution, possibly derived from historical data or predictive machine learning models, is available. We demonstrate that such a predictor can indeed reduce the number of samples required for all three property testing tasks. The reduction in sample complexity depends directly on the predictor’s quality, measured by its total variation distance from $p$. A key advantage of our algorithms is their adaptability to the precision of the prediction. Specifically, our algorithms can self-adjust their sample complexity based on the accuracy of the available prediction, operating without any prior knowledge of the estimation’s accuracy (i. e. they are consistent). Additionally, we never use more samples than the standard approaches require, even if the predictions provide no meaningful information (i. e. they are also robust). We provide lower bounds to indicate that the improvements in sample complexity achieved by our algorithms are information-theoretically optimal. Furthermore, experimental results show that the performance of our algorithms on real data significantly exceeds our worst-case guarantees for sample complexity, demonstrating the practicality of our approach.

NeurIPS Conference 2024 Conference Paper

Statistical-Computational Trade-offs for Density Estimation

• Anders Aamand
• Alexandr Andoni
• Justin Y. Chen
• Piotr Indyk
• Shyam Narayanan
• Sandeep Silwal
• Haike Xu

We study the density estimation problem defined as follows: given $k$ distributions $p_1, \ldots, p_k$ over a discrete domain $[n]$, as well as a collection of samples chosen from a "query" distribution $q$ over $[n]$, output $p_i$ that is "close" to $q$. Recently Aamand et al. gave the first and only known result that achieves sublinear bounds in both the sampling complexity and the query time while preserving polynomial data structure space. However, their improvement over linear samples and time is only by subpolynomial factors. Our main result is a lower bound showing that, for a broad class of data structures, their bounds cannot be significantly improved. In particular, if an algorithm uses $O(n/\log^c k)$ samples for some constant $c>0$ and polynomial space, then the query time of the data structure must be at least $k^{1-O(1)/\log \log k}$, i. e. , close to linear in the number of distributions $k$. This is a novel statistical-computational trade-off for density estimation, demonstrating that any data structure must use close to a linear number of samples or take close to linear query time. The lower bound holds even in the realizable case where $q=p_i$ for some $i$, and when the distributions are flat (specifically, all distributions are uniform over half of the domain $[n]$). We also give a simple data structure for our lower bound instance with asymptotically matching upper bounds. Experiments show that the data structure is quite efficient in practice.

ICML Conference 2023 Conference Paper

Data Structures for Density Estimation

• Anders Aamand
• Alexandr Andoni
• Justin Y. Chen
• Piotr Indyk
• Shyam Narayanan
• Sandeep Silwal

We study statistical/computational tradeoffs for the following density estimation problem: given $k$ distributions $v_1, \ldots, v_k$ over a discrete domain of size $n$, and sampling access to a distribution $p$, identify $v_i$ that is "close" to $p$. Our main result is the first data structure that, given a sublinear (in $n$) number of samples from $p$, identifies $v_i$ in time sublinear in $k$. We also give an improved version of the algorithm of Acharya et al. (2018) that reports $v_i$ in time linear in $k$. The experimental evaluation of the latter algorithm shows that it achieves a significant reduction in the number of operations needed to achieve a given accuracy compared to prior work.

NeurIPS Conference 2023 Conference Paper

Differentially Private Approximate Near Neighbor Counting in High Dimensions

• Alexandr Andoni
• Piotr Indyk
• Sepideh Mahabadi
• Shyam Narayanan

Range counting (e. g. , counting the number of data points falling into a given query ball) under differential privacy has been studied extensively. However, the current algorithms for this problem are subject to the following dichotomy. One class of algorithms suffers from an additive error that is a fixed polynomial in the number of points. Another class of algorithms allows for polylogarithmic additive error, but the error grows exponentially in the dimension. To achieve the latter, the problem is relaxed to allow a “fuzzy” definition of the range boundary, e. g. , a count of the points in a ball of radius $r$ might also include points in a ball of radius $cr$ for some $c>1$. In this paper we present an efficient algorithm that offers a sweet spot between these two classes. The algorithm has an additive error that is an arbitrary small power of the data set size, depending on how fuzzy the range boundary is, as well as a small ($1+o(1)$) multiplicative error. Crucially, the amount of noise added has no dependence on the dimension. Our algorithm introduces a variant of Locality-Sensitive Hashing, utilizing it in a novel manner.

NeurIPS Conference 2023 Conference Paper

Near-Linear Time Algorithm for the Chamfer Distance

• Ainesh Bakshi
• Piotr Indyk
• Rajesh Jayaram
• Sandeep Silwal
• Erik Waingarten

For any two point sets $A, B \subset \mathbb{R}^d$ of size up to $n$, the Chamfer distance from $A$ to $B$ is defined as $\texttt{CH}(A, B)=\sum_{a \in A} \min_{b \in B} d_X(a, b)$, where $d_X$ is the underlying distance measure (e. g. , the Euclidean or Manhattan distance). The Chamfer distance is a popular measure of dissimilarity between point clouds, used in many machine learning, computer vision, and graphics applications, and admits a straightforward $O(d n^2)$-time brute force algorithm. Further, Chamfer distance is often used as a proxy for the more computationally demanding Earth-Mover (Optimal Transport) Distance. However, the \emph{quadratic} dependence on $n$ in the running time makes the naive approach intractable for large datasets. We overcome this bottleneck and present the first $(1+\epsilon)$-approximate algorithm for estimating Chamfer distance with a near-linear running time. Specifically, our algorithm runs in time $O(nd \log (n)/\epsilon^2)$ and is implementable. Our experiments demonstrate that it is both accurate and fast on large high-dimensional datasets. We believe that our algorithm will open new avenues for analyzing large high-dimensional point clouds. We also give evidence that if the goal is to report a $(1+\epsilon)$-approximate mapping from $A$ to $B$ (as opposed to just its value), then any sub-quadratic time algorithm is unlikely to exist.

ICLR Conference 2023 Conference Paper

Subquadratic Algorithms for Kernel Matrices via Kernel Density Estimation

• Ainesh Bakshi
• Piotr Indyk
• Praneeth Kacham
• Sandeep Silwal
• Samson Zhou

Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel methods (learning and inference using kernel matrices) is efficiency -- given $n$ input points, most kernel-based algorithms need to materialize the full $n \times n$ kernel matrix before performing any subsequent computation, thus incurring $\Omega(n^2)$ runtime. Breaking this quadratic barrier for various problems has therefore, been a subject of extensive research efforts. We break the quadratic barrier and obtain \emph{subquadratic} time algorithms for several fundamental linear-algebraic and graph processing primitives, including approximating the top eigenvalue and eigenvector, spectral sparsification, solving linear systems, local clustering, low-rank approximation, arboricity estimation and counting weighted triangles. We build on the recently developed Kernel Density Estimation framework, which (after preprocessing in time subquadratic in $n$) can return estimates of row/column sums of the kernel matrix. In particular, we develop efficient reductions from \emph{weighted vertex} and \emph{weighted edge sampling} on kernel graphs, \emph{simulating random walks} on kernel graphs, and \emph{importance sampling} on matrices to Kernel Density Estimation and show that we can generate samples from these distributions in \emph{sublinear} (in the support of the distribution) time. Our reductions are the central ingredient in each of our applications and we believe they may be of independent interest. We empirically demonstrate the efficacy of our algorithms on low-rank approximation (LRA) and spectral sparsification, where we observe a $\textbf{9x}$ decrease in the number of kernel evaluations over baselines for LRA and a $\textbf{41x}$ reduction in the graph size for spectral sparsification.

NeurIPS Conference 2023 Conference Paper

Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations

• Piotr Indyk
• Haike Xu

Graph-based approaches to nearest neighbor search are popular and powerful tools for handling large datasets in practice, but they have limited theoretical guarantees. We study the worst-case performance of recent graph-based approximate nearest neighbor search algorithms, such as HNSW, NSG and DiskANN. For DiskANN, we show that its "slow preprocessing'' version provably supports approximate nearest neighbor search query with constant approximation ratio and poly-logarithmic query time, on data sets with bounded "intrinsic'' dimension. For the other data structure variants studied, including DiskANN with "fast preprocessing'', HNSW and NSG, we present a family of instances on which the empirical query time required to achieve a "reasonable'' accuracy is linear in instance size. For example, for DiskANN, we show that the query procedure can take at least $0. 1 n$ steps on instances of size $n$ before it encounters any of the $5$ nearest neighbors of the query.

NeurIPS Conference 2022 Conference Paper

(Optimal) Online Bipartite Matching with Degree Information

• Anders Aamand
• Justin Chen
• Piotr Indyk

We propose a model for online graph problems where algorithms are given access to an oracle that predicts (e. g. , based on modeling assumptions or past data) the degrees of nodes in the graph. Within this model, we study the classic problem of online bipartite matching, and a natural greedy matching algorithm called MinPredictedDegree, which uses predictions of the degrees of offline nodes. For the bipartite version of a stochastic graph model due to Chung, Lu, and Vu where the expected values of the offline degrees are known and used as predictions, we show that MinPredictedDegree stochastically dominates any other online algorithm, i. e. , it is optimal for graphs drawn from this model. Since the "symmetric" version of the model, where all online nodes are identical, is a special case of the well-studied "known i. i. d. model", it follows that the competitive ratio of MinPredictedDegree on such inputs is at least 0. 7299. For the special case of graphs with power law degree distributions, we show that MinPredictedDegree frequently produces matchings almost as large as the true maximum matching on such graphs. We complement these results with an extensive empirical evaluation showing that MinPredictedDegree compares favorably to state-of-the-art online algorithms for online matching.

NeurIPS Conference 2022 Conference Paper

Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks

• Anders Aamand
• Justin Chen
• Piotr Indyk
• Shyam Narayanan
• Ronitt Rubinfeld
• Nicholas Schiefer
• Sandeep Silwal
• Tal Wagner

Recent work shows that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman (WL) graph test. In particular, they show that the WL test can be simulated by GNNs. However, those simulations involve neural networks for the “combine” function of size polynomial or even exponential in the number of graph nodes $n$, as well as feature vectors of length linear in $n$. We present an improved simulation of the WL test on GNNs with {\em exponentially} lower complexity. In particular, the neural network implementing the combine function in each node has only $\mathrm{polylog}(n)$ parameters, and the feature vectors exchanged by the nodes of GNN consists of only $O(\log n)$ bits. We also give logarithmic lower bounds for the feature vector length and the size of the neural networks, showing the (near)-optimality of our construction.

NeurIPS Conference 2022 Conference Paper

Faster Linear Algebra for Distance Matrices

• Piotr Indyk
• Sandeep Silwal

The distance matrix of a dataset $X$ of $n$ points with respect to a distance function $f$ represents all pairwise distances between points in $X$ induced by $f$. Due to their wide applicability, distance matrices and related families of matrices have been the focus of many recent algorithmic works. We continue this line of research and take a broad view of algorithm design for distance matrices with the goal of designing fast algorithms, which are specifically tailored for distance matrices, for fundamental linear algebraic primitives. Our results include efficient algorithms for computing matrix-vector products for a wide class of distance matrices, such as the $\ell_1$ metric for which we get a linear runtime, as well as an $\Omega(n^2)$ lower bound for any algorithm which computes a matrix-vector product for the $\ell_{\infty}$ case, showing a separation between the $\ell_1$ and the $\ell_{\infty}$ metrics. Our upper bound results in conjunction with recent works on the matrix-vector query model have many further downstream applications, including the fastest algorithm for computing a relative error low-rank approximation for the distance matrix induced by $\ell_1$ and $\ell_2^2$ functions and the fastest algorithm for computing an additive error low-rank approximation for the $\ell_2$ metric, in addition to applications for fast matrix multiplication among others. We also give algorithms for constructing distance matrices and show that one can construct an approximate $\ell_2$ distance matrix in time faster than the bound implied by the Johnson-Lindenstrauss lemma.

SODA Conference 2022 Conference Paper

Frequency Estimation with One-Sided Error

• Piotr Indyk
• Shyam Narayanan
• David P. Woodruff

Frequency estimation, also known as the Point Query problem, is one of the most fundamental problems in streaming algorithms. Given a stream S of elements from some universe U = {1 … n }, the goal is to compute, in a single pass, a short “sketch” of S so that for any element i ∊ U, one can estimate the number x i of times i occurs in S based on the sketch alone. Two state of the art solutions to this problems are Count-Min and Count-Sketch algorithms. They are based on linear sketches, which means that the data elements can be deleted as well as inserted and sketches for two different streams can be combined via addition. However, the guarantees offered by Count-Min and Count-Sketch are incomparable. The frequency estimator x produced by Count-Min sketch, using O (1/ ∊ ·log n ) dimensions, guarantees that with high probability, and holds deterministically. Also, Count-Min works under the assumption that x ≥ 0. On the other hand, Count-Sketch, using O (1/ ∊ 2 · log n ) dimensions, guarantees that with high probability. A natural question is whether it is possible to design the “best of both worlds” sketching method, with error guarantees depending on the ℓ 2 norm and space comparable to Count-Sketch, but (like Count-Min) also has the no-underestimation property. Our main set of results shows that the answer to the above question is negative. We show this in two incomparable computational models: linear sketching and streaming algorithms. Specifically, we show that: Any linear sketch satisfying the ℓ p norm error guarantee with probability at least 2/3 and having the no-underestimation property must be of dimension of at least Ω( n 1–1/ p / ∊ ), even if the sketched vectors are non-negative. This bound is tight, as we also give a linear sketch of dimension O ( n 1–1/ p / ∊ ) satisfying these properties. Any streaming algorithm satisfying the ℓ p norm error guarantee with probability at least 2/3 and having the no-underestimation property must use at least Ω(n 1–1/ p / ∊ ) bits. This holds even for algorithms that only allow insertions and make any constant number of passes over the stream. This bound is tight up to a logarithmic factor. We also study the complementary problem, where the sketch is required to not over -estimate, i. e. , should hold always. We show that any linear sketch satisfying this property and having the ℓ p error guarantee with probability at least 2/3 must be of dimension at least Ω ( n 1–1/ p / ∊ ). We also show that this bound is tight up to polylogarithmic factors, by providing an appropriate linear sketch.

ICML Conference 2022 Conference Paper

Streaming Algorithms for Support-Aware Histograms

• Justin Y. Chen
• Piotr Indyk
• Tal Wagner

Histograms, i. e. , piece-wise constant approximations, are a popular tool used to represent data distributions. Traditionally, the difference between the histogram and the underlying distribution (i. e. , the approximation error) is measured using the L_p norm, which sums the differences between the two functions over all items in the domain. Although useful in many applications, the drawback of this error measure is that it treats approximation errors of all items in the same way, irrespective of whether the mass of an item is important for the downstream application that uses the approximation. As a result, even relatively simple distributions cannot be approximated by succinct histograms without incurring large error. In this paper, we address this issue by adapting the definition of approximation so that only the errors of the items that belong to the support of the distribution are considered. Under this definition, we develop efficient 1-pass and 2-pass streaming algorithms that compute near-optimal histograms in sub-linear space. We also present lower bounds on the space complexity of this problem. Surprisingly, under this notion of error, there is an exponential gap in the space complexity of 1-pass and 2-pass streaming algorithms. Finally, we demonstrate the utility of our algorithms on a collection of real and synthetic data sets.

ICLR Conference 2022 Conference Paper

Triangle and Four Cycle Counting with Predictions in Graph Streams

• Justin Y. Chen
• Talya Eden
• Piotr Indyk
• Honghao Lin
• Shyam Narayanan
• Ronitt Rubinfeld
• Sandeep Silwal
• Tal Wagner

We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles, two fundamental problems in graph analytics that are widely studied in the graph data stream literature. Recently, Hsu et al. (2019) and Jiang et al. (2020) applied machine learning techniques in other data stream problems, using a trained oracle that can predict certain properties of the stream elements to improve on prior “classical” algorithms that did not use oracles. In this paper, we explore the power of a “heavy edge” oracle in multiple graph edge streaming models. In the adjacency list model, we present a one-pass triangle counting algorithm improving upon the previous space upper bounds without such an oracle. In the arbitrary order model, we present algorithms for both triangle and four cycle estimation with fewer passes and the same space complexity as in previous algorithms, and we show several of these bounds are optimal. We analyze our algorithms under several noise models, showing that the algorithms perform well even when the oracle errs. Our methodology expands upon prior work on “classical” streaming algorithms, as previous multi-pass and random order streaming algorithms can be seen as special cases of our algorithms, where the first pass or random order was used to implement the heavy edge oracle. Lastly, our experiments demonstrate advantages of the proposed method compared to state-of-the-art streaming algorithms.

ICML Conference 2021 Conference Paper

Faster Kernel Matrix Algebra via Density Estimation

• Arturs Backurs
• Piotr Indyk
• Cameron Musco
• Tal Wagner

We study fast algorithms for computing basic properties of an n x n positive semidefinite kernel matrix K corresponding to n points x_1, .. ., x_n in R^d. In particular, we consider the estimating the sum of kernel matrix entries, along with its top eigenvalue and eigenvector. These are some of the most basic problems defined over kernel matrices. We show that the sum of matrix entries can be estimated up to a multiplicative factor of 1+\epsilon in time sublinear in n and linear in d for many popular kernel functions, including the Gaussian, exponential, and rational quadratic kernels. For these kernels, we also show that the top eigenvalue (and a witnessing approximate eigenvector) can be approximated to a multiplicative factor of 1+\epsilon in time sub-quadratic in n and linear in d. Our algorithms represent significant advances in the best known runtimes for these problems. They leverage the positive definiteness of the kernel matrix, along with a recent line of work on efficient kernel density estimation.

NeurIPS Conference 2021 Conference Paper

Few-Shot Data-Driven Algorithms for Low Rank Approximation

• Piotr Indyk
• Tal Wagner
• David Woodruff

Recently, data-driven and learning-based algorithms for low rank matrix approximation were shown to outperform classical data-oblivious algorithms by wide margins in terms of accuracy. Those algorithms are based on the optimization of sparse sketching matrices, which lead to large savings in time and memory during testing. However, they require long training times on a large amount of existing data, and rely on access to specialized hardware and software. In this work, we develop new data-driven low rank approximation algorithms with better computational efficiency in the training phase, alleviating these drawbacks. Furthermore, our methods are interpretable: while previous algorithms choose the sketching matrix either at random or by black-box learning, we show that it can be set (or initialized) to clearly interpretable values extracted from the dataset. Our experiments show that our algorithms, either by themselves or in combination with previous methods, achieve significant empirical advantage over previous work, improving training times by up to an order of magnitude toward achieving the same target accuracy.

ICLR Conference 2021 Conference Paper

Learning-based Support Estimation in Sublinear Time

• Talya Eden
• Piotr Indyk
• Shyam Narayanan
• Ronitt Rubinfeld
• Sandeep Silwal
• Tal Wagner

We consider the problem of estimating the number of distinct elements in a large data set (or, equivalently, the support size of the distribution induced by the data set) from a random sample of its elements. The problem occurs in many applications, including biology, genomics, computer systems and linguistics. A line of research spanning the last decade resulted in algorithms that estimate the support up to $ \pm \varepsilon n$ from a sample of size $O(\log^2(1/\varepsilon) \cdot n/\log n)$, where $n$ is the data set size. Unfortunately, this bound is known to be tight, limiting further improvements to the complexity of this problem. In this paper we consider estimation algorithms augmented with a machine-learning-based predictor that, given any element, returns an estimation of its frequency. We show that if the predictor is correct up to a constant approximation factor, then the sample complexity can be reduced significantly, to $$ \ \log (1/\varepsilon) \cdot n^{1-\Theta(1/\log(1/\varepsilon))}. $$ We evaluate the proposed algorithms on a collection of data sets, using the neural-network based estimators from {Hsu et al, ICLR'19} as predictors. Our experiments demonstrate substantial (up to 3x) improvements in the estimation accuracy compared to the state of the art algorithm.

ICML Conference 2021 Conference Paper

Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering

• Shyam Narayanan
• Sandeep Silwal
• Piotr Indyk
• Or Zamir

Random dimensionality reduction is a versatile tool for speeding up algorithms for high-dimensional problems. We study its application to two clustering problems: the facility location problem, and the single-linkage hierarchical clustering problem, which is equivalent to computing the minimum spanning tree. We show that if we project the input pointset $X$ onto a random $d = O(d_X)$-dimensional subspace (where $d_X$ is the doubling dimension of $X$), then the optimum facility location cost in the projected space approximates the original cost up to a constant factor. We show an analogous statement for minimum spanning tree, but with the dimension $d$ having an extra $\log \log n$ term and the approximation factor being arbitrarily close to $1$. Furthermore, we extend these results to approximating {\em solutions} instead of just their {\em costs}. Lastly, we provide experimental results to validate the quality of solutions and the speedup due to the dimensionality reduction. Unlike several previous papers studying this approach in the context of $k$-means and $k$-medians, our dimension bound does not depend on the number of clusters but only on the intrinsic dimensionality of $X$.

SODA Conference 2020 Conference Paper

Composable Core-sets for Determinant Maximization Problems via Spectral Spanners

• Piotr Indyk
• Sepideh Mahabadi
• Shayan Oveis Gharan
• Alireza Rezaei 0001

We study a generalization of classical combinatorial graph spanners to the spectral setting. Given a set of vectors V ⊆ ℝ d, we say a set U ⊆ V is an α -spectral k spanner, for k ≤ d, if for all v ϵ V there is a probability distribution μ v supported on U such that where for two matrices A, B ϵ ℝ d × d we write iff the sum of the bottom d – k + 1 eigenvalues of B – A is nonnegative. In particular, iff. We show that any set V has an Õ ( k )-spectral spanner of size Õ ( k ) and this bound is almost optimal in the worst case. We use spectral spanners to study composable coresets for spectral problems. We show that for many objective functions one can use a spectral spanner, independent of the underlying function, as a core-set and obtain almost optimal composable core-sets. For example, for the k -determinant maximization problem, we obtain an Õ ( k ) k -composable core-set, and we show that this is almost optimal in the worst case. Our algorithm is a spectral analogue of the classical greedy algorithm for finding (combinatorial) spanners in graphs. We expect that our spanners find many other applications in distributed or parallel models of computation.

ICLR Conference 2020 Conference Paper

Learning Space Partitions for Nearest Neighbor Search

• Yihe Dong
• Piotr Indyk
• Ilya P. Razenshteyn
• Tal Wagner

Space partitions of $\mathbb{R}^d$ underlie a vast and important class of fast nearest neighbor search (NNS) algorithms. Inspired by recent theoretical work on NNS for general metric spaces (Andoni et al. 2018b,c), we develop a new framework for building space partitions reducing the problem to balanced graph partitioning followed by supervised classification. We instantiate this general approach with the KaHIP graph partitioner (Sanders and Schulz 2013) and neural networks, respectively, to obtain a new partitioning procedure called Neural Locality-Sensitive Hashing (Neural LSH). On several standard benchmarks for NNS (Aumuller et al. 2017), our experiments show that the partitions obtained by Neural LSH consistently outperform partitions found by quantization-based and tree-based methods as well as classic, data-oblivious LSH.

ICML Conference 2020 Conference Paper

Scalable Nearest Neighbor Search for Optimal Transport

• Arturs Backurs
• Yihe Dong
• Piotr Indyk
• Ilya P. Razenshteyn
• Tal Wagner

The Optimal Transport (a. k. a. Wasserstein) distance is an increasingly popular similarity measure for rich data domains, such as images or text documents. This raises the necessity for fast nearest neighbor search algorithms according to this distance, which poses a substantial computational bottleneck on massive datasets. In this work we introduce Flowtree, a fast and accurate approximation algorithm for the Wasserstein-1 distance. We formally analyze its approximation factor and running time. We perform extensive experimental evaluation of nearest neighbor search algorithms in the W_1 distance on real-world dataset. Our results show that compared to previous state of the art, Flowtree achieves up to 7. 4 times faster running time.

ICML Conference 2019 Conference Paper

Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm

• Sepideh Mahabadi
• Piotr Indyk
• Shayan Oveis Gharan
• Alireza Rezaei 0001

“Composable core-sets” are an efficient framework for solving optimization problems in massive data models. In this work, we consider efficient construction of composable core-sets for the determinant maximization problem. This can also be cast as the MAP inference task for “determinantal point processes", that have recently gained a lot of interest for modeling diversity and fairness. The problem was recently studied in \cite{indyk2018composable}, where they designed composable core-sets with the optimal approximation bound of $O(k)^k$. On the other hand, the more practical “Greedy" algorithm has been previously used in similar contexts. In this work, first we provide a theoretical approximation guarantee of $C^{k^2}$ for the Greedy algorithm in the context of composable core-sets; Further, we propose to use a “Local Search" based algorithm that while being still practical, achieves a nearly optimal approximation bound of $O(k)^{2k}$; Finally, we implement all three algorithms and show the effectiveness of our proposed algorithm on standard data sets.

NeurIPS Conference 2019 Conference Paper

Estimating Entropy of Distributions in Constant Space

• Jayadev Acharya
• Sourbh Bhadane
• Piotr Indyk
• Ziteng Sun

We consider the task of estimating the entropy of $k$-ary distributions from samples in the streaming model, where space is limited. Our main contribution is an algorithm that requires $O\left(\frac{k \log (1/\varepsilon)^2}{\varepsilon^3}\right)$ samples and a constant $O(1)$ memory words of space and outputs a $\pm\varepsilon$ estimate of $H(p)$. Without space limitations, the sample complexity has been established as $S(k, \varepsilon)=\Theta\left(\frac k{\varepsilon\log k}+\frac{\log^2 k}{\varepsilon^2}\right)$, which is sub-linear in the domain size $k$, and the current algorithms that achieve optimal sample complexity also require nearly-linear space in $k$. Our algorithm partitions $[0, 1]$ into intervals and estimates the entropy contribution of probability values in each interval. The intervals are designed to trade bias and variance. Distribution property estimation and testing with limited memory is a largely unexplored research area. We hope our work will motivate research in this field.

NeurIPS Conference 2019 Conference Paper

Learning-Based Low-Rank Approximations

• Piotr Indyk
• Ali Vakilian
• Yang Yuan

We introduce a “learning-based” algorithm for the low-rank decomposition problem: given an $n \times d$ matrix $A$, and a parameter $k$, compute a rank-$k$ matrix $A'$ that minimizes the approximation loss $\|A-A'\|_F$. The algorithm uses a training set of input matrices in order to optimize its performance. Specifically, some of the most efficient approximate algorithms for computing low-rank approximations proceed by computing a projection $SA$, where $S$ is a sparse random $m \times n$ “sketching matrix”, and then performing the singular value decomposition of $SA$. We show how to replace the random matrix $S$ with a “learned” matrix of the same sparsity to reduce the error. Our experiments show that, for multiple types of data sets, a learned sketch matrix can substantially reduce the approximation loss compared to a random matrix $S$, sometimes up to one order of magnitude. We also study mixed matrices where only some of the rows are trained and the remaining ones are random, and show that matrices still offer improved performance while retaining worst-case guarantees. Finally, to understand the theoretical aspects of our approach, we study the special case of $m=1$. In particular, we give an approximation algorithm for minimizing the empirical loss, with approximation factor depending on the stable rank of matrices in the training set. We also show generalization bounds for the sketch matrix learning problem.

ICML Conference 2019 Conference Paper

Scalable Fair Clustering

• Arturs Backurs
• Piotr Indyk
• Krzysztof Onak
• Baruch Schieber
• Ali Vakilian
• Tal Wagner

We study the fair variant of the classic k-median problem introduced by (Chierichetti et al. , NeurIPS 2017) in which the points are colored, and the goal is to minimize the same average distance objective as in the standard $k$-median problem while ensuring that all clusters have an “approximately equal” number of points of each color. (Chierichetti et al. , NeurIPS 2017) proposed a two-phase algorithm for fair $k$-clustering. In the first step, the pointset is partitioned into subsets called fairlets that satisfy the fairness requirement and approximately preserve the k-median objective. In the second step, fairlets are merged into k clusters by one of the existing k-median algorithms. The running time of this algorithm is dominated by the first step, which takes super-quadratic time. In this paper, we present a practical approximate fairlet decomposition algorithm that runs in nearly linear time.

NeurIPS Conference 2019 Conference Paper

Space and Time Efficient Kernel Density Estimation in High Dimensions

• Arturs Backurs
• Piotr Indyk
• Tal Wagner

Recently, Charikar and Siminelakis (2017) presented a framework for kernel density estimation in provably sublinear query time, for kernels that possess a certain hashing-based property. However, their data structure requires a significantly increased super-linear storage space, as well as super-linear preprocessing time. These limitations inhibit the practical applicability of their approach on large datasets. In this work, we present an improvement to their framework that retains the same query time, while requiring only linear space and linear preprocessing time. We instantiate our framework with the Laplacian and Exponential kernels, two popular kernels which possess the aforementioned property. Our experiments on various datasets verify that our approach attains accuracy and query time similar to Charikar and Siminelakis (2017), with significantly improved space and preprocessing time.

FOCS Conference 2018 Conference Paper

Efficient Density Evaluation for Smooth Kernels

• Arturs Backurs
• Moses Charikar
• Piotr Indyk
• Paris Siminelakis

Given a kernel function k(. ,.) and a dataset P⊂ R^d, the kernel density function of P at a point x∈ R d is equal to KDF P (x): = 1/|P| Σy∈P k(x, y). Kernel density evaluation has numerous applications, in scientific computing, statistics, computer vision, machine learning and other fields. In all of them it is necessary to evaluate KDF P(x) quickly, often for many inputs x and large point-sets P. In this paper we present a collection of algorithms for efficient KDF evaluation under the assumptions that the kernel k is "smooth", i. e. the value changes at most polynomially with the distance. This assumption is satisfied by several well-studied kernels, including the (generalized) t-student kernel and rational quadratic kernel. For smooth kernels, we give a data structure that, after O(dn log (Φ n)/ε^2) preprocessing, estimates KDF P(x) up to a factor of 1 ± ε in O(dlog (Φ n)/ε 2 ) time, where Phi; is the aspect ratio. The log(Φn) term can be further replaced by log n under an additional decay condition on k, which is satisfied by the aforementioned examples. We further extend the results in two ways. First, we use low-distortion embeddings to extend the results to kernels defined for spaces other than ℓ_2. The key feature of this reduction is that the distortion of the embedding affects only the running time of the algorithm, not the accuracy of the estimation. As a result, we obtain (1+ε)-approximate estimation algorithms for kernels over other ℓ p norms, Earth-Mover Distance, and other metric spaces. Second, for smooth kernels that are decreasing with distance, we present a general reduction from density estimation to approximate near neighbor in the underlying space. This allows us to construct algorithms for general doubling metrics, as well as alternative algorithms for l p norms and other spaces.

SODA Conference 2018 Conference Paper

Set Cover in Sub-linear Time

• Piotr Indyk
• Sepideh Mahabadi
• Ronitt Rubinfeld
• Ali Vakilian
• Anak Yodpinyanee

SODA Conference 2017 Conference Paper

Better Approximations for Tree Sparsity in Nearly-Linear Time

• Arturs Backurs
• Piotr Indyk
• Ludwig Schmidt

The Tree Sparsity problem is defined as follows: given a node-weighted tree of size η and an integer k, output a rooted subtree of size k with maximum weight. The best known algorithm solves this problem in time O ( kn ), i. e. , quadratic in the size of the input tree for k = Θ( n ). In this work, we design (1+∊)-approximation algorithms for the Tree Sparsity problem that run in nearly-linear time. Unlike prior algorithms for this problem, our results offer single criterion approximations, i. e. , they do not increase the sparsity of the output solution, and work for arbitrary trees (not only balanced trees). We also provide further algorithms for this problem with different runtime vs approximation trade-offs. Finally, we show that if the exact version of the Tree Sparsity problem can be solved in strongly subquadratic time, then the (min, +) convolution problem can be solved in strongly subquadratic time as well. The latter is a well- studied problem for which no strongly subquadratic time algorithm is known.

SODA Conference 2017 Conference Paper

Near-Optimal (Euclidean) Metric Compression

• Piotr Indyk
• Tal Wagner

NeurIPS Conference 2017 Conference Paper

On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks

• Arturs Backurs
• Piotr Indyk
• Ludwig Schmidt

Empirical risk minimization (ERM) is ubiquitous in machine learning and underlies most supervised learning methods. While there is a large body of work on algorithms for various ERM problems, the exact computational complexity of ERM is still not understood. We address this issue for multiple popular ERM problems including kernel SVMs, kernel ridge regression, and training the final layer of a neural network. In particular, we give conditional hardness results for these problems based on complexity-theoretic assumptions such as the Strong Exponential Time Hypothesis. Under these assumptions, we show that there are no algorithms that solve the aforementioned ERM problems to high accuracy in sub-quadratic time. We also give similar hardness results for computing the gradient of the empirical loss, which is the main computational burden in many non-convex learning tasks.

NeurIPS Conference 2017 Conference Paper

Practical Data-Dependent Metric Compression with Provable Guarantees

• Piotr Indyk
• Ilya Razenshteyn
• Tal Wagner

We introduce a new distance-preserving compact representation of multi-dimensional point-sets. Given n points in a d-dimensional space where each coordinate is represented using B bits (i. e. , dB bits per point), it produces a representation of size O( d log(d B/epsilon) +log n) bits per point from which one can approximate the distances up to a factor of 1 + epsilon. Our algorithm almost matches the recent bound of Indyk et al, 2017} while being much simpler. We compare our algorithm to Product Quantization (PQ) (Jegou et al, 2011) a state of the art heuristic metric compression method. We evaluate both algorithms on several data sets: SIFT, MNIST, New York City taxi time series and a synthetic one-dimensional data set embedded in a high-dimensional space. Our algorithm produces representations that are comparable to or better than those produced by PQ, while having provable guarantees on its performance.

IJCAI Conference 2016 Conference Paper

A Nearly-Linear Time Framework for Graph-Structured Sparsity

• Chinmay Hegde
• Piotr Indyk
• Ludwig Schmidt

We introduce a framework for sparsity structures defined via graphs. Our approach is flexible and generalizes several previously studied sparsity models. Moreover, we provide efficient projection algorithms for our sparsity model that run in nearly-linear time. In the context of sparse recovery, our framework achieves an information-theoretically optimal sample complexity for a wide range of parameters. We complement our theoretical analysis with experiments showing that our algorithms also improve on prior work in practice.

NeurIPS Conference 2016 Conference Paper

Fast recovery from a union of subspaces

• Chinmay Hegde
• Piotr Indyk
• Ludwig Schmidt

We address the problem of recovering a high-dimensional but structured vector from linear observations in a general setting where the vector can come from an arbitrary union of subspaces. This setup includes well-studied problems such as compressive sensing and low-rank matrix recovery. We show how to design more efficient algorithms for the union-of subspace recovery problem by using approximate projections. Instantiating our general framework for the low-rank matrix recovery problem gives the fastest provable running time for an algorithm with optimal sample complexity. Moreover, we give fast approximate projections for 2D histograms, another well-studied low-dimensional model of data. We complement our theoretical results with experiments demonstrating that our framework also leads to improved time and sample complexity empirically.

SODA Conference 2016 Conference Paper

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

• Mahdi Cheraghchi
• Piotr Indyk

SODA Conference 2016 Conference Paper

Nearly-optimal bounds for sparse recovery in generic norms, with applications to k -median sketching

• Arturs Backurs
• Piotr Indyk
• Ilya P. Razenshteyn
• David P. Woodruff

FOCS Conference 2016 Conference Paper

Which Regular Expression Patterns Are Hard to Match?

• Arturs Backurs
• Piotr Indyk

Regular expressions constitute a fundamental notion in formal language theory and are frequently used in computer science to define search patterns. In particular, regular expression matching and membership testing are widely used computational primitives, employed in many programming languages and text processing utilities. A classic algorithm for these problems constructs and simulates a non-deterministic finite automaton corresponding to the expression, resulting in an O(m n) running time (where m is the length of the pattern and n is the length of the text). This running time can be improved slightly (by a polylogarithmic factor), but no significantly faster solutions are known. At the same time, much faster algorithms exist for various special cases of regular expressions, including dictionary matching, wildcard matching, subset matching, word break problem etc. In this paper, we show that the complexity of regular expression matching can be characterized based on its depth (when interpreted as a formula). Our results hold for expressions involving concatenation, OR, Kleene star and Kleene plus. For regular expressions of depth two (involving any combination of the above operators), we show the following dichotomy: matching and membership testing can be solved in near-linear time, except for "concatenations of stars", which cannot be solved in strongly sub-quadratic time assuming the Strong Exponential Time Hypothesis (SETH). For regular expressions of depth three the picture is more complex. Nevertheless, we show that all problems can either be solved in strongly sub-quadratic time, or cannot be solved in strongly sub-quadratic time assuming SETH. An intriguing special case of membership testing involves regular expressions of the form "a star of an OR of concatenations", e. g. , [a|ab|bc]*. This corresponds to the so-called word break problem, for which a dynamic programming algorithm with a runtime of (roughly) O(n √m) is known. We show that the latter bound is not tight and improve the runtime to O(n m 0. 44. .. ).

ICML Conference 2015 Conference Paper

A Nearly-Linear Time Framework for Graph-Structured Sparsity

• Chinmay Hegde
• Piotr Indyk
• Ludwig Schmidt

We introduce a framework for sparsity structures defined via graphs. Our approach is flexible and generalizes several previously studied sparsity models. Moreover, we provide efficient projection algorithms for our sparsity model that run in nearly-linear time. In the context of sparse recovery, we show that our framework achieves an information-theoretically optimal sample complexity for a wide range of parameters. We complement our theoretical analysis with experiments demonstrating that our algorithms improve on prior work also in practice.

STOC Conference 2015 Conference Paper

Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)

• Arturs Backurs
• Piotr Indyk

The edit distance (a.k.a. the Levenshtein distance) between two strings is defined as the minimum number of insertions, deletions or substitutions of symbols needed to transform one string into another. The problem of computing the edit distance between two strings is a classical computational task, with a well-known algorithm based on dynamic programming. Unfortunately, all known algorithms for this problem run in nearly quadratic time. In this paper we provide evidence that the near-quadratic running time bounds known for the problem of computing edit distance might be {tight}. Specifically, we show that, if the edit distance can be computed in time O(n 2-δ ) for some constant δ>0, then the satisfiability of conjunctive normal form formulas with N variables and M clauses can be solved in time M O(1) 2 (1-ε)N for a constant ε>0. The latter result would violate the Strong Exponential Time Hypothesis , which postulates that such algorithms do not exist.

NeurIPS Conference 2015 Conference Paper

Practical and Optimal LSH for Angular Distance

• Alexandr Andoni
• Piotr Indyk
• Thijs Laarhoven
• Ilya Razenshteyn
• Ludwig Schmidt

We show the existence of a Locality-Sensitive Hashing (LSH) family for the angular distance that yields an approximate Near Neighbor Search algorithm with the asymptotically optimal running time exponent. Unlike earlier algorithms with this property (e. g. , Spherical LSH (Andoni-Indyk-Nguyen-Razenshteyn 2014) (Andoni-Razenshteyn 2015)), our algorithm is also practical, improving upon the well-studied hyperplane LSH (Charikar 2002) in practice. We also introduce a multiprobe version of this algorithm and conduct an experimental evaluation on real and synthetic data sets. We complement the above positive results with a fine-grained lower bound for the quality of any LSH family for angular distance. Our lower bound implies that the above LSH family exhibits a trade-off between evaluation time and quality that is close to optimal for a natural class of LSH functions.

SODA Conference 2014 Conference Paper

(Nearly) Sample-Optimal Sparse Fourier Transform

• Piotr Indyk
• Michael Kapralov
• Eric Price 0001

SODA Conference 2014 Conference Paper

Approximation-Tolerant Model-Based Compressive Sensing

• Chinmay Hegde
• Piotr Indyk
• Ludwig Schmidt

SODA Conference 2014 Conference Paper

Beyond Locality-Sensitive Hashing

• Alexandr Andoni
• Piotr Indyk
• Huy L. Nguyen 0001
• Ilya P. Razenshteyn

We present a new data structure for the c-approximate near neighbor problem (ANN) in the Euclidean space. For n points in ℝ d, our algorithm achieves O c ( n ρ + d log n ) query time and O c ( n 1+ ρ + d log n ) space, where ρ ≤ 7/(8 c 2 ) + O (1/ c 3 ) + o c (1). This is the first improvement over the result by Andoni and Indyk (FOCS 2006) and the first data structure that bypasses a locality-sensitive hashing lower bound proved by O'Donnell, Wu and Zhou (ICS 2011). By a standard reduction we obtain a data structure for the Hamming space and ℓ 1 norm with ρ ≤ 7/(8 c )+ O (1/ c 3/2 )+ o c (1), which is the first improvement over the result of Indyk and Motwani (STOC 1998).

FOCS Conference 2014 Conference Paper

Sample-Optimal Fourier Sampling in Any Constant Dimension

• Piotr Indyk
• Michael Kapralov

We give an algorithm for ℓ 2 /ℓ 2 sparse recovery from Fourier measurements using O(k log N) samples, matching the lower bound of Do Ba-Indyk-Price-Woodruff'10 for non-adaptive algorithms up to constant factors for any k ≤ N 1-δ. The algorithm runs in Õ(N) time. Our algorithm extends to higher dimensions, leading to sample complexity of Õ d (k log N), which is optimal up to constant factors for any d = O(1). These are the first sample optimal algorithms for these problems. A preliminary experimental evaluation indicates that our algorithm has empirical sampling complexity comparable to that of other recovery methods known in the literature, while providing strong provable guarantees on the recovery quality.

SODA Conference 2013 Conference Paper

Euclidean spanners in high dimensions

• Sariel Har-Peled
• Piotr Indyk
• Anastasios Sidiropoulos

A classical result in metric geometry asserts that any n -point metric admits a linear-size spanner of dilation O (log n ) [PS89]. More generally, for any c > 1, any metric space admits a spanner of size O ( n 1+1/ c ), and dilation at most c. This bound is tight assuming the well-known girth conjecture of Erdős [Erd63]. We show that for a metric induced by a set of n points in high-dimensional Euclidean space, it is possible to obtain improved dilation/size trade-offs. More specifically, we show that any n -point Euclidean metric admits a near-linear size spanner of dilation O (√log n ). Using the LSH scheme of Andoni and Indyk [AI06] we further show that for any c > 1, there exist spanners of size roughly O ( n 1+1/ c 2 ) and dilation O ( c ). Finally, we also exhibit super-linear lower bounds on the size of spanners with constant dilation.

SODA Conference 2013 Conference Paper

Shift Finding in Sub-Linear Time

• Alexandr Andoni
• Piotr Indyk
• Dina Katabi
• Haitham Hassanieh

We study the following basic pattern matching problem. Consider a “code” sequence c consisting of n bits chosen uniformly at random, and a “signal” sequence x obtained by shifting c (modulo n ) and adding noise. The goal is to efficiently recover the shift with high probability. The problem models tasks of interest in several applications, including GPS synchronization and motion estimation. We present an algorithm that solves the problem in time Õ ( n ( f /(1+ f ) ), where Õ ( N f ) is the running time of the best algorithm for finding the closest pair among N “random” sequences of length O (log N ). A trivial bound of f = 2 leads to a simple algorithm with a running time of Õ ( n 2/3 ). The asymptotic running time can be further improved by plugging in recent more efficient algorithms for the closest pair problem. Our results also yield a sub-linear time algorithm for approximate pattern matching algorithm for a random signal (text), even for the case when the error between the signal and the code (pattern) is asymptotically as large as the code size. This is the first sublinear time algorithm for such error rates.

STOC Conference 2012 Conference Paper

Nearly optimal sparse fourier transform

• Haitham Hassanieh
• Piotr Indyk
• Dina Katabi
• Eric Price 0001

SODA Conference 2012 Conference Paper

Simple and practical algorithm for sparse Fourier transform

• Haitham Hassanieh
• Piotr Indyk
• Dina Katabi
• Eric Price 0001

STOC Conference 2011 Conference Paper

K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance

• Piotr Indyk
• Eric Price 0001

FOCS Conference 2011 Conference Paper

On the Power of Adaptivity in Sparse Recovery

• Piotr Indyk
• Eric Price 0001
• David P. Woodruff

The goal of (stable) sparse recovery is to recover a k-sparse approximation x* of a vector x from linear measurements of x. Specifically, the goal is to recover x* such that ∥x-x*∥ p ≤ C min, k-sparse x, ∥x-x'∥ q for some constant C and norm parameters p and q. It is known that, for p = q=l or p = q = 2, this task can be accomplished using m = O(k log(n/k)) non-adaptive measurements [3] and that this bound is tight [9], [12], [28]. In this paper we show that if one is allowed to perform measurements that are adaptive, then the number of measurements can be considerably reduced. Specifically, for C = 1+∈ and p = q = 2 we show · A scheme with m= O(1/∈ log log (n∈/k)) measurements that uses O(log* k · log log(n∈/k)) rounds. This is a significant improvement over the best possible non-adaptive bound. · A scheme with m = O(1/∈k log(k/∈) + k log(n/k)) measurements that uses two rounds. This improves over the best possible non-adaptive bound. To the best of our knowledge, these are the first results of this type.

SODA Conference 2010 Conference Paper

Efficiently Decodable Non-adaptive Group Testing

• Piotr Indyk
• Hung Q. Ngo 0001
• Atri Rudra

We consider the following “efficiently decodable” non-adaptive group testing problem. There is an unknown string x ∊ {0, 1} n with at most d ones in it. We are allowed to test any subset S ⊆ [ n ] of the indices. The answer to the test tells whether x i = 0 for all i ∊ S or not. The objective is to design as few tests as possible (say, t tests) such that x can be identified as fast as possible (say, poly( t )-time). Efficiently decodable non-adaptive group testing has applications in many areas, including data stream algorithms and data forensics. A non-adaptive group testing strategy can be represented by a t × n matrix, which is the stacking of all the characteristic vectors of the tests. It is well-known that if this matrix is d -disjunct, then any test outcome corresponds uniquely to an unknown input string. Furthermore, we know how to construct d -disjunct matrices with t = O ( d 2 log n ) efficiently. However, these matrices so far only allow for a “decoding” time of O ( nt ), which can be exponentially larger than poly( t ) for relatively small values of d. This paper presents a randomness efficient construction of d -disjunct matrices with t = O ( d 2 log n ) that can be decoded in time poly( d ) · t log 2 t + O ( t ). To the best of our knowledge, this is the first result that achieves an efficient decoding time and matches the best known O ( d 2 log n ) bound on the number of tests. We also derandomize the construction, which results in a polynomial time deterministic construction of such matrices when d = O (log n /log log n ). A crucial building block in our construction is the notion of ( d, ℓ)- list disjunct matrices, which represent the more general “list group testing” problem whose goal is to output less than d + ℓ positions in x, including all the (at most d ) positions that have a one in them. List disjunct matrices turn out to be interesting objects in their own right and were also considered independently by [Cheraghchi, FCT 2009]. We present connections between list disjunct matrices, expanders, dispersers and disjunct matrices. List disjunct matrices have applications in constructing ( d, ℓ)-sparsity separator structures [Ganguly, ISAAC 2008] and in constructing tolerant testers for Reed-Solomon codes in the data stream model.

SODA Conference 2010 Conference Paper

Lower Bounds for Sparse Recovery

• Khanh Do Ba
• Piotr Indyk
• Eric Price 0001
• David P. Woodruff

We consider the following k -sparse recovery problem: design an m × n matrix A, such that for any signal x, given Ax we can efficiently recover ○ satisfying ‖ x – ○‖ 1 ≤ C min k -sparse x′ ‖ x – x′ ‖ 1. It is known that there exist matrices A with this property that have only O ( k log( n/k )) rows. In this paper we show that this bound is tight. Our bound holds even for the more general randomized version of the problem, where A is a random variable, and the recovery algorithm is required to work for any fixed x with constant probability (over A ).

SODA Conference 2009 Conference Paper

Approximate line nearest neighbor in high dimensions

• Alexandr Andoni
• Piotr Indyk
• Robert Krauthgamer
• Huy L. Nguyên

TCS Journal 2009 Journal Article

Efficient computations of ℓ 1 and ℓ ∞ rearrangement distances

• Amihood Amir
• Yonatan Aumann
• Piotr Indyk
• Avivit Levy
• Ely Porat

Recently, a new pattern matching paradigm was proposed, pattern matching with address errors. In this paradigm approximate string matching problems are studied, where the content is unaltered and only the locations of the different entries may change. Specifically, a broad class of problems was defined—the class of rearrangement errors. In this type of error the pattern is transformed through a sequence of rearrangement operations, each with an associated cost. The natural ℓ 1 and ℓ 2 rearrangement systems were considered. The best algorithm presented for general patterns, that may have repeating symbols, is O ( n m ). In this paper, we show that the problem can be approximated in linear time for general patterns! Another natural rearrangement system is considered in this paper—the ℓ ∞ rearrangement distance. For this new rearrangement system efficient exact solutions for different variants of the problem are provided, as well as a faster approximation.

FOCS Conference 2009 Conference Paper

Efficient Sketches for Earth-Mover Distance, with Applications

• Alexandr Andoni
• Khanh Do Ba
• Piotr Indyk
• David P. Woodruff

We 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 [¿] 2, we achieve space ¿ ¿ for approximation O(1/¿), for any desired 0 < ¿ < 1. Our sketch has immediate applications to the streaming and nearest neighbor search problems.

JMLR Journal 2009 Journal Article

Learning Approximate Sequential Patterns for Classification

• Zeeshan Syed
• Piotr Indyk
• John Guttag

In this paper, we present an automated approach to discover patterns that can distinguish between sequences belonging to different labeled groups. Our method searches for approximately conserved motifs that occur with varying statistical properties in positive and negative training examples. We propose a two-step process to discover such patterns. Using locality sensitive hashing (LSH), we first estimate the frequency of all subsequences and their approximate matches within a given Hamming radius in labeled examples. The discriminative ability of each pattern is then assessed from the estimated frequencies by concordance and rank sum testing. The use of LSH to identify approximate matches for each candidate pattern helps reduce the runtime of our method. Space requirements are reduced by decomposing the search problem into an iterative method that uses a single LSH table in memory. We propose two further optimizations to the search for discriminative patterns. Clustering with redundancy based on a 2-approximate solution of the k -center problem decreases the number of overlapping approximate groups while providing exhaustive coverage of the search space. Sequential statistical methods allow the search process to use data from only as many training examples as are needed to assess significance. We evaluated our algorithm on data sets from different applications to discover sequential patterns for classification. On nucleotide sequences from the Drosophila genome compared with random background sequences, our method was able to discover approximate binding sites that were preserved upstream of genes. We observed a similar result in experiments on ChIP-on-chip data. For cardiovascular data from patients admitted with acute coronary syndromes, our pattern discovery approach identified approximately conserved sequences of morphology variations that were predictive of future death in a test population. Our data showed that the use of LSH, clustering, and sequential statistics improved the running time of the search algorithm by an order of magnitude without any noticeable effect on accuracy. These results suggest that our methods may allow for an unsupervised approach to efficiently learn interesting dissimilarities between positive and negative examples that may have a functional role. [abs] [ pdf ][ bib ] &copy JMLR 2009. ( edit, beta )

SODA Conference 2009 Conference Paper

Overcoming the l 1 non-embeddability barrier: algorithms for product metrics

• Alexandr Andoni
• Piotr Indyk
• Robert Krauthgamer

SODA Conference 2008 Conference Paper

Declaring independence via the sketching of sketches

• Piotr Indyk
• Andrew McGregor 0001

SODA Conference 2008 Conference Paper

Earth mover distance over high-dimensional spaces

• Alexandr Andoni
• Piotr Indyk
• Robert Krauthgamer

SODA Conference 2008 Conference Paper

Explicit constructions for compressed sensing of sparse signals

• Piotr Indyk

FOCS Conference 2008 Conference Paper

Near-Optimal Sparse Recovery in the L1 Norm

• Piotr Indyk
• Milan Ruzic

We consider the *approximate sparse recovery problem*, where the goal is to (approximately) recover a high-dimensional vector x from Rn from its lower-dimensional *sketch* Ax from Rm. Specifically, we focus on the sparse recovery problem in the L1 norm: for a parameter k, given the sketch Ax, compute an approximation x' of x such that the L1 approximation error | |x-x'| | is close to minimum of | |x-x*| | over all vectors x* with at most k terms. The sparse recovery problem has been subject to extensive research over the last few years. Many solutions to this problem have been discovered, achieving different trade-offs between various attributes, such as the sketch length, encoding and recovery times. In this paper we provide a sparse recovery scheme which achieves close to optimal performance on virtually all attributes. In particular, this is the first recovery scheme that guarantees k log(n/k) sketch length, and near-linear n log (n/k) recovery time *simultaneously*. It also features low encoding and update times, and is noise-resilient.

SODA Conference 2007 Conference Paper

A near linear time constant factor approximation for Euclidean bichromatic matching (cost)

• Piotr Indyk

SODA Conference 2007 Conference Paper

Approximation algorithms for embedding general metrics into trees

• Mihai Badoiu
• Piotr Indyk
• Anastasios Sidiropoulos

STOC Conference 2007 Conference Paper

Uncertainty principles, extractors, and explicit embeddings of l2 into l1

• Piotr Indyk

We give an explicit construction of a constant distortion embedding F of l 2 n into l 1 m , with m=n 1+o(1) .As a bonus, our embedding also has good computational properties: for any input x , Fx can be computed in n 1+o(1) time.The previously known mappings required Ω(n 2 ) evaluation time.

SODA Conference 2006 Conference Paper

Efficient algorithms for substring near neighbor problem

• Alexandr Andoni
• Piotr Indyk

FOCS Conference 2006 Conference Paper

Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions

• Alexandr Andoni
• Piotr Indyk

We present an algorithm for the c-approximate nearest neighbor problem in a d-dimensional Euclidean space, achieving query time of O(dn 1 c2/+o(1)) and space O(dn + n 1+1 c2/+o(1)). This almost matches the lower bound for hashing-based algorithm recently obtained in (R. Motwani et al. , 2006). We also obtain a space-efficient version of the algorithm, which uses dn+n log O(1) n space, with a query time of dn O(1/c2). Finally, we discuss practical variants of the algorithms that utilize fast bounded-distance decoders for the Leech lattice

FOCS Conference 2006 Conference Paper

On the Optimality of the Dimensionality Reduction Method

• Alexandr Andoni
• Piotr Indyk
• Mihai Patrascu

We investigate the optimality of (1+\in )-approximation algorithms obtained via the dimensionality reduction method. We show that: --Any data structure for the (1+\in )-approximate nearest neighbor problem in Hamming space, which uses constant number of probes to answer each query, must use n^{\Omega \left( {1/ \in ^2 } \right)} space. --Any algorithm for the (1+\in )-approximate closest substring problem must run in time exponential in 1/ \in ^{2 - \gamma } for any \gamma > 0 (unless 3SAT can be solved in subexponential time) Both lower bounds are (essentially) tight.

STOC Conference 2005 Conference Paper

Low-distortion embeddings of general metrics into the line

• Mihai Badoiu
• Julia Chuzhoy
• Piotr Indyk
• Anastasios Sidiropoulos

A low-distortion embedding between two metric spaces is a mapping which preserves the distances between each pair of points, up to a small factor called distortion. Low-distortion embeddings have recently found numerous applications in computer science.Most of the known embedding results are "absolute",that is, of the form: any metric Y from a given class of metrics C can be embedded into a metric X with low distortion c . This is beneficial if one can guarantee low distortion for all metrics Y in C . However, in any situations, the worst-case distortion is too large to be meaningful. For example, if X is a line metric, then even very simple metrics (an n - point star or an n -point cycle) are embeddable into X only with distortion linear in n . Nevertheless, embeddings into the line (or into low-dimensional spaces) are important for many applications.A solution to this issue is to consider "relative" (or "approximation") embedding problems, where the goal is to design an (a-approxiation) algorithm which, given any metric X from C as an input, finds an embedding of X into Y which has distortion a * c Y ( X ), where c Y ( X )is the best possible distortion of an embedding of X into Y .In this paper we show algorithms and hardness results for relative embedding problems.In particular we give: •an algorith that, given a general metric M , finds an embedding with distortion O (Δ 3⁄4 poly( c line ( M ))), where Δ is the spread of M •an algorithm that,given a weighted tree etric M , finds an embedding with distortion poly( c line ( M )) •a hardness result, showing that computing minimum line distortion is hard to approximate up to a factor polynomial in n ,even for weighted tree metrics with spread Δ= n O (1).

STOC Conference 2005 Conference Paper

Optimal approximations of the frequency moments of data streams

• Piotr Indyk
• David P. Woodruff

We give a 1-pass Õ ( m 1-2⁄ k )-space algorithm for computing the k -th frequency moment of a data stream for any real k > 2. Together with the lower bounds of [1, 2, 4], this resolves the main problem left open by Alon et al in 1996 [1]. Our algorithm also works for streams with deletions and thus gives an Õ ( m 1-2⁄p ) space algorithm for the L p difference problem for any p > 2. This essentially matches the known Ω( m 1-2⁄ p - o (1) ) lower bound of [12, 2]. Finally the update time of our algorithms is Õ (1).

STOC Conference 2004 Conference Paper

Algorithms for dynamic geometric problems over data streams

• Piotr Indyk

SODA Conference 2004 Conference Paper

Approximate Nearest Neighbor under edit distance via product metrics

• Piotr Indyk

SODA Conference 2004 Conference Paper

Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates

• Venkatesan Guruswami
• Piotr Indyk

SODA Conference 2004 Conference Paper

Fast approximate pattern matching with few indels via embeddings

• Mihai Badoiu
• Piotr Indyk

SODA Conference 2003 Conference Paper

Better algorithms for high-dimensional proximity problems via asymmetric embeddings

• Piotr Indyk

SODA Conference 2003 Conference Paper

Embeddings and non-approximability of geometric problems

• Venkatesan Guruswami
• Piotr Indyk

STOC Conference 2003 Conference Paper

Linear time encodable and list decodable codes

• Venkatesan Guruswami
• Piotr Indyk

We present the first construction of error-correcting codes which can be (list) decoded from a noise fraction arbitrarily close to 1 in linear time . Specifically, we present an explicit construction of codes which can be encoded in linear time as well as list decoded in linear time from a fraction (1-ε) of errors for arbitrary ε > 0 . The rate and alphabet size of the construction are constants that depend only on ε . Our construction involves devising a new combinatorial approach to list decoding, in contrast to all previous approaches which relied on the power of decoding algorithms for algebraic codes like Reed-Solomon codes.Our result implies that it is possible to have, and in fact explicitly specifies, a coding scheme for arbitrarily large noise thresholds with only constant redundancy in the encoding and constant amount of work (at both the sending and receiving ends) for each bit of information to be communicated. Such a result was known for certain probabilistic error models, and here we show that this is possible under the stronger adversarial noise model as well.

SODA Conference 2003 Conference Paper

Lower bounds for embedding edit distance into normed spaces

• Alexandr Andoni
• Michel Deza
• Anupam Gupta 0001
• Piotr Indyk
• Sofya Raskhodnikova

FOCS Conference 2003 Conference Paper

Tight Lower Bounds for the Distinct Elements Problem

• Piotr Indyk
• David P. Woodruff

We prove strong lower bounds for the space complexity of (/spl epsi/, /spl delta/)-approximating the number of distinct elements F/sub 0/ in a data stream. Let m be the size of the universe from which the stream elements are drawn. We show that any one-pass streaming algorithm for (/spl epsi/, /spl delta/)-approximating F/sub 0/ must use /spl Omega/(1//spl epsi//sup 2/) space when /spl epsi/ = /spl Omega/(m/sup -1/(9 + k)/), for any k > 0, improving upon the known lower bound of /spl Omega/(1//spl epsi/) for this range of /spl epsi/. This lower bound is tight up to a factor of log log m for small /spl epsi/ and log 1//spl epsi/ for large /spl epsi/. Our lower bound is derived from a reduction from the one-way communication complexity of approximating a Boolean function in Euclidean space. The reduction makes use of a low-distortion embedding from an l/sub 2/ to l/sub 1/ norm.

STOC Conference 2002 Conference Paper

Approximate clustering via core-sets

• Mihai Badoiu
• Sariel Har-Peled
• Piotr Indyk

SODA Conference 2002 Conference Paper

Derandomized dimensionality reduction with applications

• Lars Engebretsen
• Piotr Indyk
• Ryan O'Donnell

SODA Conference 2002 Conference Paper

Explicit constructions of selectors and related combinatorial structures, with applications

• Piotr Indyk

STOC Conference 2002 Conference Paper

Fast, small-space algorithms for approximate histogram maintenance

• Anna C. Gilbert
• Sudipto Guha
• Piotr Indyk
• Yannis Kotidis
• S. Muthukrishnan 0001
• Martin J. Strauss

(MATH) A vector A of length N is defined implicitly, via a stream of updates of the form "add 5 to A 3 ." We give a sketching algorithm, that constructs a small sketch from the stream of updates, and a reconstruction algorithm, that produces a B -bucket piecewise-constant representation (histogram) H for A from the sketch, such that || A—H ||≤(1+ε)|| A—H opt ||, where the error || A—H || is either $\ell_1$ (absolute) or $\ell_2$ (root-mean-square) error. The time to process a single update, time to reconstruct the histogram, and size of the sketch are each bounded by poly( B ,log( N ),log|| A ,1/ε. Our result is obtained in two steps. First we obtain what we call a robust histogram approximation for A , a histogram such that adding a small number of buckets does not help improve the representation quality significantly. From the robust histogram, we cull a histogram of desired accruacy and B buckets in the second step. This technique also provides similar results for Haar wavelet representations, under $\ell_2$ error. Our results have applications in summarizing data distributions fast and succinctly even in distributed settings.

SODA Conference 2002 Conference Paper

Maintaining stream statistics over sliding windows (extended abstract)

• Mayur Datar
• Aristides Gionis
• Piotr Indyk
• Rajeev Motwani 0001

STOC Conference 2002 Conference Paper

Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets

• Venkatesan Guruswami
• Piotr Indyk

We present an explicit construction of linear-time encodable and decodable codes of rate r which can correct a fraction (1 — r ε)/2 of errors over an alphabet of constant size depending only on ε, for every 0 0. The error-correction performance of these codes is optimal as seen by the Singleton bound (these are "near-MDS" codes). Such near-MDS linear-time codes were known for the decoding from erasures [2]; our construction generalizes this to handle errors as well. Concatenating these codes with good, constant-sized binary codes gives a construction of linear-time binary codes which meet the so-called "Zyablov bound". In a nutshell, our results match the performance of the previously known explicit constructions of codes that had polynomial time encoding and decoding, but in addition have linear time encoding and decoding algorithms.We also obtain some results for list decoding targeted at the situation when the fraction of errors is very large, namely (1—ε) for an arbitrarily small constant ε > 0. The previously known constructions of such codes of good rate over constant-sized alphabets either used algebraic-geometric codes and thus suffered from complicated constructions and slow decoding, or as in the recent work of the authors [9], had fast encoding/decoding, but suffered from an alphabet size that was exponential in 1/ε. We present two constructions of such codes with rate close to Ω(ε 2 ) over an alphabet of size quasi-polynomial in 1/ε. One of the constructions, at the expense of a slight worsening of the rate, can achieve an alphabet size which is polynomial in 1/ε. It also yields constructions of codes for list decoding from erasures which achieve new trade-offs. In particular, we construct codes of rate close to the optimal Ω(ε) rate which can be efficiently list decoded from a fraction (1—ε) of erasures.

STOC Conference 2002 Conference Paper

Near-optimal sparse fourier representations via sampling

• Anna C. Gilbert
• Sudipto Guha
• Piotr Indyk
• S. Muthukrishnan 0001
• Martin J. Strauss

(MATH) We give an algorithm for finding a Fourier representation R of B terms for a given discrete signal signal A of length N , such that $\|\signal-\repn\|_2^2$ is within the factor (1 +ε) of best possible $\|\signal-\repn_\opt\|_2^2$. Our algorithm can access A by reading its values on a sample set T ⊆[0, N ), chosen randomly from a (non-product) distribution of our choice, independent of A . That is, we sample non-adaptively. The total time cost of the algorithm is polynomial in B log( N )log( M )ε (where M is the ratio of largest to smallest numerical quantity encountered), which implies a similar bound for the number of samples.

FOCS Conference 2001 Conference Paper

Algorithmic Applications of Low-Distortion Geometric Embeddings

• Piotr Indyk

The author surveys algorithmic results obtained using low-distortion embeddings of metric spaces into (mostly) normed spaces. He shows that low-distortion embeddings provide a powerful and versatile toolkit for solving algorithmic problems. Their fundamental nature makes them applicable in a variety of diverse settings, while their relation to rich mathematical fields (e. g. , functional analysis) ensures availability of tools for their construction.

FOCS Conference 2001 Conference Paper

Expander-Based Constructions of Efficiently Decodable Codes

• Venkatesan Guruswami
• Piotr Indyk

We present several novel constructions of codes which share the common thread of using expander (or expander-like) graphs as a component. The expanders enable the design of efficient decoding algorithms that correct a large number of errors through various forms of "voting" procedures. We consider both the notions of unique and list decoding, and in all cases obtain asymptotically good codes which are decodable up to a "maximum" possible radius and either: (a) achieve a similar rate as the previously best known codes but come with significantly faster algorithms, or (b) achieve a rate better than any prior construction with similar error-correction properties. Among our main results are: i) codes of rate /spl Omega/(/spl epsi//sup 2/) over constant-sized alphabet that can be list decoded in quadratic time from (1-/spl epsi/) errors; ii) codes of rate /spl Omega/(/spl epsi/) over constant-sized alphabet that can be uniquely decoded from (1/2-/spl epsi/) errors in near-linear time (this matches AG-codes with much faster algorithms); iii) linear-time encodable and decodable binary codes of positive rate (in fact, rate /spl Omega/(/spl epsi//sup 2/)) that can correct up to (1/4-/spl epsi/) fraction errors.

TCS Journal 2001 Journal Article

On page migration and other relaxed task systems

• Yair Bartal
• Moses Charikar
• Piotr Indyk

This paper is concerned with the page migration (or file migration) problem (Black and Sleator, Technical Report CMU-CS-89-201, Department of Computer Science, Carnegie-Mellon University, 1989) as part of a large class of on-line problems. The page migration problem deals with the management of pages residing in a network of processors. In the classical problem there is only one copy of each page which is accessed by different processors over time. The page is allowed to be migrated between processors. However a migration incurs higher communication cost than an access (proportionally to the page size). The problem is that of deciding when and where to migrate the page in order to lower access costs. A more general setting is the k-page migration problem where we wish to maintain k copies of the page. The page migration problems are concerned with a dilemma common to many on-line problems: determining when it is beneficial to make configuration changes. We deal with the relaxed task systems model which captures a large class of problems of this type, that can be described as the generalization of some original task system problem (Borodin et al. , J. ACM 39(4) (1992) 745–763). Given a c-competitive algorithm for a task system we show how to obtain a deterministic O(c2) and randomized O(c) competitive algorithms for the corresponding relaxed task system. The result implies deterministic algorithms for k-page migration by using k-server (Manasse et al. , J. Algorithms 11(2) (1990) 208–230) algorithms, and for network leasing by using generalized Steiner tree algorithms (Awerbuch et al. , Proc 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, January 1996, pp. 68–74), as well as providing solutions for natural generalizations of other problems (e. g. storage rearrangement (Fiat et al. , Proc. 36th Ann. IEEE Symp. on Foundations of Computer Science, October 1995, pp. 392–403). We further study some special cases of the k-page migration problem and get optimal deterministic algorithms. For the classical page migration problem we present a deterministic algorithm that achieves a competitive ratio of ∼4. 086, improving upon the previously best competitive ratio of 7 (Awerbuch et al. , Proc. 25th ACM Symp. on Theory of Computing, May 1993, pp. 164–173). (The current lower bound on the problem is ∼3. 148 (Chrobak et al. , J. Algorithms 24(1) (1997) 124–157).)

SODA Conference 2001 Conference Paper

Pattern matching for sets of segments

• Alon Efrat
• Piotr Indyk
• Suresh Venkatasubramanian

SODA Conference 2001 Conference Paper

Reductions among high dimensional proximity problems

• Ashish Goel
• Piotr Indyk
• Kasturi R. Varadarajan

SODA Conference 2000 Conference Paper

Approximate congruence in nearly linear time

• Piotr Indyk
• Suresh Venkatasubramanian

SODA Conference 2000 Conference Paper

Dimensionality reduction techniques for proximity problems

• Piotr Indyk

FOCS Conference 2000 Conference Paper

Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation

• Piotr Indyk

In this paper we show several results obtained by combining the use of stable distributions with pseudorandom generators for bounded space. In particular: we show how to maintain (using only O(log n//spl epsiv//sup 2/) words of storage) a sketch C(p) of a point p/spl isin/l/sub 1//sup n/ under dynamic updates of its coordinates, such that given sketches C(p) and C(q) one can estimate |p-q|/sub 1/ up to a factor of (1+/spl epsiv/) with large probability. We obtain another sketch function C' which maps l/sub 1//sup n/ into a normed space l/sub 1//sup m/ (as opposed to C), such that m=m(n) is much smaller than n; to our knowledge this is the first dimensionality reduction lemma for l/sub 1/ norm we give an explicit embedding of l/sub 2//sup n/ into l/sub l//sup nO(log n)/ with distortion (1+1/n/sup /spl theta/(1)/) and a non-constructive embedding of l/sub 2//sup n/ into l/sub 1//sup O(n)/ with distortion (1+/spl epsiv/) such that the embedding can be represented using only O(n log/sup 2/ n) bits (as opposed to at least n/sup 2/ used by earlier methods).

SODA Conference 1999 Conference Paper

A Small Approximately min-wise Independent Family of Hash Functions

• Piotr Indyk

FOCS Conference 1999 Conference Paper

A Sublinear Time Approximation Scheme for Clustering in Metric Spaces

• Piotr Indyk

The metric 2-clustering problem is defined as follows: given a metric (or weighted graph) (X, d), partition X into two sets S(1) and S(2) in order to minimize the value of /spl Sigma//sub i//spl Sigma//sub {u, v}/spl sub/S(i)/d(u, v). In this paper, we show an approximation scheme for this problem.

FOCS Conference 1999 Conference Paper

Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings

• Martín Farach-Colton
• Piotr Indyk

Hausdorff metrics are used in geometric settings for measuring the distance between sets of points. They have been used extensively in areas such as computer vision, pattern recognition and computational chemistry. While computing the distance between a single pair of sets under the Hausdorff metric has been well studied, no results are known for the nearest-neighbor problem under Hausdorff metrics. Indeed, no results were known for the nearest-neighbor problem for any metric without a norm structure, of which the Hausdorff is one. We present the first nearest-neighbor algorithm for the Hausdorff metric. We achieve our result by embedding Hausdorff metrics into l/sub /spl infin// and by using known nearest-neighbor algorithms for this target metric. We give upper and lower bounds on the number of dimensions needed for such an l/sub /spl infin// embedding. Our bounds require the introduction of new techniques based on superimposed codes and non-uniform sampling.

FOCS Conference 1999 Conference Paper

Efficient Regular Data Structures and Algorithms for Location and Proximity Problems

• Arnon Amir
• Alon Efrat
• Piotr Indyk
• Hanan Samet

Investigates data structures obtained by a recursive partitioning of the input domain into regions of equal size. One of the most well-known examples of such a structure is the quadtree, which is used in this paper as a basis for more complex data structures; we also provide multidimensional versions of the stratified tree of P. van Emde Boas (1997). We show that, under the assumption that the input points have limited precision (i. e. are drawn from an integer grid of size u), these data structures yield efficient solutions to many important problems. In particular, they allow us to achieve O(log log u) time per operation for finding the dynamic approximate nearest neighbor (under insertions and deletions) and the exact online closest pair (under insertions only) in any constant dimension. They allow O(log log u) point location in a given planar shape or in its expansion (dilation by a ball of a given radius). Finally, we provide a linear-time (optimal) algorithm for computing the expansion of a shape represented by a quadtree. This result shows that the spatial order imposed by this regular data structure is sufficient to optimize the dilation by a ball operation.

SODA Conference 1999 Conference Paper

Geometric Matching Under Noise: Combinatorial Bounds and Algorithms

• Piotr Indyk
• Rajeev Motwani 0001
• Suresh Venkatasubramanian

STOC Conference 1999 Conference Paper

Inerpolation of Symmetric Functions and a New Type of Combinatorial Design

• Piotr Indyk

FOCS Conference 1999 Conference Paper

Stochastic Load Balancing and Related Problems

• Ashish Goel
• Piotr Indyk

We study the problems of makespan minimization (load balancing), knapsack, and bin packing when the jobs have stochastic processing requirements or sizes. If the jobs are all Poisson, we present a two approximation for the first problem using Graham's rule, and observe that polynomial time approximation schemes can be obtained for the last two problems. If the jobs are all exponential, we present polynomial time approximation schemes for all three problems. We also obtain quasi-polynomial time approximation schemes for the last two problems if the jobs are Bernoulli variables.

STOC Conference 1999 Conference Paper

Sublinear Time Algorithms for Metric Space Problems

• Piotr Indyk

SODA Conference 1999 Conference Paper

Tree Pattern Matching and Subset Matching in Deterministic O ( n log 3 n )-time

• Richard Cole 0001
• Ramesh Hariharan
• Piotr Indyk

STOC Conference 1998 Conference Paper

Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality

• Piotr Indyk
• Rajeev Motwani 0001

FOCS Conference 1998 Conference Paper

Faster Algorithms for String Matching Problems: Matching the Convolution Bound

• Piotr Indyk

In this paper we give a randomized O(nlogn)-time algorithm for the string matching with don't cares problem. This improves the Fischer-Paterson bound from 1974 and answers the open problem posed (among others) by Weiner and Galil. Using the same technique, we give an O(nlogn)-time algorithm for other problems, including subset matching, tree pattern matching, (general) approximate threshold matching and point set matching. As this bound essentially matches the complexity of computing of the fast Fourier transform which is the only known technique for solving problems of this type, it is likely that the algorithms are in fact optimal. Additionally the technique used for the threshold matching problem can be applied to the on-line version of this problem, in which we are allowed to preprocess the text and require to process the pattern in time sublinear in the text length. This result involves an interesting variant of the Karp-Rabin fingerprint method in which hash functions are locality-sensitive, i. e. the probability of collision of two words depends on the distance between them.

FOCS Conference 1998 Conference Paper

On Approximate Nearest Neighbors in Non-Euclidean Spaces

• Piotr Indyk

The nearest neighbor search (NNS) problem is the following: Given a set of n points P={p/sub 1/, .. ., p/sub n/} in some metric space X, preprocess P so as to efficiently answer queries which require finding a point in P closest to a query point q/spl isin/X. The approximate nearest neighbor search (c-NNS) is a relaxation of NNS which allows to return any point within c times the distance to the nearest neighbor (called c-nearest neighbor). This problem is of major and growing importance to a variety of applications. In this paper we give an algorithm for (4log/sub 1+/spl rho//log4d+3)-NNS algorithm in l/sub /spl infin///sup d/ with O(dn/sup 1+/spl rho//logn) storage and O(dlogn) query time. In particular this yields the first algorithm for O(1)-NNS for l/sub /spl infin// with subexponential storage. The preprocessing time is linear in the size of the data structure. The algorithm can be also used (after simple modifications) to output the exact nearest neighbor in time bounded bounded O(dlogn) plus the number of (4log/sub 1+/spl rho//log4d+3)-nearest neighbors of the query point. Building on this result, we also obtain an approximation algorithm for a general class of product metrics. Finally: we show that for any c<3 the c-NNS problem in l/sub /spl infin// is provably hard for a version of the indexing model introduced by Hellerstein et al. (1997).

FOCS Conference 1997 Conference Paper

Deterministic Superimposed Coding with Applications to Pattern Matching

• Piotr Indyk

A superimposed code is a set of binary vectors having the property that no vector is contained in a boolean sum (i. e. bitwise OR) of a small number of others. Such codes are used in information retrieval for constructing so-called signature files; they also have applications in other areas. In this paper we introduce a new notion of data-dependent superimposed codes and give a deterministic algorithm for constructing short such codes. We then show that these codes can be used to achieve an almost optimal de-randomization of several pattern matching algorithms, including the almost-linear algorithm for tree pattern matching developed recently. Thus, we give the first almost-linear time deterministic algorithms for these problems.

STOC Conference 1997 Conference Paper

Locality-Preserving Hashing in Multidimensional Spaces

• Piotr Indyk
• Rajeev Motwani 0001
• Prabhakar Raghavan
• Santosh S. Vempala

SODA Conference 1997 Conference Paper

On Page Migration and Other Relaxed Task Systems

• Yair Bartal
• Moses Charikar
• Piotr Indyk