Skip to main content
SpringerLink
Log in

Adapting metric indexes for searching in multi-metric spaces

  • Published:
Multimedia Tools and Applications Aims and scope Submit manuscript

Abstract

An important research issue in multimedia databases is the retrieval of similar objects. For most applications in multimedia databases, an exact search is not meaningful. Thus, much effort has been devoted to develop efficient and effective similarity search techniques. A recent approach that has been shown to improve the effectiveness of similarity search in multimedia databases resorts to the usage of combinations of metrics (i.e., a search on a multi-metric space). In this approach, the desirable contribution (weight) of each metric is chosen at query time. It follows that standard metric indexes cannot be directly used to improve the efficiency of dynamically weighted queries, because they assume that there is only one fixed distance function at indexing and query time. This paper presents a methodology for adapting metric indexes to multi-metric indexes, that is, to support similarity queries with dynamic combinations of metric functions. The adapted indexes are built with a single distance function and store partial distances to estimate the dynamically weighed distances. We present two novel indexes for multimetric space indexing, which are the result of the application of the proposed methodology.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24
Fig. 25
Fig. 26

Similar content being viewed by others

Notes

  1. This algorithm was taken from the SISAP library http://www.sisap.org

References

  1. Böhm C, Berchtold S, Keim DA (2001) Searching in high-dimensional spaces: index structures for improving the performance of multimedia databases. ACM Comput Surv 33(3):322–373. doi:http://doi.acm.org/10.1145/502807.502809

    Article  Google Scholar 

  2. Brin S (1995) Near neighbor search in large metric spaces. In: Proc. of the 21th international conference on very large data bases (VLDB’95). Morgan Kaufmann, San Mateo, CA, pp 574–584

    Google Scholar 

  3. Bustos B, Skopal T (2006) Dynamic similarity search in multi-metric spaces. In: Proc. 8th ACM SIGMM international workshop on multimedia information retrieval (MIR’06). ACM Press, pp 137–146

    Google Scholar 

  4. Bustos B, Navarro G, Chávez E (2003) Pivot selection techniques for proximity searching in metric spaces. Pattern Recogn Lett 24(14):2357–2366

    Article  MATH  Google Scholar 

  5. Bustos B, Keim D, Schreck T (2005) A pivot-based index structure for combination of feature vectors. In: Proc. 20th annual ACM symposium on applied computing, multimedia and visualization track (SAC-MV’05). ACM Press, pp 1180–1184

    Google Scholar 

  6. Bustos B, Keim D, Saupe D, Schreck T, Vranić D (2004) Automatic selection and combination of descriptors for effective 3D similarity search. In: Proc. IEEE international workshop on multimedia content-based analysis and retrieval (MCBAR’04). IEEE Computer Society Press, Los Alamitos, CA, pp 514–521

    Google Scholar 

  7. Bustos B, Keim D, Saupe D, Schreck T, Vranić D (2004) Using entropy impurity for improved 3D object similarity search. In: Proc. IEEE international conference on multimedia and expo (ICME’04). IEEE, pp 1303–1306

  8. Bustos B, Keim D, Saupe D, Schreck T, Vranić D (2006) An experimental effectiveness comparison of methods for 3D similarity search. Int J Digit Libr 6(1):39–54 (Special issue on Multimedia Contents and Management in Digital Libraries)

    Article  Google Scholar 

  9. Chávez E, Navarro G (2005) A compact space decomposition for effective metric indexing. Pattern Recogn Lett 26(9):1363–1376

    Article  Google Scholar 

  10. Chávez E, Navarro G, Baeza-Yates R, Marroquín JL (2001) Searching in metric spaces. ACM Comput Surv 33(3):273–321. doi:http://doi.acm.org/10.1145/502807.502808

    Article  Google Scholar 

  11. Ciaccia P, Patella M (2002) Searching in metric spaces with user-defined and approximate distances. ACM Trans Database Syst 27(4):398–437

    Article  Google Scholar 

  12. Ciaccia P, Patella M, Zezula P (1997) M-tree: an efficient access method for similarity search in metric spaces. In: Proc. of the 23rd international conference on very large data bases (VLDB’97). Morgan Kaufmann, San Mateo, CA, pp 426–435

    Google Scholar 

  13. Falchi F, Lucchese C, Perego R, Rabitti F (2008) CoPhIR: content-based photo image retrieval. http://cophir.isti.cnr.it/CoPhIR.pdf

  14. Hettich S, Bay SD (1999) The UCI KDD archive. http://kdd.ics.uci.edu. University of California, Department of Information and Computer Science, Irvine, CA

  15. Hjaltason GR, Samet H (1995) Ranking in spatial databases. In: Proc. of the 4th international symposium on advances in spatial databases (SSD’95). Springer, pp 83–95

  16. Hoksza D, Galgonek J (2009) Density-based classification of protein structures using iterative TM-score. In: Computational structure bioinformatics workshop (CSBW’09) (BIBM’09). IEEE

  17. Keim D (1999) Efficient geometry-based similarity search of 3D spatial databases. In: Proc. ACM international conference on management of data (SIGMOD’99). ACM Press, pp 419–430

  18. Samet H (2005) Foundations of multidimensional and metric data structures (the Morgan Kaufmann series in computer graphics and geometric modeling). Morgan Kaufmann, San Mateo, CA

    Google Scholar 

  19. Smith T, Waterman M (1981) Identification of common molecular subsequences. J Mol Biol 147(1):195–197

    Article  Google Scholar 

  20. Zezula P, Amato G, Dohnal V, Batko M (2005) Similarity search: the metric space approach (advances in database systems). Springer, New York

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Chile, Av. Blanco Encalada 2120, Santiago, Chile

    Benjamin Bustos & Sebastian Kreft

  2. Department of Software Engineering, Charles University in Prague, Malostranské nám. 25, 118 00, Prague, Czech Republic

    Tomáš Skopal

Authors
  1. Benjamin Bustos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sebastian Kreft
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tomáš Skopal
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Benjamin Bustos.

Additional information

This paper is partially funded by FONDECYT (Chile) Project 11070037 (B. Bustos and S. Kreft), CONICYT Master’s Scholarship (S. Kreft) and by Czech Science Foundation Project 201/09/0683 (T. Skopal).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bustos, B., Kreft, S. & Skopal, T. Adapting metric indexes for searching in multi-metric spaces. Multimed Tools Appl 58, 467–496 (2012). https://doi.org/10.1007/s11042-011-0731-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11042-011-0731-3

Keywords

Search

Navigation