Locality Sensitive Hashing Index Based on Optimal Linear Order

Nearest neighbor (NN) search in high-dimensional space is a fundamental paradigm in a wide range of applications, such as text information retrieval, search engine, content-based information query, duplication detection, etc. In these areas, data are usually large-scale and are modeled as high-dimensional features, which introduce two major problems to NN search, the "curse of dimensionality" and I/O performance bottleneck. On the one hand, the dimensionality curse makes exact NNs nearly infeasible to achieve. A lot of research efforts have been devoted to finding approximate nearest neighbors (ANN) which are close enough to the query to achieve a satisfying trade-off between accuracy and efficiency. On the other hand, large-scale feature sets are often too massive to fit into the internal memory, external storage (usually disk) becomes a reasonable choice. However, due to the huge speed gap between internal memory and external memory, the resulting input/output communication becomes very expensive, too much NN candidates or improper loading manner would make the NN candidates loading the most time-consuming part of the entire NN search, called the I/O performance bottleneck. LSH is a widely adopted technique due to its excellent error guarantee and high computational efficiency in tackling the "curse of dimensionality". It can enable fast and accurate irrelevant points filtration and offers c-ANN results at a sub-linear time complexity which also makes it an attractive approach for disk-based ANN search. Plenty of LSH based methods have been developed to further boost the ANN performance. However, most of them access candidate objects through significant random I/O operations, which makes them tend to incur the I/O performance bottleneck. In this work, a novel Locality-Sensitive Hashing (LSH) index called Optimal Order LSH (O2LSH) is designed to further address the above two problems. First, O2LSH introduces space-filling curves to sort the compound LSH keys and rearrange the original data points accordingly. In this way, NN candidates can be stored on same or adjacent disk pages so that only a few sequential I/O operations can load enough candidates during the search. A thorough quantitative analysis is then conducted on several common space-filling curves. The results show that there exists two different kinds of characteristic among these space-filling curves, (1) curves of "dimension-first-traverse" characteristic (such as the row-wise curve) tend to introduce several limitations to ANN search; (2) curves of "neighborhood-first-traverse" characteristic (such as Z-order, Gray curve, Hilbert curve, etc.) can produce better local distribution of NN candidate points, and the performance are more stable. Based on the analysis, O2LSH chooses a best "neighborhood-first-traverse" curve as the linear order to maintain as many as NN candidates within same local disk pages. In this way, O2LSH can not only enhance the I/O efficiency but also improve the ANN search accuracy. We conduct empirical experiments on 6 real-world multimedia data sets. The results demonstrate the superior accuracy and I/O efficiency of O2LSH in ANN search, compared with 4 state-of-the-art methods, including C2LSH, SK-LSH, SRS and QALSH. Particularly, O2LSH is no longer sensitive to a key parameter of LSH function as the basic sorting-based solution does, which further improves the algorithm practicality. © 2020, Science Press. All right reserved.