Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Burkhardt, Stefan
Kärkkäinen, Juha

dblp
dblp



BibTeX cite key*:

BurkhardtKarkkainen2003

Title

Title*:

Better Filtering with Gapped q-Grams

Journal

Journal Title*:

Fundamenta Informaticae

Journal's URL:

http://fi.mimuw.edu.pl/

Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

IOS

Publisher's URL:

http://www.iospress.nl/

Publisher's
Address:

Amsterdam, The Netherlands

ISSN:

0169-2968

Vol, No, pp, Date

Volume*:

56

Number:

1-2

Publishing Date:

2003

Pages*:

51-70

Number of
VG Pages:

20

Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

A popular and well-studied class of filters for approximate string
matching compares substrings of length $q$, \emph{the $q$-grams}, in
the pattern and the text to identify text areas that contain potential
matches. A generalization of the method that uses {\em gapped}
$q$-grams instead of contiguous substrings is mentioned a few times in
literature but has never been analyzed in any depth. In this paper,
we report the first results of a study on gapped $q$-grams. We show
that gapped $q$-grams can provide orders of magnitude faster and/or
more efficient filtering than contiguous $q$-grams. To achieve these
results the arrangement of the gaps in the $q$-gram and a filter
parameter called \emph{threshold} have to be optimized. Both of these
tasks are nontrivial combinatorial optimization problems for which we
present efficient solutions. We concentrate on the $k$~mismatches
problem, i.e, approximate string matching with the Hamming distance.

URL for the Abstract:


Categories,
Keywords:

approximate string matching, filter algorithm, gapped q-grams, k mismatches problem

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{BurkhardtKarkkainen2003,
AUTHOR = {Burkhardt, Stefan and K{\"a}rkk{\"a}inen, Juha},
TITLE = {Better Filtering with Gapped q-Grams},
JOURNAL = {Fundamenta Informaticae},
PUBLISHER = {IOS},
YEAR = {2003},
NUMBER = {1-2},
VOLUME = {56},
PAGES = {51--70},
ADDRESS = {Amsterdam, The Netherlands},
ISBN = {0169-2968},
}


Entry last modified by Christine Kiesel, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Juha Kaerkkainen
Created
04/15/2003 04:56:54 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Christine Kiesel
Christine Kiesel
Uwe Brahm
Christine Kiesel
Christine Kiesel
Edit Dates
30.05.2005 16:40:57
30.05.2005 16:40:24
08/06/2004 10:23:38 PM
15.06.2004 18:01:53
09.06.2004 17:13:31