The DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.
Multidimensional binary search trees used for associative searching
Open accessAbstract
This paper develops the multidimensional binary search tree (or k -d tree, where k is the dimensionality of the search space) as a data structure for storage of information to be retrieved by associative searches. The k -d tree is defined and examples are given. It is shown to be quite efficient in its storage requirements. A significant advantage of this structure is that a single data structure can handle many types of queries very efficiently. Various utility algorithms are developed; their proven average running times in an n record file are: insertion, O (log n ); deletion of the root, O ( n ( k -1)/ k ); deletion of a random node, O (log n ); and optimization (guarantees logarithmic performance of searches), O ( n log n ). Search algorithms are given for partial match queries with t keys specified [proven maximum running time of O ( n ( k - t )/ k )] and for nearest neighbor queries [empirically observed average running time of O (log n ).] These performances far surpass the best currently known algorithms for these tasks. An algorithm is presented to handle any general intersection query. The main focus of this paper is theoretical. It is felt, however, that k -d trees could be quite useful in many applications, and examples of potential uses are given.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,320
An Algorithm for Finding Best Matches in Logarithmic Expected Time
Friedman, J. H., Bentley, J. L., & Finkel, R. A. (1977) · ACM Transactions on Mathematical Software · doi:10.1145/355744.355745 · Cited by 2,813
Self-citationQuad trees a data structure for retrieval on composite keys
Finkel, R. A., & Bentley, J. L. (1974) · Acta Informatica · doi:10.1007/bf00288933 · Cited by 2,041
Self-citationBlum, M., Floyd, R. W., Pratt, V., Rivest, R. L., & Tarjan, R. E. (1973) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(73)80033-9 · Cited by 1,235
Vasconcelos, W. V. (1998) · Algorithms and Computation in Mathematics · doi:10.1007/978-3-642-58951-5_2 · Cited by 404
An Algroithm for Finding Best Matches in Logarithmic Expected Time
Friedman, J. H., Bentley, J. L., & Finkel, R. A. (1976) · Cited by 9
Self-citation
Cited by
Items 101–158 of 158
Text-Based Twitter User Geolocation Prediction
Han, B., Cook, P., & Baldwin, T. (2014) · Journal of Artificial Intelligence Research · doi:10.1613/jair.4200 · Cited by 324
Active Constraints/Virtual Fixtures: A Survey
Bowyer, S. A., Davies, B. L., & Rodriguez y Baena, F. (2014) · IEEE Transactions on Robotics · doi:10.1109/tro.2013.2283410 · Cited by 316
Understanding and Enhancement of Internal Clustering Validation Measures
Liu, Y., Li, Z., Xiong, H., Gao, X., Wu, J., & Wu, S. (2013) · IEEE Transactions on Cybernetics · doi:10.1109/tsmcb.2012.2220543 · Cited by 315
A simple algorithm for nearest neighbor search in high dimensions
Nene, S. A., & Nayar, S. K. (1997) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.615448 · Cited by 311
Atkeson, C. G., Moore, A. W., & Schaal, S. (1997) · Lazy Learning · doi:10.1007/978-94-017-2053-3_2 · Cited by 308
Visualizing Large-scale and High-dimensional Data
Tang, J., Liu, J., Zhang, M., & Mei, Q. (2016) · Proceedings of the 25th International Conference on World Wide Web · doi:10.1145/2872427.2883041 · Cited by 306
Spatial crowdsourcing: a survey
Tong, Y., Zhou, Z., Zeng, Y., Chen, L., & Shahabi, C. (2020) · The VLDB Journal · doi:10.1007/s00778-019-00568-7 · Cited by 305
A local density-based approach for outlier detection
Tang, B., & He, H. (2017) · Neurocomputing · doi:10.1016/j.neucom.2017.02.039 · Cited by 301
ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms
Aumüller, M., Bernhardsson, E., & Faithfull, A. (2020) · Information Systems · doi:10.1016/j.is.2019.02.006 · Cited by 300
Perceptual Metrics for Image Database Navigation
Rubner, Y., & Tomasi, C. (2001) · Springer eBooks · doi:10.1007/978-1-4757-3343-3 · Cited by 296
Analysis of human faces using a measurement-based skin reflectance model
Weyrich, T., Matusik, W., Pfister, H., Bickel, B., Donner, C., Tu, C., McAndless, J., Lee, J., Ngan, A., Jensen, H. W., et al. (2006) · ACM Transactions on Graphics · doi:10.1145/1141911.1141987 · Cited by 291
High Accuracy and Visibility-Consistent Dense Multiview Stereo
Vu, H.-H., Labatut, P., Pons, J.-P., & Keriven, R. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.172 · Cited by 284
Guided Locality Preserving Feature Matching for Remote Sensing Image Registration
Ma, J., Jiang, J., Zhou, H., Zhao, J., & Guo, X. (2018) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2018.2820040 · Cited by 283
Computational Geometry—A Survey
Lee, & Preparata (1984) · IEEE Transactions on Computers · doi:10.1109/tc.1984.1676388 · Cited by 283
Polarization and Fake News: Early Warning of Potential Misinformation Targets
Vicario, M. D., Quattrociocchi, W., Scala, A., & Zollo, F. (2019) · ACM Transactions on the Web · doi:10.1145/3316809 · Cited by 280
Pairtools: From sequencing data to chromosome contacts
Open2C, Abdennur, N., Fudenberg, G., Flyamer, I. M., Galitsyna, A. A., Goloborodko, A., Imakaev, M., & Venev, S. V. (2024) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1012164 · Cited by 279
TempestExtremes: a framework for scale-insensitive pointwise feature tracking on unstructured grids
Ullrich, P. A., & Zarzycki, C. M. (2017) · Geoscientific Model Development · doi:10.5194/gmd-10-1069-2017 · Cited by 275
RNN-DBSCAN: A Density-Based Clustering Algorithm Using Reverse Nearest Neighbor Density Estimates
Bryant, A., & Cios, K. (2018) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2017.2787640 · Cited by 273
Searching in metric spaces by spatial approximation
Navarro, G. (2002) · The VLDB Journal The International Journal on Very Large Data Bases · doi:10.1007/s007780200060 · Cited by 272
Liu, X., Su, Y., Hu, T., Yang, Q., Liu, B., Deng, Y., Tang, H., Tang, Z., Fang, J., & Guo, Q. (2022) · Remote Sensing of Environment · doi:10.1016/j.rse.2021.112844 · Cited by 270
Survey of Improving K-Nearest-Neighbor for Classification
Jiang, L., Cai, Z., Wang, D., & Jiang, S. (2007) · Fourth International Conference on Fuzzy Systems and Knowledge Discovery (FSKD 2007) · doi:10.1109/fskd.2007.552 · Cited by 270
Similarity searching in medical image databases
Petrakis, E. G. M., & Faloutsos, A. (1997) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.599932 · Cited by 269
Lim, H., Hwang, S., & Myung, H. (2021) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2021.3061363 · Cited by 268
PDB file parser and structure class implemented in Python
Hamelryck, T., & Manderick, B. (2003) · Bioinformatics · doi:10.1093/bioinformatics/btg299 · Cited by 266
Experiments on neural net recognition of spoken and written text
Burr, D. J. (1988) · IEEE Transactions on Acoustics, Speech, and Signal Processing · doi:10.1109/29.1643 · Cited by 263
Dimensionality reduction for similarity searching in dynamic databases
Ravi Kanth, K. V., Agrawal, D., & Singh, A. (1998) · Proceedings of the 1998 ACM SIGMOD international conference on Management of data · doi:10.1145/276304.276320 · Cited by 256
OPALS – A framework for Airborne Laser Scanning data analysis
Pfeifer, N., Mandlburger, G., Otepka, J., & Karel, W. (2014) · Computers, Environment and Urban Systems · doi:10.1016/j.compenvurbsys.2013.11.002 · Cited by 252
Retrieval-Augmented Generation for AI-Generated Content: A Survey
Zhao, P., Zhang, H., Yu, Q., Wang, Z., Geng, Y., Fu, F., Yang, L., Zhang, W., Jiang, J., & Cui, B. (2024) · arXiv · doi:10.48550/arxiv.2402.19473 · Cited by 240
Scalable learning of collective behavior based on sparse social dimensions
Tang, L., & Liu, H. (2009) · Proceedings of the 18th ACM conference on Information and knowledge management · doi:10.1145/1645953.1646094 · Cited by 233
Panjkovich, A., & Svergun, D. I. (2016) · Physical Chemistry Chemical Physics · doi:10.1039/c5cp04540a · Cited by 204
Survey of Vector Database Management Systems
Pan, J. J., Wang, J., & Li, G. (2023) · arXiv · doi:10.48550/arxiv.2310.14021 · Cited by 184
Detection of differentially abundant cell subpopulations in scRNA-seq data
Zhao, J., Jaffe, A., Li, H., Lindenbaum, O., Sefik, E., Jackson, R., Cheng, X., Flavell, R. A., & Kluger, Y. (2021) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2100293118 · Cited by 154
Tsintotas, K. A., Bampis, L., & Gasteratos, A. (2022) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2022.3175656 · Cited by 175
“, k-d trees [395], randomized k-d forests [396], [397], Chow Liu trees [398], decision trees [399], BK tree [400].”
MethodA survey on knowledge-oriented retrieval-augmented generation
Cheng, M., Luo, Y., Ouyang, J., Liu, Q., Liu, H., Li, L., Yu, S., Zhang, B., Cao, J., Ma, J., et al. (2025) · arXiv · doi:10.48550/arxiv.2503.10677 · Cited by 140
Fast and scalable search of whole-slide images via self-supervised deep learning
Chen, C., Lu, M. Y., Williamson, D. F. K., Chen, T. Y., Schaumberg, A. J., & Mahmood, F. (2022) · Nature Biomedical Engineering · doi:10.1038/s41551-022-00929-8 · Cited by 130
Li, C., Virgilio, M. C., Collins, K. L., & Welch, J. D. (2023) · Nature Biotechnology · doi:10.1038/s41587-022-01476-y · Cited by 130
A computational study of mental health awareness campaigns on social media
Saha, K., Torous, J., Ernala, S. K., Rizuto, C., Stafford, A., & De Choudhury, M. (2019) · Translational Behavioral Medicine · doi:10.1093/tbm/ibz028 · Cited by 93
Zomorodian, A., & Carlsson, G. (2008) · Computational Geometry · doi:10.1016/j.comgeo.2008.02.003 · Cited by 89
Otake, Y., Wang, A. S., Webster Stayman, J., Uneri, A., Kleinszig, G., Vogt, S., Khanna, A. J., Gokaslan, Z. L., & Siewerdsen, J. H. (2013) · Physics in Medicine and Biology · doi:10.1088/0031-9155/58/23/8535 · Cited by 89
“In this study, we employed a standard kD-tree partitioning strategy (Bentley 1975) in 3D, where the largest box (space) was recursively partitioned into two boxes at the middle of its longest edge until the number of boxes reaches a desired number, N (equal to the number of multi-starts).”
MethodHeinzerling, B., & Inui, K. (2021) · Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume · doi:10.18653/v1/2021.eacl-main.153 · Cited by 78
An Overview of Perceptual Hashing
Farid, H. (2021) · Journal of Online Trust and Safety · doi:10.54501/jots.v1i1.24 · Cited by 70
So, M., Ohnishi, T., Park, K., Ono, M., Tsuge, Y., & Inoue, G. (2019) · International Journal of Hydrogen Energy · doi:10.1016/j.ijhydene.2019.09.012 · Cited by 58
Teacher algorithms for curriculum learning of Deep RL in continuously parameterized environments
Portelas, R., Colas, C., Hofmann, K., & Oudeyer, P.-Y. (2019) · arXiv · doi:10.48550/arxiv.1910.07224 · Cited by 59
LLMatic: Neural Architecture Search Via Large Language Models And Quality Diversity Optimization
Nasir, M. U., Earle, S., Togelius, J., James, S., & Cleghorn, C. (2024) · Proceedings of the Genetic and Evolutionary Computation Conference · doi:10.1145/3638529.3654017 · Cited by 52
A Deep Step Pattern Representation for Multimodal Retinal Image Registration
Lee, J., Liu, P., Cheng, J., & Fu, H. (2019) · 2019 IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2019.00518 · Cited by 56
Bayesian nonparametric learning of cloth models for real-time state estimation
Koganti, N., Tamei, T., Ikeda, K., & Shibata, T. (2017) · IEEE Transactions on Robotics · doi:10.1109/tro.2017.2691721 · Cited by 41
3D–2D registration in mobile radiographs: algorithm development and preliminary clinical evaluation
Otake, Y., Wang, A. S., Uneri, A., Kleinszig, G., Vogt, S., Aygun, N., Lo, S.-F. L., Wolinsky, J.-P., Gokaslan, Z. L., & Siewerdsen, J. H. (2015) · Physics in Medicine & Biology · doi:10.1088/0031-9155/60/5/2075 · Cited by 41
Hanke, L., Sheward, D. J., Pankow, A., Vidakovics, L. P., Karl, V., Kim, C., Urgard, E., Smith, N. L., Astorga-Wells, J., Ekström, S., et al. (2022) · Science Advances · doi:10.1126/sciadv.abm0220 · Cited by 38
Software to convert terrestrial LiDAR scans of natural environments into photorealistic meshes
Risse, B., Mangan, M., Stürzl, W., & Webb, B. (2018) · Environmental Modelling & Software · doi:10.1016/j.envsoft.2017.09.018 · Cited by 34
Semantic-Enhanced Differentiable Search Index Inspired by Learning Strategies
Tang, Y., Zhang, R., Guo, J., Chen, J., Zhu, Z., Wang, S., Yin, D., & Cheng, X. (2023) · Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining · doi:10.1145/3580305.3599903 · Cited by 29
On Approximately Searching for Similar Word Embeddings
Sugawara, K., Kobayashi, H., & Iwasaki, M. (2016) · Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/p16-1214 · Cited by 28
Redundant Bit Vectors for Quickly Searching High-Dimensional Regions
Goldstein, J., Plat, J. C., & Burges, C. J. C. (2005) · Lecture Notes in Computer Science · doi:10.1007/11559887_9 · Cited by 22
Predicting improved protein conformations with a temporal deep recurrent neural network
Pfeiffenberger, E., & Bates, P. A. (2018) · PLOS ONE · doi:10.1371/journal.pone.0202652 · Cited by 21
BusTime: Which is the Right Prediction Model for My Bus Arrival Time?
Liu, D., Sun, J., & Wang, S. (2020) · 2020 5th IEEE International Conference on Big Data Analytics (ICBDA) · doi:10.1109/icbda49040.2020.9101265 · Cited by 11
Detecting fabrication in large-scale molecular omics data
Bradshaw, M. S., & Payne, S. H. (2021) · PLOS ONE · doi:10.1371/journal.pone.0260395 · Cited by 8
Resilient K-d Trees: K-Means in Space Revisited
Gieseke, F., Moruz, G., & Vahrenhold, J. (2010) · 2010 IEEE International Conference on Data Mining · doi:10.1109/icdm.2010.94 · Cited by 3
P-HNSW: Crash-Consistent HNSW for Vector Databases on Persistent Memory
Lee, H., Park, T., Na, Y., & Kim, W.-H. (2025) · Applied Sciences · doi:10.3390/app151910554 · Cited by 1
Pritzel, A., Uria, B., Srinivasan, S., Puigdomènech, A., Vinyals, O., Hassabis, D., Wierstra, D., & Blundell, C. (2017) · arXiv · doi:10.48550/arxiv.1703.01988
Metadata
- Authors
- Bentley, J. L.
- Venue
- Communications of the ACM
- Published
- 1975-09
- Volume
- 18
- Issue
- 9
- Pages
- 509-517
- ISSN
- 0001-0782 (ISSN-L)
- 1557-7317
- OpenAlex
- W2165558283
- Cited by
- 7,520
- References
- 6
- FWCI
- 10.12
- Type
- journal article
- Language
- en
- Open access
- bronze
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.