Scalability comparison of Peer-to-Peer similarity search structures

Abstract

Due to the increasing complexity of current digital data, similarity search has become a fundamental computational task in many applications. Unfortunately, its costs are still high and grow linearly on single server structures, which prevents them from efficient application on large data volumes. In this paper, we shortly describe four recent scalable distributed techniques for similarity search and study their performance in executing queries on three different datasets. Though all the methods employ parallelism to speed up query execution, different advantages for different objectives have been identified by experiments. The reported results would be helpful for choosing the best implementations for specific applications. They can also be used for designing new and better indexing structures in the future.

Introduction

Efficient lookup for specific keywords in a dictionary containing hundreds of thousands of words or locating specific records in millions of bank accounts are quite easy tasks for present-day computers. Since records in such domains can be sorted, and every record either fully satisfies the search condition or it does not at all, hashing or tree-like structures can be applied as indexes. High scalability of such technologies is guaranteed by logarithmically bounded search time with respect to the size of the file.

However, to find images of sport cars, time series with similar development, or groups of customers with common buying patterns in respective data collections, the traditional technologies simply fail. Here, the required comparison is gradual, rather than binary, because, once a reference (query) pattern is given, each instance in a search file and the pattern are in certain relation measured by a user-defined dissimilarity function. Such a searching is more and more important for a variety of current complex digital data collections and is generally designated as the similarity search.

Although many similarity search approaches have been proposed, the most generic one considers the mathematical metric space as a suitable abstraction of similarity [1]. The simple but powerful concept of the metric space consists of a domain of objects and a distance function that measures proximity of pairs of objects. It can be applied not only to multi-dimensional vector spaces, but also to different forms of string objects, as well as to sets or groups of various nature, etc. Although many index structures have been proposed, the similarity search is inherently expensive. Besides, the linear increase of the search time prevents them from application to huge files that have become common and the predictions expect a continuous rapid growth.

Very recently, we have proposed four scalable distributed similarity search structures for metric data. The first two structures adopt the basic ball and generalized hyperplane partitioning principles [2] and they are called the ${\mathrm{VPT}}^{\ast }$ and the ${\mathrm{GHT}}^{\ast }$, respectively [3]. The other two apply transformation strategies — the metric similarity search problem is transformed into a series of range queries executed on existing distributed keyword structures, namely the CAN [4] and the Chord [5]. By analogy, we call them the MCAN [6] and the M-Chord [7]. Each of the structures is able to execute similarity queries for any metric dataset, and they all exploit parallelism for query execution. However, due to the completely different underlying principles, an important question arises: What are the advantages and disadvantages of the individual approaches in terms of search costs and scalability for different real-life search problems?

In this paper, we report on implementations of the ${\mathrm{VPT}}^{\ast }$, ${\mathrm{GHT}}^{\ast }$, MCAN and M-Chord systems over the same infrastructure of peer computers. We have conducted numerous experiments on three different datasets and present the most important findings. We focus on scalability with respect to the size of the query, the size of the dataset, and the number of queries executed simultaneously. The results reported in this paper have been presented on the INFOSCALE ’06 conference [8].

The rest of the paper is organized as follows. The necessary background and related work are reported in Section 2. A brief specification of our four indexing techniques is available in Section 3, while the assumptions and results of our experiments can be found in Section 4. The paper concludes in Section 5.