Optimal Load Factor for Appro ximate Nearest Neighbor Search u nder Exact Euclidean Locality Sens itive Hashing

Locality Sensitive Hashing (LSH) is an index - based data structure that allows spatial item retrieval over a large data set . 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, a i h as been used by researchers . In t his paper , we d emonstrate that the choice of a i does 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 a e . Experiments on the Defense Meteoro logical Satellite Program imagery datasethave show n that a e saves more than 7 5 % o n memory sp ace; cuts the computational complexity by more than 7 0 % and answers query t wo times faster on the average compared to that of a i .