Sage Journals: Discover world-class research

Abstract

Similarity searching is the core of many applications in artificial intelligence since it solves problems like nearest neighbor searching. A common approach to similarity searching consists in mapping the database to a metric space in order to build an index that allows for fast searching. One of the most powerful searching algorithms for high dimensional data is known as the permutation based algorithm (PBA). However, PBA has to collect the most similar permutations to a given query’s permutation. In this paper, how to speed up this process by proposing several novel hash functions for Locality Sensitive Hashing (LSH) with PBA is shown. As a matter of fact, at searching our technique allows discarding up to 50% of the database to answer the query with a candidate list obtained in constant time.

Keywords

Nearest neighbor similarity searching metric spaces

Get full access to this article

View all access options for this article.

References

Amato

and Savino

, Approximate similarity search in metric spaces using inverted files, In 3rd International ICST Conference on Scalable Information Systems, INFOSCALE 2008, Vico Equense, Italy, 2008, p. 28. doi: 10.4108/ICST.INFOSCALE2008.3486. URL https://doi.org/10.4108/ICST.INFOSCALE2008.3486.

Chávez

and Navarro

, A probabilistic spell for the curse of dimensionality, In 3rd Workshop on Algorithm Engineering and Experiments (ALENEX’01), volume 2153 of Lecture Notes in Computer Science, 2001, pp. 147–160.

Chávez

, Navarro

, Baeza-Yates

and Marroquín

, Proximity searching in metric spaces, ACM Computing Surveys33(3) (2001), 273–321.

Chávez

, Figueroa

and Navarro

, Effective proximity retrieval by ordering permutations, IEEE Trans on Pattern Analysis and Machine Intelligence (TPAMI)30(9) (2009), 1647–1658.

Esuli

, Use of permutation prefixes for efficient and scalable approximate similarity search, Inf Process Manage48(5) (2012), 889–902. ISSN 0306-4573. doi: 10.1016/j.ipm.2010.11.011. URL http://dx.doi.org/10.1016/j.ipm.2010.11.011.

Figueroa

and Paredes.

, An effective permutant selection heuristic for proximity searching in metric spaces, In Proc 6th Mexican Conf on Pattern Recognition (MCPR’14), LNCS 8495, 2014, pp. 102–111.

Figueroa

, Navarro

, Chávez

, Metric spaces library, 2007. Available at http://www.sisap.org/Metric_Space_Library.html.

Gionis

, Indyk

and Motwani

, Similarity search in high dimensions via hashing, VLDB’99 Proceedings of the 25th International Converence on Very Large Data Bases, 1999, pp. 518–529.

Navarro

, Paredes

, Reyes

and Bustos

, An empirical evaluation of intrinsic dimension estimators, Inf Syst64(C) (2017), 206–218. ISSN 0306-4379. doi: 10.1016/j.is.2016.06.004. URL https://doi.org/10.1016/j.is.2016.06.004.

10.

Novak

and Batko

, Metric index: An efficient and scalable solution for similarity search, In Proceedings of the 2009 Second International Workshop on Similarity Search and Applications, SISAP ’09, Washington, DC, USA, 2009, pp. 65–73. IEEE Computer Society. ISBN 978-0-7695-3765-8. doi: 10.1109/SISAP.2009.26. URL http://dx.doi.org/10.1109/SISAP.2009.26.

11.

Novak

, Kyselak

and Zezula

, On localitysensitive indexing in generic metric spaces, In Proceedings of the Third International Conference on SImilarity Search and APplications, SISAP ’10, New York, NY, USA, 2010, pp. 59–66. ACM. ISBN 978-1-4503-0420-7. doi: 10.1145/1862344.1862354. URL http://doi.acm.org/10.1145/1862344.1862354.

12.

Samet

, Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2005. ISBN 0123694469.

13.

Tellez

E.S.

and Chavez

, On locality sensitive hashing in metric spaces, In Proceedings of the Third International Conference on SImilarity Search and APplications, SISAP ’10, New York, NY, USA, 2010, pp. 67–74. ACM. ISBN 978-1-4503-0420-7. doi: 10.1145/1862344.1862355. URL http://doi.acm.org/10.1145/1862344.1862355.

14.

Zezula

, Amato

, Dohnal

and Batko

, Similarity Search: The Metric Space Approach, volume 32 of Advances in Database Systems, Springer, 2006.

Locality-sensitive hashing of permutations for proximity searching

Abstract

Keywords

Get full access to this article

References