Fast &Dimensional Tree Algorithms for Nearest Neighbor Search with Application to Vector
Viswanathan Ramasubramanian, Kuldip K. Paliwal · 1992
In this paper, fast search algorithms are proposed and studied for vector quantization encoding using the K-di- mensional (K-d) tree structure. Here, the emphasis is on the optimal design of the K-d tree for efficient nearest neighbor search in multidimensional space under a bucket-Voronoi in- tersection search framework. Efficient optimization criteria and procedures are proposed for designing the K-d tree, for the case when the test data distribution is available (as in vector quantization applications in the form of training data) as well as for the case when the test data distribution is not available and only the Voronoi intersection information is to be used. The proposed optimization criteria and bucket-Voronoi inter- section search procedure are studied in the context of vector quantization encoding of speech waveform and are empirically observed to achieve constant search complexity for O(log N) tree depths. Comparisons are made with other optimization criteria-the maximum product criterion and Friedman et al.'s optimization criterion-and the proposed criteria are found to be more efficienl in reducing the search complexity. Under the framework used for obtaining the proposed optimization cri- teria, a geometric interpretation is given for the maximum product criterion explaining the reasons for its inefficiency with respect to the proposed optimization criteria.