Scalable complex pattern search in sequential data

ABSTRACT

Searching data streams has been traditionally very limited, either in the complexity of the search or in the size of the searched dataset. In this paper, we investigate the design and optimization of constructs that enable SQL to express complex patterns. In particular we propose the RSPS (recursive sequential pattern search) algorithm which exploits the inter-dependencies between the elements of a sequential pattern to minimize repeated passes over the same data. Performance gains derived experimental results show impressive speedup up to 100 times.

REFERENCES

• 1: Knuth, D. E., Morris, J. H., and Pratt, V. R., Fast pattern matching in strings. SIAM Journal of Computing, 1977. 6(2): p. 323--350.
• 2: 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]

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, Theory

Keywords:
complex pattern search, pattern search, sql-ts, time series