Journal of the ACM · 1986 · 118 citations · 18 references
ComputingComputer ScienceData StructuresDatabasesInformation RetrievalDimensionality ReductionNearest Neighbor SearchRetrieval ModelsSearch SystemsSearching AlgorithmsContour IntegrationData MatchingIndex StructuresK-d TreesNearest Neighbor Data StructuresRetrievalSimilarity Search
A precise analysis of partial match retrieval of multidimensional data is presented. The structures considered here are multidimensional search trees ( k -d-trees) and digital tries ( k -d-tries), as well as structures designed for efficient retrieval of information stored on external devices. The methods used include a detailed study of a differential system around a regular singular point in conjunction with suitable contour integration techniques for the analysis of k -d-trees, and properties of the Mellin integral transform for k -d-tries and extendible cell algorithms.
18
Multidimensional binary search trees used for associative searching
Jon Bentley · Communications of the ACM · 1975 · 7.5K citations · Full text
The Art of Computer Programming
G.E. Whitesides · Nuclear Science and Engineering · 1970 · 6.1K citations
J. Nievergelt, Hans Hinterberger, Kenneth C. Sevcik · ACM Transactions on Database Systems · 1984 · 1.1K citations · Full text