Digital Symposium Collection 2000

Window-Accumulated Subsequence Matching Problem is Linear Luc Boasson, Patrick Cegielski, Irène Guessarian, and Yuri Matiyasevich   View Paper (PDF)   Return to Indexing Abstract Given two strings, text t of length n, and pattern p = p1 . . . pk of length k, and given a natural number w, the subsequence matching problem consists in finding the number of size w windows of text t which contain pattern p as a subsequence, i.e. the letters p1,. . . ,pk occur in the window, in the same order as in p, but not necessarily consecutively (they may be interleaved with other letters). Subsequence matching is used for finding frequent patterns and association rules in databases. We generalize the Knuth- Morris-Pratt (KMP) pattern matching algorithm; we define a non-conventional kind of RAM, the MP-RAMS which model more closely the microprocessor operations; we design an O(n) on-line algorithm for solving the subsequence matching problem on MP- RAMS. References Note: References link to DBLP on the Web. [A90] ... [AHU74] Alfred V. Aho , John E. Hopcroft , Jeffrey D. Ullman : The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6 [BYG92] Ricardo A. Baeza-Yates , Gaston H. Gonnet : A New Approach to Text Searching. CACM 35(10) : 74-82(1992) [BYN96] Ricardo A. Baeza-Yates , Gonzalo Navarro : A Faster Algorithm for Approximate String Matching. CPM 1996 : 1-23 [BG95] Amir M. Ben-Amram , Zvi Galil : On the Power of the Shift Instruction. Information and Computation 117(1) : 19-36(1995) [C71] ... [C88] Maxime Crochemore : String Matching with Constraints. MFCS 1988 : 44-58 [DFGGK97] Gautam Das , Rudolf Fleischer , Leszek Gasieniec , Dimitrios Gunopulos , Juha Kärkkäinen : Episode Matching. CPM 1997 : 12-27 [G81] Zvi Galil : String Matching in Real Time. JACM 28(1) : 134-149(1981) [KMP77] Donald E. Knuth , James H. Morris Jr. , Vaughan R. Pratt : Fast Pattern Matching in Strings. SIAM J. Comput. 6(2) : 323-350(1977) [KR97] Gregory Kucherov , Michaël Rusinowitch : Matching a Set of Strings with Variable Length don't Cares. TCS 178(1-2) : 129-154(1997) [MBY91] Udi Manber , Ricardo A. Baeza-Yates : An Algorithm for String Matching with a Sequence of don't Cares. IPL 37(3) : 133-136(1991) [M97] Heikki Mannila : Methods and Problems in Data Mining. ICDT 1997 : 41-55 [MTV95] Heikki Mannila , Hannu Toivonen , A. Inkeri Verkamo : Discovering Frequent Episodes in Sequences. KDD 1995 : 210-215 [Ma71] ... [PRS74] Vaughan R. Pratt , Michael O. Rabin , Larry J. Stockmeyer : A Characterization of the Power of Vector Machines. STOC 1974 : 122-134 [S71] A. O. Slisenko : String-Matching in Real Time: Some Properties of the Data Structure. MFCS 1978 : 493-496 [TRL92] Jerry L. Trahan , Michael C. Loui , Vijaya Ramachandran : Multiplication, Division and Shift Instructions in Parallel Random Access Machines. TCS 100(1) : 1-44(1992) [U95] Esko Ukkonen : On-Line Construction of Suffix Trees. Algorithmica 14(3) : 249-260(1995) [WM92] Sun Wu , Udi Manber : Fast Text Searching Allowing Errors. CACM 35(10) : 83-91(1992) BIBTEX @inproceedings{DBLP:conf/pods/BoassonCGM99,   author    = {Luc Boasson and                 Patrick Cegielski and                 Ir{\`e}ne Guessarian and                 Yuri Matiyasevich},    title     = {Window-Accumulated Subsequence Matching Problem is Linear},    booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium                 on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,                 Pennsylvania},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-062-7},    pages     = {327-336},    crossref  = {DBLP:conf/pods/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM