Supermetric search
Connor R., Vadicamo L., Cardillo F. A., Rabitti F.
similarity search Metric space four-point property Hilbert exclusion Information Systems supermetric space Hardware and Architecture Supermetric space Similarity search Metric indexing metric space Four-point property Information Retrieval (cs.IR) FOS: Computer and information sciences Computer Science - Information Retrieval Hilbert Exclusion Software metric indexing H.3.3
Metric search is concerned with the efficient evaluation of queries in metric spaces. In general, a large space of objects is arranged in such a way that, when a further object is presented as a query, those objects most similar to the query can be efficiently found. Most mechanisms rely upon the triangle inequality property of the metric governing the space. The triangle inequality property is equivalent to a finite embedding property, which states that any three points of the space can be isometrically embedded in two-dimensional Euclidean space. In this paper, we examine a class of semimetric space which is finitely four-embeddable in three-dimensional Euclidean space. In mathematics this property has been extensively studied and is generally known as the four-point property. All spaces with the four-point property are metric spaces, but they also have some stronger geometric guarantees. We coin the term supermetric(1) space as, in terms of metric search, they are significantly more tractable. Supermetric spaces include all those governed by Euclidean, Cosine,(2) Jensen-Shannon and Triangular distances, and are thus commonly used within many domains. In previous work we have given a generic mathematical basis for the supermetric property and shown how it can improve indexing performance for a given exact search structure. Here we present a full investigation into its use within a variety of different hyperplane partition indexing structures, and go on to show some more of its flexibility by examining a search structure whose partition and exclusion conditions are tailored, at each node, to suit the individual reference points and data set present there. Among the results given, we show a new best performance for exact search using a well-known benchmark. (C) 2018 Elsevier Ltd. All rights reserved.
Source: Information systems (Oxf.) 80 (2019): 108–123. doi:10.1016/j.is.2018.01.002
Publisher: Pergamon,, Oxford , Regno Unito
[2] R. Connor, L. Vadicamo, F. A. Cardillo, F. Rabitti, Supermetric Search with the Four-Point Property, Springer International Publishing, Cham, 2016, pp. 51{64. doi:10.1007/978-3-319-46759-7{\_}4. URL http://dx.doi.org/10.1007/978-3-319-46759-7_4
[3] E. Chavez, V. Luduen~a, N. Reyes, P. Roggero, Faster proximity searching with the distal SAT, Information Systems 59 (2016) 15 { 47. doi:http://dx.doi.org/10.1016/j.is.2015.10.014.
[6] E. Chavez, G. Navarro, Metric databases, in: L. C. Rivero, J. H. Doorn, V. E. Ferraggine (Eds.), Encyclopedia of Database Technologies and Applications, Idea Group, 2005, pp. 366{371.
[7] E. Chavez, G. Navarro, R. Baeza-Yates, J. L. Marroqu n, Searching in metric spaces, ACM Comput. Surv. 33 (3) (2001) 273{321. doi: 10.1145/502807.502808. URL http://doi.acm.org/10.1145/502807.502808
[8] G. R. Hjaltason, H. Samet, Index-driven similarity search in metric spaces (survey article), ACM Trans. Database Syst. 28 (4) (2003) 517{ 580. doi:10.1145/958942.958948. URL http://doi.acm.org/10.1145/958942.958948
[9] J. K. Uhlmann, Satisfying general proximity / similarity queries with metric trees, Information Processing Letters 40 (4) (1991) 175 { 179. doi:http://dx.doi.org/10.1016/0020-0190(91)90074-R.
[10] I. Kalantari, G. McDonald, A data structure and an algorithm for the nearest point problem, IEEE Transactions on Software Engineering SE9 (5) (1983) 631{634. doi:10.1109/TSE.1983.235263.
[11] H. Noltemeier, K. Verbarg, C. Zirkelbach, Monotonous Bisector* Trees | a tool for e cient partitioning of complex scenes of geometric objects, Springer Berlin Heidelberg, Berlin, Heidelberg, 1992, pp. 186{203. doi: 10.1007/3-540-55488-2{\_}27. URL http://dx.doi.org/10.1007/3-540-55488-2_27
[12] F. Dehne, H. Noltemeier, Voronoi trees and clustering problems, Information Systems 12 (2) (1987) 171 { 175. doi:http: //dx.doi.org/10.1016/0306-4379(87)90041-X. URL http://www.sciencedirect.com/science/article/pii/ 030643798790041X
[14] G. Navarro, Searching in metric spaces by spatial approximation, The VLDB Journal 11 (1) (2002) 28{46. doi:10.1007/s007780200060.
[15] G. Navarro, N. Reyes, String Processing and Information Retrieval: 9th International Symposium, SPIRE 2002 Lisbon, Portugal, September 11{ 13, 2002 Proceedings, Springer Berlin Heidelberg, Berlin, Heidelberg, 2002, Ch. Fully Dynamic Spatial Approximation Trees, pp. 254{270. doi:10.1007/3-540-45735-6{\_}23.
[24] M. J. Huiskes, M. S. Lew, The mir ickr retrieval evaluation, in: MIR '08: Proceedings of the 2008 ACM International Conference on Multimedia Information Retrieval, ACM, New York, NY, USA, 2008.
Metrics
Back to previous page
@article{oai:it.cnr:prodotti:403045,
title = {Supermetric search},
author = {Connor R. and Vadicamo L. and Cardillo F. A. and Rabitti F.},
publisher = {Pergamon,, Oxford , Regno Unito},
doi = {10.1016/j.is.2018.01.002 and 10.48550/arxiv.1707.08361},
journal = {Information systems (Oxf.)},
volume = {80},
pages = {108–123},
year = {2019}
}
0000-0003-0940-4768ISTI Repository
DOI
10.1016/j.is.2018.01.002
10.48550/arxiv.1707.08361
arXiv.org e-Print Archive
Information Systems
www.sciencedirect.com