2722	 Multidimensional Binary Search Trees Used for Associative Searching	 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 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- 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 theoretical. It is felt however that k-d trees could be quite useful in many applications and examples of potential uses are given. associative retrieval binary search trees key attribute information retrieval system nearest neighbor queries partial match queries intersection queries binary tree insertion
