LIDH: An Efficient Filtering Method for Approximate к Nearest Neighbor Queries Based on Local Intrinsic Dimension

摘要

Due to the so-called "curse of dimensionality" causing poor performance when querying in the high-dimensional space, the high-dimensional approximate fcNN (AfcNN) query has been extensively explored to trade accuracy for efficiency. In this paper, we propose a Local Intrinsic Dimension-based Hashing (LIDH) method for the high-dimensional AkNN query which locates a definite searching range by Local Intrinsic Dimensionality for filtering data points. Specifically, we propose a filter-refinement model for the AfcNN query to avoid the virtual rehashing with fewer index space. Experimental evaluations demonstrate that our method can provide higher I/O and CPU efficiency while retaining satisfactory query accuracies.