Efficient processing of complex similarity queries in RDBMS through query rewriting

ABSTRACT

Multimedia and complex data are usually queried by similarity predicates. Whereas there are many works dealing with algorithms to answer basic similarity predicates, there are not generic algorithms able to efficiently handle similarity complex queries combining several basic similarity predicates. In this work we propose a simple and effective set of algorithms that can be combined to answer complex similarity queries, and a set of algebraic rules useful to rewrite similarity query expressions into an adequate format for those algorithms. Those rules and algorithms allow relational database management systems to turn complex queries into efficient query execution plans. We present experiments that highlight interesting scenarios. They show that the proposed algorithms are orders of magnitude faster than the traditional similarity algorithms. Moreover, they are linearly scalable considering the database size.

REFERENCES

• 1: Stefan Berchtold , Christian Böhm , Bernhard Braunmüller , Daniel A. Keim , Hans-Peter Kriegel, Fast parallel similarity search in multimedia databases, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.1-12, May 11-15, 1997, Tucson, Arizona, United States
• 2: C. Böhm, B. Braunmüller, and H.-P. Kriegel. The pruning power: Theory and heuristics for mining databases with multiple k-nearest-neighbor queries. In Int. Conf. on DaWaK, pages 244--257, 2000.
• 3: Klemens Böhm , Michael Mlivoncic , Hans-Jörg Schek , Roger Weber, Fast Evaluation Techniques for Complex Similarity Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.211-220, September 11-14, 2001
• 4: Efficiently Supporting Multiple Similarity Queries for Mining in Metric Databases, Proceedings of the 16th International Conference on Data Engineering, p.256, February 28-March 03, 2000
• 5: Kevin Chen-Chuan Chang , Seung-won Hwang, Minimal probing: supporting expensive predicates for top-k queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564731]
• 6: Surajit Chaudhuri , Prasanna Ganesan , Sunita Sarawagi, Factorizing complex predicates in queries to exploit indexes, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872802]
• 7: Surajit Chaudhuri , Luis Gravano, Optimizing queries over multimedia repositories, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.91-102, June 04-06, 1996, Montreal, Quebec, Canada
• 8: Surajit Chaudhuri , Kyuseok Shim, Optimization of queries with user-defined predicates, ACM Transactions on Database Systems (TODS), v.24 n.2, p.177-228, June 1999 [doi>10.1145/320248.320249]
• 9: 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
• 10: Paolo Ciaccia , Marco Patella , Pavel Zezula, Processing Complex Similarity Queries with Distance-Based Access Methods, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.9-23, March 23-27, 1998
• 11: 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]
• 12: A. Kemper , G. Moerkotte , K. Peithner , M. Steinbrunn, Optimizing disjunctive queries with expensive predicates, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.336-347, May 24-27, 1994, Minneapolis, Minnesota, United States
• 13: 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
• 14: Nikos Mamoulis , Dimitris Papadias , Dinos Arkoumanis, Complex Spatial Query Processing, Geoinformatica, v.8 n.4, p.311-346, December 2004 [doi>10.1023/B:GEIN.0000040830.73424.f0]
• 15: C. Mohan , Donald J. Haderle , Yun Wang , Josephine M. Cheng, Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.29-43, March 26-30, 1990
• 16: Kriengkrai Porkaew , Sharad Mehrotra , Michael Ortega, Query Reformulation for Content Based Multimedia Retrieval in MARS, Proceedings of the IEEE International Conference on Multimedia Computing and Systems Volume II-Volume 2, p.747, June 07-11, 1999
• 17: 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
• 18: 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
• 19: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 20: Improvements in Distance-Based Indexing, Proceedings of the 16th International Conference on Scientific and Statistical Database Management (SSDBM'04), p.161, June 21-23, 2004 [doi>10.1109/SSDBM.2004.42]
• 21: A. J. M. Traina , C. Traina , J. M. Bueno , F. J. T. Chino , P. Azevedo-Marques, Efficient Content-Based Image Retrieval through Metric Histograms, World Wide Web, v.6 n.2, p.157-185, June 2003 [doi>10.1023/A:1023670521530]
• 22: 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 ]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Theory

Keywords:
query rewriting, similarity predicates