Dynamic similarity search in multi-metric spaces

ABSTRACT

An important research issue in multimedia databases is the retrieval of similar objects. For most applications in multi-media 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 where the desirable contribution (weight) of each metric is chosen at query time. This paper presents the Multi-Metric M-tree (M 3 -tree), a metric access method that supports similarity queries with dynamic combinations of metric functions. The M 3-tree, an extension of the M-tree, stores partial distances to better estimate the weighed distances between routing/ground entries and each query, where a single distance function is used to build the whole index. An experimental evaluation shows that the M 3-tree may be as efficient as having multiple M-trees (one for each).

REFERENCES

• 1: Christian Böhm , Stefan Berchtold , Daniel A. Keim, Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases, ACM Computing Surveys (CSUR), v.33 n.3, p.322-373, September 2001 [doi>10.1145/502807.502809]
• 2: Benjamin Bustos , Daniel Keim , Dietmar Saupe , Tobias Schreck , Dejan Vranic, Automatic Selection and Combination of Descriptors for Effective 3D Similarity Search, Proceedings of the IEEE Sixth International Symposium on Multimedia Software Engineering (ISMSE'04), p.514-521, December 13-15, 2004
• 3: B. Bustos, D. Keim, D. Saupe, T. Schreck, and D. Vranić. Using entropy impurity for improved 3D object similarity search. In Proc. IEEE International Conference on Multimedia and Expo (ICME'04), pages 1303--1306. IEEE, 2004.
• 4: B. Bustos, D. Keim, D. Saupe, T. Schreck, and D. Vranić. An experimental effectiveness comparison of methods for 3D similarity search. Intl. Journal on Digital Libraries, 6(1):39--54, 2006.
• 5: Benjamin Bustos , Daniel Keim , Tobias Schreck, A pivot-based index structure for combination of feature vectors, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066945]
• 6: Edgar Chávez , Gonzalo Navarro , Ricardo Baeza-Yates , José Luis Marroquín, Searching in metric spaces, ACM Computing Surveys (CSUR), v.33 n.3, p.273-321, September 2001 [doi>10.1145/502807.502808]
• 7: Paolo Ciaccia , Marco Patella, Searching in metric spaces with user-defined and approximate distances, ACM Transactions on Database Systems (TODS), v.27 n.4, p.398-437, December 2002 [doi>10.1145/582410.582412]
• 8: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 9: Arjen P. de Vries , Nikos Mamoulis , Niels Nes , Martin Kersten, Efficient k-NN search on vertically decomposed data, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564729]
• 10: S. Hettich and S. Bay. The UCI KDD archive {http://kdd.ics.uci.edu}, 1999.
• 11: Daniel A. Keim, Efficient geometry-based similarity search of 3D spatial databases, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.419-430, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 12: T. Skopal. On fast non-metric similarity search by metric access methods. In Proc. 10th International Conference on Extending Database Technology (EDBT'06), LNCS 3896, pages 718--736. Springer, 2006.
• 13: T. Skopal, J. Pokorný, M. Krátký, and V. Snášel. Revisiting M-tree building principles. In Proc. 7th East European Conference on Advances in Databases and Information Systems (ADBIS'03), LNCS 2798, pages 148--162. Springer, 2003.
• 14: T. Skopal, J. Pokorný, and V. Snášel. Nearest neighbours search using the PM-tree. In Proc. 10th International Conference on Database Systems for Advanced Applications (DASFAA'05), LNCS 3453, pages 803--815. Springer, 2005.
• 15: Pavel Zezula , Giuseppe Amato , Vlastislav Dohnal , Michal Batko, Similarity Search: The Metric Space Approach (Advances in Database Systems), Springer-Verlag New York, Inc., Secaucus, NJ, 2005

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Design, Performance

Keywords:
combination of metric functions, content-based indexing and retrieval, nearest neighbor queries