CIKM'05 (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.
Retourner à la liste des publications.