Efficient evaluation of parameterized pattern queries

ABSTRACT

Many applications rely on sequence databases and use extensively pattern-matching queries to retrieve data of interest. This paper extends the traditional pattern-matching expressions to parameterized patterns, featuring variables. Parameterized patterns are more expressive and allow to define concisely regular expressions that would be very complex to describe without variables. They can also be used to express additional constraints on patterns' variables.We show that they can be evaluated without additional cost with respect to traditional techniques (e.g., the Knuth-Morris-Pratt algorithm). We describe an algorithm that enjoys low memory and CPU time requirements, and provide experimental results which illustrate the gain of the optimized solution.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 2: Alberto Apostolico , Raffaele Giancarlo, The Boyer Moore Galil string searching strategies revisited, SIAM Journal on Computing, v.15 n.1, p.98-105, Feb. 1986 [doi>10.1137/0215007]
• 3: Brenda S. Baker, Parameterized pattern matching by Boyer-Moore-type algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.541-550, January 22-24, 1995, San Francisco, California, United States
• 4: Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
• 5: M. Crochemore, A. Czumaj, L. Gasieniec, T. Lecroq, W. Plandowski, and W. Rytter. Fast practical multi-pattern matching. Inf. Process. Lett., 71(3-4):107--113, 1999.
• 6: Maxime Crochemore , Wojciech Rytter, Text algorithms, Oxford University Press, Inc., New York, NY, 1994
• 7: Multi-scale Classification of Moving Objects Trajectories, Proceedings of the 16th International Conference on Scientific and Statistical Database Management (SSDBM'04), p.307, June 21-23, 2004 [doi>10.1109/SSDBM.2004.55]
• 8: Cédric Mouza , Philippe Rigaux, Mobility Patterns, Geoinformatica, v.9 n.4, p.297-319, December 2005 [doi>10.1007/s10707-005-4574-9]
• 9: C. I. Ezeife and M. Chen. Mining Web Sequential Patterns Incrementally with Revised PLWAP Tree. In WAIM, pages 539--548, 2004.
• 10: Dina Q. Goldin , Paris C. Kanellakis, On Similarity Queries for Time-Series Data: Constraint Specification and Implementation, Proceedings of the First International Conference on Principles and Practice of Constraint Programming, p.137-153, September 19-22, 1995
• 11: Sang-Wook Kim , Jeehee Yoon , Sanghyun Park , Tae-Hoon Kim, Shape-based retrieval of similar subsequences in time-series databases, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain [doi>10.1145/508791.508874]
• 12: D. Knuth, J. Morris, and V. Pratt. Fast Pattern Matching in Strings. SIAM J. Computing, 6(2):323--350, 1977.
• 13: Gad M. Landau , Uzi Vishkin, Fast string matching with k-differences, Journal of Computer and System Sciences, v.37 n.1, p.63-78, August 1988 [doi>10.1016/0022-0000(88)90045-1]
• 14: Y.-N. Law, H. Wang, and C. Zaniolo. Query Languages and Data Models for Database Sequences and Data Streams. In Proc. Intl. Conf. on Very Large Data Bases (VLDB), pages 492--503, 2004.
• 15: Hua-Fu Li , Suh-Yin Lee , Man-Kwan Shan, On mining webclick streams for path traversal patterns, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013497]
• 16: Nikos Mamoulis , Huiping Cao , George Kollios , Marios Hadjieleftheriou , Yufei Tao , David W. Cheung, Mining, indexing, and querying historical spatiotemporal data, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014080]
• 17: D. W. Mount. Bioinformatics Sequence and Genome Analysis, Second Edition. CSHL Press, 2004.
• 18: Raghu Ramakrishnan , Donko Donjerkovic , Arvind Ranganathan , Kevin S. Beyer , Muralidhar Krishnaprasad, SRQL: Sorted Relational Query Language, Proceedings of the 10th International Conference on Scientific and Statistical Database Management, p.84-95, July 01-03, 1998 [doi>10.1109/SSDM.1998.688114]
• 19: Reza Sadri , Carlo Zaniolo , Amir Zarkesh , Jafar Adibi, Expressing and optimizing sequence queries in database systems, ACM Transactions on Database Systems (TODS), v.29 n.2, p.282-318, June 2004 [doi>10.1145/1005566.1005568]
• 20: Reza Sadri , Carlo Zaniolo , Amir Zarkesh , Jafar Adibi, Optimization of sequence queries in database systems, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.71-81, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375563]
• 21: Praveen Seshadri , Miron Livny , Raghu Ramakrishnan, SEQ: A Model for Sequence Databases, Proceedings of the Eleventh International Conference on Data Engineering, p.232-239, March 06-10, 1995
• 22: Imre Simon, String Matching Algorithms and Automata, Proceedings of the Colloquium in Honor of Arto Salomaa on Results and Trends in Theoretical Computer Science, p.386-395, June 10-11, 1994
• 23: A. Prasad Sistla , Tao Hu , Vikas Chowdhry, Similarity based retrieval from sequence databases using automata as queries, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584833]
• 24: E. Ukkonen. Finding approximate patterns in strings. J. Algorithms, 6(1):132--137, 1985.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

General Terms:
Languages, Performance

Keywords:
parameterized patterns, query evaluation