The Computer Journal Advance Access originally published online on June 21, 2006
The Computer Journal 2006 49(6):670-684; doi:10.1093/comjnl/bxl035
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||
Persistent Semi-Dynamic Ordered Partition Index
Department of Computer Science, New Jersey Institute of Technology NJIT, Newark, NJ 07102, USA
*Corresponding author: alexthomasian{at}gmail.com
Similarity search is a popular paradigm in advanced database applications. In content based image retrieval (CBIR) for example, images are transformed into feature vectors, which are then used for similarity search via k-nearest-neighbor (k-NN) queries in the feature vector space. Clustering by building a disk resident index is one method to speed up the processing of k-NN queries. In the case of high-dimensional feature vectors the dimensionality curse results in a high degree of overlap among the minimum bounding rectangles of the index, which results in most pages of the index being accessed. This is especially detrimental to performance, since disk positioning time for random disk accesses is slow and improving only at a rate of 8% annually. We propose an alternative solution to indexing high-dimensional data, which takes advantage of increasing main memory sizes and the 40% annual improvement in disk transfer rates, More specifically we make the Ordered-Partition—OP-tree, which is a main memory resident index, persistent by writing it onto disk. We investigate the optimization of OP-tree parameters and compare its performance with the sequential scan method with and without Karhunen–Loève transformation. We use serialization to compact the dynamically allocated nodes of the OP-tree in main memory, which form a linked list, into a contiguous area. The index can then be saved on disk as a single file and loaded into main memory by a single transfer. The original OP-tree is static, so we propose several methods to support the insertion of new points dynamically. We compare these methods from the viewpoints of time and space efficiency. We also study the effect of incrementally building the index with and without applying the Karhunen-Loève transformation. We compare the processing time of k-NN queries on persistent OP-trees and SR-trees to demonstrate the viability of the proposed method. We use one synthetic and three real world datasets in our experiments.
Key Words: Multimedia databases • feature vectors • similarity search • nearest neighbor queries • high dimensional indexing • persistent index