A Bloom filter based semi‐index on q‐grams
Szymon Grabowski, Robert Susik, Marcin Raniszewski · Software Practice and Experience · 2016
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.