A Bloom filter based semi‐index on q‐grams. (24th August 2016)

• Record Type: Journal Article
• Authors: Grabowski, Szymon; Susik, Robert; Raniszewski, Marcin
• Is Part Of: Software, practice & experience. Volume 47:Number 6(2017)
• Page Start: 799
• Page End: 811
• Publication Date: 2016-08-24
• Subjects: text indexing -- q‐grams -- Bloom filter -- minimizers; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2431
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: We present a simple q ‐gram based semi‐index, which allows to look for a pattern typically only in a small fraction of text blocks. Several space‐time tradeoffs are presented. Experiments on Pizza & Chili datasets show that our solution is up to three orders of magnitude faster than the Claude et al. (Journal of Discrete Algorithms 2012;11 :37) semi‐index at a comparable space usage. Moreover, the construction of our data structure is fast and easily parallelizable. Copyright © 2016 John Wiley & Sons, Ltd.