Preserving-Ignoring Transformation Based Index for Approximate k Nearest Neighbor Search

摘要: Locality sensitive hashing (LSH) and its variants are widely used for approximate kNN (k nearest neighbor) search in high-dimensional space. The success of these techniques largely depends on the ability preserving information. Unfortunately, LSH only provides a high probability that nearby points original space projected into region new This potentially makes many false positives negatives resulting from unrelated points. Many extensions aim to alleviate above issue by improving distance ability. In this paper, we abound function but propose novel idea enhance performance transforming data before applying LSH. A preserving-ignoring transformation (PIT) satisfying some rigorous conditions can be convert an interim with strict capacity. Based property, linear order is utilized build efficient index structure Finally, applied candidate set searched our final results. Experiments conducted proposed approach performs better than state-of-the-art methods SK-LSH, DSH NSH terms both accuracy efficiency.