{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T09:17:27Z","timestamp":1649063847767},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,12]]},"abstract":"<jats:p> Recently, there has been a surge of interest in gapped q-gram filters for approximate string matching. Important design parameters for filters are for example the value of q, the filter-threshold and in particular the shape (aka seed) of the filter. A good choice of parameters can improve the performance of a q-gram filter by orders of magnitude and optimizing these parameters is a nontrivial combinatorial problem. We describe a new method for analyzing gapped q-gram filters. This method is simple and generic. It applies to a variety of filters, overcomes many restrictions that are present in existing algorithms and can easily be extended to new filter variants. To implement our approach, we use an extended version of BDDs (Binary Decision Diagrams), a data structure that efficiently represents sets of bit-strings. In a second step, we define a new class of multi-shape filters and analyze these filters with the BDD-based approach. Experiments show that multi-shape filters can outperform the best single-shape filters, which are currently in use, in many aspects. The BDD-based algorithm is crucial for the design and analysis of these new and better multi-shape filters. Our results apply to the k-mismatches problem, i.e. approximate string matching with Hamming distance. <\/jats:p>","DOI":"10.1142\/s0129054105003698","type":"journal-article","created":{"date-parts":[[2005,12,2]],"date-time":"2005-12-02T11:54:25Z","timestamp":1133524465000},"page":"1121-1134","source":"Crossref","is-referenced-by-count":2,"title":["BDD-BASED ANALYSIS OF GAPPED q-GRAM FILTERS"],"prefix":"10.1142","volume":"16","author":[{"given":"MARC","family":"FONTAINE","sequence":"first","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Stuhlsatzenhausweg 85, 66123 Saarbr\u00fccken, Germany"}]},{"given":"STEFAN","family":"BURKHARDT","sequence":"additional","affiliation":[{"name":"Google Inc, 1600 Amphitheatre Parkway, 94043 Mountain View, CA, USA"}]},{"given":"JUHA","family":"K\u00c4RKK\u00c4INEN","sequence":"additional","affiliation":[{"name":"Department of Computer Science, P.O. Box 68 (Gustaf H\u00e4llstr\u00f6min katu 2 B), FI-00014 University of Helsinki, Finland"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf3","first-page":"677","volume":"35","author":"Bryant R. E.","journal-title":"IEEE Transactions on Computers"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1145\/136035.136043"},{"key":"rf7","first-page":"51","volume":"56","author":"Burkhardt S.","journal-title":"Fundamenta Informaticae"},{"key":"rf9","first-page":"1054","volume":"20","author":"Choi K. P.","journal-title":"Bioinformatics"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.04.002"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00382-2"},{"key":"rf14","author":"Li M.","journal-title":"Journal of Bioinformatics and Computational Biology"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/18.3.440"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003698","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:29:06Z","timestamp":1565191746000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003698"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12]]},"references-count":8,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,12]]}},"alternative-id":["10.1142\/S0129054105003698"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003698","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12]]}}}