Locality-sensitive hashing: Difference between revisions

Revision as of 07:27, 19 May 2023

Revision as of 16:55, 5 June 2023

Line 301:

When {{mvar|t}} is large, it is possible to reduce the hashing time from <math>O(n^{\rho})</math>.

This was shown by<ref>Dahlgaard, Søren, Mathias Bæk Tejs Knudsen, and Mikkel Thorup. [https://arxiv.org/pdf/1704.04370 "Fast similarity sketching."] 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2017.</ref> and<ref>Christiani, Tobias. [https://arxiv.org/pdf/1708.07586 "Fast locality-sensitive hashing frameworks for approximate near neighbor search."] International Conference on Similarity Search and Applications. Springer, Cham, 2019.</ref> which gave

* query time: <math>O(t\log^2(1/P_2)/P_1 + n^{\rho}(d + 1/P_1))</math>;

* space: <math>O(n^{1+\rho}/P_1 + \log^2(1/P_2)/P_1)</math>;