On Parallelization Of Metric Space Index MVP-tree For Similarity Searching

Similarity indexing plays an important role in multimedia and biological data management. Confronting the challenge of “variety”, traditional way is to provide customized solutions to each data types. Although these customized solutions generally performs well, it is very costly to build and maintain them. Metric-space indexing abstracts data of various types into metric space, and takes use of the triangle inequality of the distance function of data to acquire pruning. Since it requires neither the data to have coordinates, nor the distance function to be Euclidean, metric-space indexing forms a universal solution, which is widely applicable and cost effective. However, lacking of domain information, metric-space indexing is generally slower than customized solutions. In this thesis, we try to accelerate MVP-tree, a popular metric-space index, by redesigning and implementing it in parallel. Our contributions include:(1) A parallel bulkload of MVP-tree is designed and implemented with multiple threads.(2) A parallel query system of MVP-tree is designed and implemented with multiple threads. Mechanisms of thread allocation, index caching, and intra- or inter- query parallel processing are proposed to improve the responding time and throughput. In addition, good combinations of parameters are experimentally determined for various circumstances.(3) A local index framework for parallel and distributed similarity indexing with MVP-tree is implemented, which is also integrated with multiple threads MVP-tree on each computing node for even better performance.(4) All the above are implemented in the context of the UMAD project, in particular its indexing module, Ge DBIT. A test platform is built. Experimental results show that the speed of MVP-tree is substantially improved.