LuneSearch: Addressing the Distributed Case of Similarity Search

Database Systems today need to deal with growing amounts of unstructured data that is mapped to high dimensional vectors. When this data is mapped to these feature spaces, items that are similar are located closer together. The problem is then as simple as to retrieve the top k-nearest neighbors to the given query. However, the k-nearest neighbor problem has long been an area of research with decades of effort dedicated to the exact version of the problem without much success. Then again, these mappings of objects into vectors may not be completely accurate which in turn makes approximate nearest neighbors acceptable in many scenarios. Many early exact algorithms were tree-based and later tree-based, hash-based, quantization-based and graph-based algorithms were proposed for the k-approximate version of the problem. According to recent benchmarks graph-based algorithms generally perform the best and quantization-based algorithms are also among the top performers. However efficient partitioning, routing and equal distribution of the query load remain challenging for the best performing algorithms in the distributed scenario. This paper proposes LuneSearch, an approach to build a distributed search engine to address these concerns. It uses a random sample of the dataset to calculate the centers, dynamically selects partitions for search and keeps the graph indexes small for easier redistribution of query load.