The DOI matches its Crossref record; 44 of the 44 references it cites were found in a registry or an index.
Algorithmic applications of low-distortion geometric embeddings
Abstract
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.
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
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-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
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
Leighton, T., & Rao, S. (1999) · Journal of the ACM · doi:10.1145/331524.331526 · Cited by 820
Database-friendly random projections
Achlioptas, D. (2001) · Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/375551.375608 · Cited by 699
On an extremal problem in graph theory
Erdös, P. (1964) · Colloquium Mathematicum · doi:10.4064/cm-13-2-251-254 · Cited by 646
Probabilistic approximation of metric spaces and its algorithmic applications
Bartal, Y. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548477 · Cited by 635
Ritter, H., & Kohonen, T. (1989) · Biological Cybernetics · doi:10.1007/bf00203171 · Cited by 621
Learning mixtures of Gaussians
Dasgupta, S. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814639 · Cited by 588
On lipschitz embedding of finite metric spaces in Hilbert space
Bourgain, J. (1985) · Israel Journal of Mathematics · doi:10.1007/bf02776078 · Cited by 560
Wavelet-based histograms for selectivity estimation
Matias, Y., Vitter, J. S., & Wang, M. (1998) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/276304.276344 · Cited by 425
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
Dimensionality reduction by random mapping: fast similarity computation for clustering
Kaski, S. (2002) · 1998 IEEE International Joint Conference on Neural Networks Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98CH36227) · doi:10.1109/ijcnn.1998.682302 · Cited by 388
Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries
Gilbert, A. C., Kotidis, Y., Muthukrishnan, S., & Strauss, M. J. (2001) · Cited by 376
An algorithmic theory of learning: Robust concepts and random projection
Arriaga, R. I., & Vempala, S. (2006) · Machine Learning · doi:10.1007/s10994-006-6265-7 · Cited by 316
Experiments with Random Projection
Dasgupta, S. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.3849 · Cited by 306
A Graph-Theoretic Game and Its Application to the k -Server Problem
Alon, N., Karp, R. M., Peleg, D., & West, D. B. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539792224474 · Cited by 303
The Johnson-Lindenstrauss lemma and the sphericity of some graphs
Frankl, P., & Maehara, H. (1988) · Journal of Combinatorial Theory, Series B · doi:10.1016/0095-8956(88)90043-3 · Cited by 299
Efficient search for approximate nearest neighbor in high dimensional spaces
Kushilevitz, E., Ostrovsky, R., & Rabani, Y. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276877 · Cited by 259
On the placement of Internet instrumentation
Jamin, S., Jin, C., Jin, Y., Raz, D., Shavitt, Y., & Zhang, L. (2002) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2000.832199 · Cited by 244
Stable distributions, pseudorandom generators, embeddings and data stream computation
Indyk, P. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892082 · Cited by 238
Self-citationTracking join and self-join sizes in limited storage
Alon, N., Gibbons, P. B., Matias, Y., & Szegedy, M. (1999) · doi:10.1145/303976.303978 · Cited by 211
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-citationSmall distortion and volume preserving embeddings for planar and Euclidean metrics
Rao, S. B. (1999) · doi:10.1145/304893.304983 · Cited by 190
The 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
Metric Entropy of Some Classes of Sets with Differentiable Boundaries
Dudley, R. M. (2010) · Springer eBooks · doi:10.1007/978-1-4419-5821-1_26 · Cited by 189
Placement Algorithms for Hierarchical Cooperative Caching
Korupolu, M. R., Plaxton, C. G., & Rajaraman, R. (2001) · Journal of Algorithms · doi:10.1006/jagm.2000.1129 · Cited by 175
Approximating a finite metric by a small number of tree metrics
Charikar, M., Chekuri, C., Goel, A., Guha, S., & Plotkin, S. (2002) · Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280) · doi:10.1109/sfcs.1998.743488 · Cited by 172
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
Scalable Techniques for Clustering the Web.
Haveliwala, T. H., Gionis, A., & Indyk, P. (2000) · Cited by 148
Self-citationA replacement for Voronoi diagrams of near linear size
Har-Peled, S. (2001) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959884 · Cited by 147
A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
Wu, B. Y., Lancia, G., Bafna, V., Chao, K., Ravi, R., & Tang, C. Y. (2000) · SIAM Journal on Computing · doi:10.1137/s009753979732253x · Cited by 132
Kleinberg, J. M., & Eva Tardos, D. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sffcs.1999.814572 · Cited by 129
Communication complexity of document exchange
Cormode, G., Paterson, M. S., Şahinalp, S. C., & Vishkin, U. (2026) · Symposium on Discrete Algorithms · doi:10.82444/warw.33642076 · Cited by 128
On the distortion required for embedding finite metric spaces into normed spaces
Matoušek, J. (1996) · Israel Journal of Mathematics · doi:10.1007/bf02761110 · Cited by 104
An algorithmic theory of learning: robust concepts and random projection
Arriaga, R. I., & Vempala, S. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sffcs.1999.814637 · Cited by 96
A polylog( n )-competitive algorithm for metrical task systems
Bartal, Y., Blum, A. L., Burch, C., & Tomkins, A. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258667 · Cited by 90
Approximate nearest neighbors and sequence comparison with block operations
Muthukrishnan, S., & Şahinalp, S. C. (2000) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/335305.335353 · Cited by 85
Linial, M., Linial, N., Tishby, N., & Yona, G. (1997) · Journal of Molecular Biology · doi:10.1006/jmbi.1997.0948 · Cited by 60
Embedding l ${}_{p}^{m}$ into l ${}_{1}^{n}$
Johnson, W. B., & Schechtman, G. (1982) · Acta Mathematica · doi:10.1007/bf02392350 · Cited by 57
When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree
Trevisan, L. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539799352735 · Cited by 47
Better algorithms for high-dimensional proximity problems via asymmetric embeddings
Indyk, P. (2003) · Cited by 47
Self-citationPolynomial time approximation schemes for geometric k-clustering
Ostrovsky, R., & Rabani, Y. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892123 · Cited by 46
Permutation Editing and Matching via Embeddings
Cormode, G., Muthukrishnan, S., & Şahinalp, S. C. (2001) · Lecture notes in computer science · doi:10.1007/3-540-48224-5_40 · Cited by 30
Better algorithms for unfair metrical task systems and applications
Fiat, A., & Mendel, M. (2000) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/335305.335408 · Cited by 23
Cited by
Kanerva, P. (2009) · Cognitive Computation · doi:10.1007/s12559-009-9009-8 · Cited by 970
Bounded geometries, fractals, and low-distortion embeddings
Gupta, A., Krauthgamer, R., & Lee, J. R. (2004) · 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. · doi:10.1109/sfcs.2003.1238226 · Cited by 405
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Indyk, P. (2006) · Journal of the ACM · doi:10.1145/1147954.1147955 · Cited by 402
Self-citationGeometric Approximation Algorithms
Har-Peled, S. (2011) · Mathematical Surveys and Monographs · doi:10.1090/surv/173 · Cited by 315
State representation learning for control: An overview
Lesort, T., Díaz-Rodríguez, N., Goudou, J.-F., & Filliat, D. (2018) · Neural Networks · doi:10.1016/j.neunet.2018.07.006 · Cited by 301
Metadata
- Authors
- Indyk, P.
- Venue
- Proceedings 42nd IEEE Symposium on Foundations of Computer Science
- Publisher
- IEEE
- Published
- 2001
- Pages
- 10-33
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W1530239281
- Cited by
- 253
- References
- 44
- FWCI
- 8.64
- Type
- conference paper
- 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.