×

Optimal lower bounds for locality-sensitive hashing (except when \(q\) is tiny). (English) Zbl 1320.68095


MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68P05 Data structures
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Andoni and P. Indyk. 2006. Efficient algorithms for substring near neighbor problem. InProceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm. ACM, 1212. · Zbl 1192.68814
[2] A. Andoni and P. Indyk. 2008. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions.Commun. ACM 51, 1, 117–122. · Zbl 05394971 · doi:10.1145/1327452.1327494
[3] J. Buhler. 2001. Efficient large-scale sequence comparison by locality-sensitive hashing.Bioinformatics 17, 5, 419–428. · doi:10.1093/bioinformatics/17.5.419
[4] E. Cohen, M. Datar, S. Fujiwara, A. Gionis, P. Indyk, R. Motwani, J. D. Ullman, and C. Yang. 2002. Finding interesting associations without support pruning.IEEE Trans. Knowl. Data Eng. 13, 1, 64–78. · Zbl 05108584 · doi:10.1109/69.908981
[5] A. S. Das, M. Datar, A. Garg, and S. Rajaram. 2007. Google news personalization: Scalable online collaborative filtering. InProceedings of the 16th International Conference on World Wide Web. ACM, 271–280.
[6] M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. InProceedings of the 20th Annual Symposium on Computational Geometry (SCG’04). ACM, New York, NY, 253–262. · Zbl 1373.68193
[7] A. Gionis, P. Indyk, and R. Motwani. 1999. Similarity search in high dimensions via hashing. InProceedings of the 25th International Conference on Very Large Data Bases.
[8] P. Indyk and R. Motwani. 1998. Approximate nearest neighbors: Towards removing the curse of dimensionality. InProceedings of the 13th Annual ACM Symposium on Theory of Computing. ACM, New York, NY, 604–613. · Zbl 1029.68541
[9] P. Indyk. 2001.High-dimensional Computational Geometry. Doctoral dissertation, Stanford University.
[10] P. Indyk. 2004. Nearest neighbors in high-dimensional spaces. InHandbook of Discrete and Computational Geometry, Discrete Mathematics and Its Applications, Chapman and Hall/CRC, 877–892.
[11] P. Indyk. 2009. Personal communication.
[12] R. Motwani, A. Naor, and R. Panigrahy. 2007. Lower bounds on locality sensitive hashing.SIAM J. Disc. Math. 21, 4, 930–935. · Zbl 1158.68012 · doi:10.1137/050646858
[13] T. Neylon. 2010. A locality-sensitive hash for real vectors. InProceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. 1179–1189. · Zbl 1288.68049 · doi:10.1137/1.9781611973075.94
[14] R. O’Donnell. 2003.Computational Applications of Noise Sensitivity. Doctoral dissertation, Massachusetts Institute of Technology.
[15] R. Panigrahy. 2006. Entropy based nearest neighbor search in high dimensions. InProceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm. ACM, 1186–1195. · Zbl 1192.68217
[16] R. Panigrahy, K. Talwar, and U. Wieder. 2008. A geometric approach to lower bounds for approximate near-neighbor search and partial match. InProceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, 414–423.
[17] D. Ravichandran, P. Pantel, and E. Hovy. 2005. Randomized algorithms and NLP: Using locality sensitive hash function for high speed noun clustering. InProceedings of the 43rd Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics, 622–629.
[18] G. Shakhnarovich, P. Viola, and T. Darrell. 2003. Fast pose estimation with parameter-sensitive hashing. InProceedings of the 9th IEEE International Conference on Computer Vision. Citeseer, 750.
[19] K. Terasawa and Y. Tanaka. 2007. Spherical LSH for approximate nearest neighbor search on unit hypersphere. InProceedings of the 10th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 4619, Springer-Verlag, Berlin Heidelberg, 27–38. · Zbl 1209.68164
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.