Non-contiguous sequence pattern queries

Nikos Mamoulis, Man Lung Yiu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

5 Citations (Scopus)


Non-contiguous subsequence pattern queries search for symbol instances in a long sequence that satisfy some soft temporal constraints. In this paper, we propose a methodology that indexes long sequences, in order to efficiently process such queries. The sequence data are decomposed into tables and queries are evaluated as multiway joins between them. We describe non-blocking join operators and provide query preprocessing and optimization techniques that tighten the join predicates and suggest a good join order plan. As opposed to previous approaches, our method can efficiently handle a broader range of queries and can be easily supported by existing DBMS. Its efficiency is evaluated by experimentation on synthetic and real data.
Original languageEnglish
Pages (from-to)783-800
Number of pages18
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publication statusPublished - 1 Dec 2004
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Non-contiguous sequence pattern queries'. Together they form a unique fingerprint.

Cite this