Speed Up Distance-Based Similarity Query Using Multiple Threads

Metric-space indexing, also known as distance-based indexing, is a universal indexing to support similarity queries. It only requires that the similarity of data be defined by a metric distance function. To achieve the great universalness, metric-space indexing does not take use of the domain information of data, and is thus outperformed by many domain-specific methods. In this paper, to speed up metric-space similarity query, we first assign one thread for each query in the multi-query case to increase the throughput. Then, for a single query, we assign one thread for each search path from the root of the index tree to decrease the responding time. Last but not least, we implement an in-memory buffer to break the bottleneck of the disk access to the index file. Experimental results show that our efforts result in good speed up and parallel efficiency.