Real-time data pre-processing technique for efficient feature extraction in large scale datasets

ABSTRACT

Due to the continuous and rampant increase in the size of domain specific data sources, there is a real and sustained need for fast processing in time-sensitive applications, such as medical record information extraction at the point of care, genetic feature extraction for personalized treatment, as well as off-line knowledge discovery such as creating evidence based medicine. Since parallel multi-string matching is at the core of most data mining tasks in these applications, faster on-line matching in static and streaming data is needed to improve the overall efficiency of such knowledge discovery. To solve this data mining need not efficiently handled by traditional information extraction and retrieval techniques, we propose a Block Suffix Shifting-based approach, which is an improvement over the state of the art multi-string matching algorithms such as Aho-Corasick, Commentz-Walter, and Wu-Manber. The strength of our approach is its ability to exploit the different block structures of domain specific data for off-line and online parallel matching. Experiments on several real world datasets show how our approach translates into significant performance improvements.

REFERENCES

• 1: ftp://genome-ftp.stanford.edu/pub/yeast/data_download/sequence/genomicsequence/chromosomes/gcg/.
• 2: http://searchenginewatch.com.
• 3: http://www.kdnuggets.com/datasets/kddcup.html.
• 4: http://www.rsc.org/.
• 5: http://www.unet.univie.ac.at/aix/cmds/aixcmds2/fgrep.htm
• 6: Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
• 7: Beate Commentz-Walter, A String Matching Algorithm Fast on the Average, Proceedings of the 6th Colloquium, on Automata, Languages and Programming, p.118-132, July 16-20, 1979
• 8: 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]
• 9: Chia-Hui Chang , Shao-Chen Lui, IEPAD: information extraction based on pattern discovery, Proceedings of the 10th international conference on World Wide Web, p.681-688, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372182]
• 10: Jinlin Chen , Terry Cook, Mining contiguous sequential patterns from web logs, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242753]
• 11: Hung Chim , Xiaotie Deng, A new suffix tree similarity measure for document clustering, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242590]
• 12: Anthony Don , Elena Zheleva , Machon Gregory , Sureyya Tarkan , Loretta Auvil , Tanya Clement , Ben Shneiderman , Catherine Plaisant, Discovering interesting usage patterns in text collections: integrating text mining with visualization, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321473]
• 13: V. P. Donald Knuth; James H. Morris, Jr. Fast pattern matching in strings. In SIAM Journal on Computing, pages 323--350, 1977.
• 14: Kimmo Fredriksson, On-line Approximate String Matching in Natural Language, Fundamenta Informaticae, v.72 n.4, p.453-466, June 2006
• 15: Vassil Gedov , Carsten Stolz , Ralph Neuneier , Michal Skubacz , Dietmar Seipel, Matching web site structure and content, 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.1013438]
• 16: Stefan Kals , Engin Kirda , Christopher Kruegel , Nenad Jovanovic, SecuBat: a web vulnerability scanner, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135817]
• 17: S. Kim and Y. Kim. A fast multiple string-pattern matching algorithm. In Proc. of 17th AoM/IAoM Conference on Computer Science, Aug. 1999.
• 18: Y. Liu, L. V. Lita, S. Niculescu, P. Mitra, and C. L. Giles. Finding a haystack in haystacks - simultaneous identificcation ofconcepts in large bio-medical corpora. SIAM SDM 2008.
• 19: U. Manber. Agrep, an approximate grep. In http://www.tgries.de/agrep/, 2005.
• 20: Alexandros Ntoulas , Marc Najork , Mark Manasse , Dennis Fetterly, Detecting spam web pages through content analysis, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135794]
• 21: Martin Roesch, Snort - Lightweight Intrusion Detection for Networks, Proceedings of the 13th USENIX conference on System administration, November 07-12, 1999, Seattle, Washington
• 22: U. M. Sun Wu. A fast algorithm for multi-pattern searching. In Technical Report TR 94-17, University of Arizona at Tuscon, May 1994.
• 23: Wen-tau Yih , Joshua Goodman , Vitor R. Carvalho, Finding advertising keywords on web pages, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135813]
• 24: B. W. Watson and R. E. Watson. A new family of string pattern matching algorithms. South African Computer Journal, 30:34--41, 2003.
• 25: S. Wu and U. Manber. Fast text searching with errors. Technical Report TR-91-11, 1991.

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

Keywords:
block suffix shift, feature extraction, multiple-pattern matching, pre-processing