The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
Open accessAbstract
We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain improved algorithms for the following problems: approximate nearest neighbor search, well-separated pair decomposition, spanner construction, compact representation scheme, doubling measure, and computation of the (approximate) Lipschitz constant of a function. In all cases, the running (preprocessing) time is near linear and the space being used is linear.
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
Adhi Harmoko, S., M.Komp, Jacquard, J. M., Zuse, K., & Eniac (2005) · Cited by 18,035
The Art of Computer Programming
Whitesides, G. E. (1970) · Nuclear Science and Engineering · doi:10.13182/nse70-a19705 · Cited by 6,008
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
The Art of Computer Programming. Volume 2: Seminumerical Algorithms.
Taussky, O., & Knuth, D. E. (1970) · The American Mathematical Monthly · doi:10.2307/2317055 · Cited by 3,822
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1998) · Journal of the ACM · doi:10.1145/293347.293348 · Cited by 2,300
Clustering to minimize the maximum intercluster distance
Gonzalez, T. F. (1985) · Theoretical Computer Science · doi:10.1016/0304-3975(85)90224-5 · Cited by 1,717
Bender, M. A., & Farach-Colton, M. (2000) · Lecture notes in computer science · doi:10.1007/10719839_9 · Cited by 815
Cover trees for nearest neighbor
Beygelzimer, A., Kakade, S., & Langford, J. (2006) · Proceedings of the 23rd international conference on Machine learning - ICML '06 · doi:10.1145/1143844.1143857 · Cited by 813
Applications of random sampling in computational geometry, II
Clarkson, K. L., & Shor, P. W. (1989) · Discrete & Computational Geometry · doi:10.1007/bf02187740 · Cited by 665
Matoušek, J. (2008) · Springer eBooks · doi:10.1007/978-3-540-76649-0 · Cited by 574
Callahan, P. B., & Kosaraju, S. R. (1995) · Journal of the ACM · doi:10.1145/200836.200853 · Cited by 543
Optimal algorithms for approximate clustering
Feder, T., & Greene, D. (1988) · doi:10.1145/62212.62255 · Cited by 437
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
Finding nearest neighbors in growth-restricted metrics
Karger, D. R., & Ruhl, M. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.510013 · Cited by 334
Navigating nets: simple algorithms for proximity search
Krauthgamer, R., & Lee, J. R. (2015) · Cited by 308
AnO(n logn) algorithm for the all-nearest-neighbors Problem
Vaidya, P. M. (1989) · Discrete & Computational Geometry · doi:10.1007/bf02187718 · Cited by 232
Gavoille, C., Peleg, D., Pérennes, S., & Raz, R. (2004) · Journal of Algorithms · doi:10.1016/j.jalgor.2004.05.002 · Cited by 224
Bypassing the embedding: algorithms for low dimensional metrics
Talwar, K. (2004) · Proceedings of the thirty-sixth annual ACM symposium on Theory of computing · doi:10.1145/1007352.1007399 · Cited by 207
Sublinear time algorithms for metric space problems
Indyk, P. (1999) · Proceedings of the thirty-first annual ACM symposium on Theory of Computing · doi:10.1145/301250.301366 · Cited by 192
The Level Ancestor Problem simplified
Bender, M. A., & Farach-Colton, M. (2004) · Theoretical Computer Science · doi:10.1016/j.tcs.2003.05.002 · Cited by 187
Nearest Neighbor Queries in Metric Spaces
Clarkson, K. L. (1999) · Discrete & Computational Geometry · doi:10.1007/pl00009449 · Cited by 169
A 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
Self-citationOn metric Ramsey-type phenomena
Bartal, Y., Linial, N., Mendel, M., & Naor, A. (2005) · Annals of Mathematics · doi:10.4007/annals.2005.162.643 · Cited by 118
Self-citationCoresets for $k$-Means and $k$-Median Clustering and their ApplicationsPreprint
Har-Peled, S., & Mazumdar, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.12826 · Cited by 100
Self-citationHar-Peled, S. (2004) · Discrete & Computational Geometry · doi:10.1007/s00454-004-2822-7 · Cited by 75
Self-citationThe black-box complexity of nearest-neighbor search
Krauthgamer, R., & Lee, J. R. (2005) · Theoretical Computer Science · doi:10.1016/j.tcs.2005.09.017 · Cited by 55
Distributed approaches to triangulation and embedding
Slivkins, A. (2005) · doi:10.5555/1070432.1070522 · Cited by 32
Cited by
Cover trees for nearest neighbor
Beygelzimer, A., Kakade, S., & Langford, J. (2006) · Proceedings of the 23rd international conference on Machine learning - ICML '06 · doi:10.1145/1143844.1143857 · Cited by 813
Metadata
- Authors
- Har-Peled, S., & Mendel, M.
- Venue
- SIAM Journal on Computing
- Published
- 2006-01
- Volume
- 35
- Issue
- 5
- Pages
- 1148-1184
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2045134120
- Cited by
- 263
- References
- 27
- FWCI
- 31.25
- Type
- journal article
- Language
- en
- Open access
- green
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.