Stable distributions, pseudorandom generators, embeddings and data stream computation

By Piotr Indyk. Proceedings 41st Annual Symposium on Foundations of Computer Science, 2000

752 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/c982cb13d2a870ca09a2a1f0bf3c602cc528724e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Maintaining Stream Statistics over Sliding Windows (2002, methodology): “We now extend the EH technique and combine it with the sketching technique from Indyk [ 13 ] to compute the Lp norms of vectors in the sliding window model.”
Locality-sensitive hashing scheme based on p-stable distributions (2004, methodology): “In computer science, stable distributions were used for sketching of high dimensional vectors by Indyk ([18]) and since have found use in various applications.”
Clustering Data Streams: Theory and Practice (2003, background): “Problems that can be solved in small space when the data is a stream include: frequency estimation [36], [12], norm estimation [4], [22], [44], order statistics [64], [57], [56], [30], [28], synopsis structures [26], time indexed data [25], [32], [17], [8], signal reconstructions [24], [18], [1],…”
Two Party Distribution Testing: Communication and Security (2018, methodology): “Intuitively, considering the extreme of t n , we can obtain near-constant communication: with so many samples, we can learn the distribution, and then use sketching tools, such as the (cid:96) 1 sketching algorithm of [AMS99, Ind06].”
Near Duplicate Image Detection: min-Hash and tf-idf Weighting (2008, methodology): “[8] introduced a method for efficient extension of Locally Sensitive Hashing scheme [7] for Mahalanobis distance.”
Fast Random Walk Graph Kernel (2012, methodology): “For static graphs, the most popular choices include SVD/PCA [12, 19] and random projection [17].”
Very sparse random projections (2006, background): “It is one of the few stable distributions that have closed-form density [19].”
Sketching as a Tool for Numerical Linear Algebra (2014, background): “ation, and have inﬁnite variance, some control over them can be obtained by clipping them. The ﬁrst use of such a truncation technique in algorithmic applications that we are aware of is due to Indyk [63]. Lemma 33 Consider the event Ethat a Cauchy random variable X satisﬁes |X|≤M, for some paramete”
VisualRank: Applying PageRank to Large-Scale Image Search (2008, neutral): “l2 norms, based on p-stable distributions [40].”
Graph sketches: sparsification, spanners, and subgraphs (2012, methodology): “[24] A. Gilbert and P. Indyk.”
Improved Approximation Algorithms for Large Matrices via Random Projections (2006, neutral): “[52, 39] contains e ssentially the same result.”
Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries (2001, methodology): “In the area of theoretical algorithms, streaming models have been studied in [21, 3, 12, 13, 22, 20], where methods have been developed for comparing data streams under various distances, or clustering them.”
Fast, small-space algorithms for approximate histogram maintenance (2002, methodology): “As in [10], choose a random vector V according to a symmetric p-stable distribution.”
The Fast Johnson--Lindenstrauss Transform and Approximate Nearest Neighbors (2009, methodology): “Indyk and Motwani [29] and Kushilevitz, Ostrovsky, and Rabani [33] used low-dimensional embeddings to speed up approximate nearest neighbor searching.”
Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND (2009, background): “A major influence on the foundations of massive data sets as well as a pioneer of novel techniques has been the frequency moments problem and its variants [FM85, AMS99, Ind06 , BJK+02, CCFC04, IW05].”