Optimal Load Factor for Approximate Nearest Neighbor Search under Exact Euclidean Locality Sensitive Hashing
Ruben Buaba, Abdollah Homaifar, E. A. Kihn · International Journal of Computer Applications · 2013
Locality Sensitive Hashing (LSH) is an index-based data structure that allows spatial item retrieval over a large dataset.The performance measure, ρ, has significant effect on the computational complexity and memory space requirement to create and store items in this data structure respectively.The minimization of ρ at a specific approximation factor c, is dependent on the load factor, α.Over the years,𝛼 = 4has been used by researchers.In this paper, we demonstratethat the choice of𝛼 = 4does not guarantee low computational complexity and low memory space of the data structure under the LSH scheme.To guarantee low computational complexity and low memory space, we propose𝛼 = 5.Experiments on the Defense Meteorological Satellite Program imagery datasethave shown that𝛼 = 5saves more than 75%on memory space; cuts the computational complexity by more than 70%andanswers query two times faster on the average compared to that of𝛼 = 4.