SK-LSH

• DOI: 10.14778/2732939.2732947
• Publication Date: 2015-05-12T15:37:52Z
• Authors: Yingfan Liu; Jiangtao Cui; Zi Huang; Hui Li; Heng Tao Shen
• Keywords: Locality-sensitive hashing

Approximate Nearest Neighbor (ANN) search in high dimensional space has become a fundamental paradigm many applications. Recently, Locality Sensitive Hashing (LSH) and its variants are acknowledged as the most promising solutions to ANN search. However, state-of-the-art LSH approaches suffer from drawback: accesses candidate objects require large number of random I/O operations. In order guarantee quality returned results, sufficient should be verified, which would consume enormous cost. To address this issue, we propose novel method, called SortingKeys-LSH (SK-LSH), reduces page through locally arranging objects. We firstly define new measure evaluate distance between compound hash keys two points. A linear relationship on set is then created, corresponding data points can sorted accordingly. Hence, that close each other according stored an index file. During search, only limited disk pages among few files necessary accessed for generation verification, not significantly response time but also improves accuracy results. Our exhaustive empirical study over several real-world sets demonstrates superior efficiency SK-LSH compared with methods, including LSB, C2LSH CK-Means.