We are currently witnessing a rapid growth of image data, triggered by the popularity of the Internet and the huge amount of user-generated content from Web 2.0 applications. Given such image collections, performing similarity search to find objects most similar to a given object is a classical problem with many applications. In principle, there are two basic types of similarity query: an ε-range query and a k-nearest neighbors (k-NN) query. Given a set of data points represented in a high-dimensional space and the distance measurement between them, an ε-range query is used to find all objects with a distance smaller or equal to a given range ε from a query point, whereas a k-NN query is used to return the k-most similar neighbors of the query point.
To support a similarity search in very large collections of high-dimensional data, a number of distributed index structures for high-dimensional data spaces have been proposed. Most of the approaches recently published focus mainly on supporting range queries, or operating in decentralized systems. Locality Sensitive Hashing (LSH) Forest and LSH At Large leverage the LSH to provide approximate results to a k-NN search. LSH has received considerable attention recently, because it was shown that its runtime is independent of the dimension of feature vectors for querying. However, LSH, which probabilistically assigns similar data to the same bucket in a hash table, is not suitable for skewed data and can be highly inaccurate in a similarity search. SkipIndex is based on a K-D-tree in partitioning the data space, and maps the data space into a skip graph overlay network by encoding the space into a unique key. The DiST(Distributed Search Tree) and VBI-tree(Virtual Binary Index-tree) are also tree-based approaches, which do not scale well when data dimensions are high.
Several approaches to parallelize an NN search on the centralized systems have been developed. The approaches like the Master R-tree and Master-Client R-trees, GPR-tree (Global Parallel R-tree), and distributed hybrid spill-tree have tried to parallelize the tree-based structure. Parallel VA-files(Vector Approximation-files) and parallel CBF(Cell-Based Filtering) proposed a parallel NN-search based on the VA-file to achieve a linear increase of search speed as the number of servers grows. However, the query response times of these solutions are not satisfactory for a search engine on the World-Wide Web.
In order to provide a similarity search on massive high-dimensional data in cloud computing services or web search services, we propose a high-dimensional indexing structure, called the Distributed Vector Approximation-tree (DVA-tree), which operates in a cluster environment. We have designed a centralized indexing structure to solve the search performance and accuracy problem of decentralized indexing methods. The DVA-tree partitions a feature vector space in a hierarchical tree manner and maps leaf nodes of the tree into separate servers in a cluster environment. Then, we build an index and retrieve neighbors by using the VA-file, as the local index on separate servers. In conclusion, we propose a mechanism that efficiently distributes VA-files in order to increase k-NN search performance, as well as to support index scalability for large-scale data.
In this thesis, we make the following contributions: (i) We present a new distributed index scheme, called DVA-tree, that combines a tree-based index structure with a scan method using the VA-files; (ii) we present an approximate k algorithm to process the distributed k-NN search and propose cost formulas for predicting the response time of the k-NN search; (iii) For ununiform datasets, we enhance the k-NN search performance of DVA-tree by VA-files using independent encoding of vector data; (iv) finally, we experiment and evaluate the efficiency and effectiveness of our approach using the skewed data and uniformly distributed data.
The experiment results of the DVA-tree show that our proposed method, the DVA-tree, has significant performance advantage over existing index structures on ununiform data. We believe that the DVA-tree is the most suitable candidate to support high search performance, as well as index scalability for large-scale datasets.