A novel optimization approach to efficiently process aggregate similarity queries in metric access methods

ABSTRACT

A similarity query considers an element as the query center and searches a dataset to find either the elements far up to a bounding radius or the k nearest ones from the query center. Several algorithms have been developed to efficiently execute similarity queries. However, there are queries that require more than one center, which we call Aggregate Similarity Queries. Such queries appear when the user gives multiple desirable examples, and requests data elements that are similar to all of the examples, as in the case of applying relevance feedback. Here we give the first algorithms that can handle aggregate similarity queries on Metric Access Methods (MAM) such as the M-tree and Slim-tree. Our method, which we call Metric Aggregate Similarity Search (MASS) has the following properties: (a) it requires only the triangle inequality property; (b) it guarantees no false-dismissals, as we prove that it lower-bounds the aggregate distance scores; (c) it can work with any MAM; (d) it can handle any number of query centers, which are either scattered all over the space or concentrated on a restricted region. Experiments on both real and synthetic data show that our method scales on both the number of elements and, if the dataset is in a spatial domain, also on its dimensionality. Moreover, it achieves better results than previous related methods.

REFERENCES

• 1: A. Asuncion and D. J. Newman. UCI machine learning repository, 2007. University of California, Irvine, http://archive.ics.uci.edu/ml/.
• 2: 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
• 3: Jan-Mark Geusebroek , Gertjan J. Burghouts , Arnold W. M. Smeulders, The Amsterdam Library of Object Images, International Journal of Computer Vision, v.61 n.1, p.103-112, January 2005 [doi>10.1023/B:VISI.0000042993.50813.60]
• 4: Gisli R. Hjaltason , Hanan Samet, Ranking in Spatial Databases, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.83-95, August 06-09, 1995
• 5: Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999 [doi>10.1145/320248.320255]
• 6: Flip Korn , Nikolaos Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas, Fast Nearest Neighbor Search in Medical Image Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.215-226, September 03-06, 1996
• 7: Dimitris Papadias , Yufei Tao , Kyriakos Mouratidis , Chun Kit Hui, Aggregate nearest neighbor queries in spatial databases, ACM Transactions on Database Systems (TODS), v.30 n.2, p.529-576, June 2005 [doi>10.1145/1071610.1071616]
• 8: Humberto L. Razente , Maria Camila N. Barioni , Agma J. M. Traina , Caetano Traina, Jr., Aggregate similarity queries in relevance feedback methods for content-based image retrieval, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil [doi>10.1145/1363686.1363887]
• 9: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 10: Hanan Samet, Depth-First K-Nearest Neighbor Finding Using the MaxNearestDist Estimator, Proceedings of the 12th International Conference on Image Analysis and Processing, p.486, September 17-19, 2003
• 11: Thomas Seidl , Hans-Peter Kriegel, Optimal multi-step k-nearest neighbor search, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.154-165, June 01-04, 1998, Seattle, Washington, United States
• 12: Improvements in Distance-Based Indexing, Proceedings of the 16th International Conference on Scientific and Statistical Database Management, p.161, June 21-23, 2004 [doi>10.1109/SSDBM.2004.42]
• 13: C. Traina, Jr. , A. Traina , C. Faloutsos , B. Seeger, Fast Indexing and Visualization of Metric Data Sets using Slim-Trees, IEEE Transactions on Knowledge and Data Engineering, v.14 n.2, p.244-260, March 2002 [doi>10.1109/69.991715]
• 14: Leejay Wu , Christos Faloutsos , Katia P. Sycara , Terry R. Payne, FALCON: Feedback Adaptive Loop for Content-Based Retrieval, Proceedings of the 26th International Conference on Very Large Data Bases, p.297-306, September 10-14, 2000
• 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.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Performance

Keywords:
access methods, aggregate dissimilarity, similarity queries