The DOI matches its Crossref record; 35 of the 35 references it cites were found in a registry or an index.
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Abstract
In this article, we show several results obtained by combining the use of stable distributions with pseudorandom generators for bounded space . In particular:---We show that, for any p ∈ (0, 2], one can maintain (using only O (log n /ϵ 2 ) words of storage) a sketch C(q) of a point q ∈ l n p under dynamic updates of its coordinates. The sketch has the property that, given C(q) and C(s) , one can estimate ‖ q − s ‖ p up to a factor of (1 + ϵ) with large probability. This solves the main open problem of Feigenbaum et al. [1999].---We show that the aforementioned sketching approach directly translates into an approximate algorithm that, for a fixed linear mapping A , and given x ∈ ℜ n and y ∈ ℜ m , estimates ‖ Ax − y ‖ p in O ( n + m ) time, for any p ∈ (0, 2]. This generalizes an earlier algorithm of Wasserman and Blum [1997] which worked for the case p = 2.---We obtain another sketch function C ′ which probabilistically embeds l n 1 into a normed space l m 1 . The embedding guarantees that, if we set m = log(1/δ) O (1/ϵ) , then for any pair of points q , s ∈ l n 1 , the distance between q and s does not increase by more than (1 + ϵ) with constant probability, and it does not decrease by more than (1 − ϵ) with probability 1 − δ. This is the only known dimensionality reduction theorem for the l 1 norm. In fact, stronger theorems of this type (i.e., that guarantee very low probability of expansion as well as of contraction) cannot exist [Brinkman and Charikar 2003].---We give an explicit embedding of l n 2 into l n O (log n ) 1 with distortion (1 + 1/ n Θ(1) ).
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188
Self-citationLocality-sensitive hashing scheme based on p-stable distributions
Datar, M., Immorlica, N., Indyk, P., & Mirrokni, V. S. (2004) · Proceedings of the twentieth annual symposium on Computational geometry · doi:10.1145/997817.997857 · Cited by 2,936
Self-citationExtensions of Lipschitz mappings into a Hilbert space
Johnson, W. B., & Lindenstrauss, J. (1984) · Contemporary Mathematics · doi:10.1090/conm/026/737400 · Cited by 2,523
One-Dimensional Stable Distributions
Zolotarev, V. (1986) · Translations of Mathematical Monographs · doi:10.1090/mmono/065 · Cited by 1,843
Data Streams: Algorithms and Applications
Muthukrishnan, S. (2005) · now publishers, Inc. eBooks · doi:10.1561/9781933019604 · Cited by 1,527
Syntactic clustering of the Web
Broder, A. Z., Glassman, S. C., Manasse, M. S., & Zweig, G. (1997) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(97)00031-7 · Cited by 1,343
Maintaining Stream Statistics over Sliding Windows
Datar, M., Gionis, A., Indyk, P., & Motwani, R. (2002) · SIAM Journal on Computing · doi:10.1137/s0097539701398363 · Cited by 835
Self-citationThe space complexity of approximating the frequency moments
Alon, N., Matias, Y., & Szegedy, M. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237823 · Cited by 822
Proceedings of the 26th International Conference on Data Engineering, ICDE 2010
Li, F., Moro, M. M., Ghandeharizadeh, S., Haritsa, J. R., Weikum, G., Carey, M. J., Casati, F., Chang, E. Y., Manolescu, I., Mehrotra, S., et al. (2010) · Max Planck Institute for Plasma Physics · Cited by 452
Henzinger, M., Raghavan, P., & Rajagopalan, S. (1999) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/050/05 · Cited by 418
The dimension of almost spherical sections of convex bodies
Figiel, T., Lindenstrauss, J., & Milman, V. D. (1977) · Acta Mathematica · doi:10.1007/bf02392234 · Cited by 401
Finding interesting associations without support pruning
Cohen, E., Datar, M., Fujiwara, S., Gionis, A., Indyk, P., Motwani, R., Ullman, J. D., & Yang, C. (2001) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.908981 · Cited by 341
Self-citationAlgorithmic applications of low-distortion geometric embeddings
Indyk, P. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959878 · Cited by 253
Self-citationMaintaining stream statistics over sliding windows: (extended abstract)
Datar, M., Gionis, A., Indyk, P., & Motwani, R. (2002) · doi:10.5555/545381.545466 · Cited by 253
Self-citationFast, small-space algorithms for approximate histogram maintenance
Gilbert, A. C., Guha, S., Indyk, P., Kotidis, Y., Muthukrishnan, S., & Strauss, M. J. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.509966 · Cited by 242
Self-citationFreivalds, R. (1979) · Lecture notes in computer science · doi:10.1007/3-540-09526-8_5 · Cited by 232
Identifying Representative Trends in Massive Time Series Data Sets Using Sketches
Indyk, P., Koudas, N., & Muthukrishnan, S. (2000) · Very Large Data Bases · Cited by 208
Self-citationDynamic multidimensional histograms
Thaper, N., Guha, S., Indyk, P., & Koudas, N. (2002) · Proceedings of the 2002 ACM SIGMOD international conference on Management of data · doi:10.1145/564691.564741 · Cited by 206
Self-citationSoftware reliability via run-time result-checking
Wasserman, H., & Blum, M. (1997) · Journal of the ACM · doi:10.1145/268999.269003 · Cited by 192
Comparing Data Streams Using Hamming Norms (How to Zero In)
Cormode, G., Datar, M., Indyk, P., & Muthukrishnan, S. (2002) · Elsevier eBooks · doi:10.1016/b978-155860869-6/50037-8 · Cited by 190
Self-citationThe geometry of graphs and some of its algorithmic applications
Linial, N., London, E., & Rabinovich, Y. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365733 · Cited by 190
An Approximate L p-Difference Algorithm for Massive Data Streams: Extended Abstract
Fong, J. H., & Strauss, M. J. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-46541-3_16 · Cited by 163
On the impossibility of dimension reduction in l 1
Brinkman, B., & Charikar, M. (2005) · Journal of the ACM · doi:10.1145/1089023.1089026 · Cited by 132
Low-Distortion Embeddings of Finite Metric Spaces
Indyk, P., & Matoušek, J. (2004) · doi:10.1201/9781315119601-8 · Cited by 129
Self-citationSecure Multiparty Computation of Approximations
Feigenbaum, J., Ishai, Y., Malkin, T., Nissim, K., Strauss, M. J., & Wright, R. N. (2001) · Lecture notes in computer science · doi:10.1007/3-540-48224-5_75 · Cited by 116
Algorithmic derandomization via complexity theory
Sivakumar, D. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.509996 · Cited by 77
Reductions Among High Dimensional Proximity Problems
Goel, A., Indyk, P., & Varadarajan, K. (2000) · Cited by 69
Self-citationDimensionality reduction techniques for proximity problems
Indyk, P. (2000) · doi:10.5555/338219.338582 · Cited by 59
Self-citationEmbedding l ${}_{p}^{m}$ into l ${}_{1}^{n}$
Johnson, W. B., & Schechtman, G. (1982) · Acta Mathematica · doi:10.1007/bf02392350 · Cited by 57
Derandomized Dimensionality Reduction with Applications
Engebretsen, L., Indyk, P., & O’Donnell, R. (2001) · Cited by 53
Self-citationA bound on the deviation probability for sums of non-negative random variables.
Maurer, A. (2003) · Cited by 47
Estimating Dominance Norms of Multiple Data Streams
Cormode, G., & Muthukrishnan, S. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-39658-1_16 · Cited by 44
Checking approximate computations over the reals
Ar, S., Blum, M., Codenotti, B., & Gemmell, P. S. (1993) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/167088.167288 · Cited by 40
Fast mining of massive tabular data via approximate distance computations
Cormode, G., Indyk, P., Koudas, N., & Muthukrishnan, S. (2003) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2002.994778 · Cited by 36
Self-citation
Cited by
Models and issues in data stream systems
Babcock, B., Babu, S., Datar, M., Motwani, R., & Widom, J. (2002) · Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/543613.543615 · Cited by 2,495
Similarity estimation techniques from rounding algorithms
Charikar, M. S. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.509965 · Cited by 2,220
Finding frequent items in data streams
Charikar, M., Chen, K., & Farach-Colton, M. (2004) · Theoretical Computer Science · doi:10.1016/s0304-3975(03)00400-6 · Cited by 1,278
Computational Advertising: Techniques for Targeting Relevant Ads
Woodruff, D. P. (2014) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000060 · Cited by 866
Improved Approximation Algorithms for Large Matrices via Random Projections
Sarlos, T. (2006) · 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) · doi:10.1109/focs.2006.37 · Cited by 646
Metadata
- Authors
- Indyk, P.
- Venue
- Journal of the ACM
- Published
- 2006-05
- Volume
- 53
- Issue
- 3
- Pages
- 307-323
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2045533739
- Cited by
- 402
- References
- 35
- FWCI
- 28.02
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.