Techniques for efficient k-Nearest Neighbor searching in non-ordered discrete and hybrid data spaces
Dashiell Kolbe · 2010
Similarity searches/queries in Non-Ordered Discrete Data Spaces (NDDS) and Hybrid Data Spaces (HDS) are becoming increasingly useful in areas such as bioinformatics, multimedia, text retrieval, audio and video compression, data-mining, and E-commerce. The objective of this dissertation is to develop and analyze novel methods to support similarity searches in such spaces. In this dissertation, we first discuss performing k-Nearest Neighbor (k-NN) searches in NDDSs. Performing such searches in NDDSs raises new challenges. Due to the coarse granularity of the commonly used Hamming distance measure, a nearest neighbor query in an NDDS may lead to a large set of candidate solutions, creating a high degree of non-determinism. We propose a new distance measure that reduces the number of candidate solutions for a query while preserving the essential properties of Hamming distance. We have also implemented nearest neighbor queries using multidimensional database indexing in NDDSs. We use the properties of ourmultidimensional NDDS index to derive the probability of encountering new neighbors within specific regions of the index. This probability is used to develop a new search ordering heuristic. Our experiments demonstrate that our nearest neighbor