MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Kärkkäinen, Juhadblp
Editor(s):
Penttonen, Martti
Meineche Schmidt, Erik
dblp
dblp
Not MPII Editor(s):
Penttonen, Martti
Meineche Schmidt, Erik
BibTeX cite key*:
Karkkainen2002
Title, Booktitle
Title*:
Computing the threshold for q-gram filters
Booktitle*:
Algorithm theory, SWAT 2002 : 8th Scandinavian Workshop on Algorithm Theory
Event, URLs
Conference URL::
http://www.cs.utu.fi/swat2002/
Downloading URL:
http://link.springer.de/link/service/series/0558/papers/2368/23680348.pdf
Event Address*:
Turku, Finland
Language:
English
Event Date*
(no longer used):
-- July 3-5, 2002
Organization:
Event Start Date:
3 July 2002
Event End Date:
5 July 2002
Publisher
Name*:
Springer
URL:
http://www.springer.de/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
2368
Number:
Month:
July
Pages:
348-357
Year*:
2002
VG Wort Pages:
ISBN/ISSN:
3-540-43866-1
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
A popular and much studied class of filters for approximate string
matching is based on finding common $q$-grams, substrings of length
$q$, between the pattern and the text. A variation of the basic idea uses
\emph{gapped} $q$-grams and has been recently shown to provide
significant improvements in practice. A major difficulty with gapped
$q$-gram filters is the computation of the so-called \emph{threshold}
which defines the filter criterium. We describe the first general
method for computing the threshold for $q$-gram filters. The method is
based on a carefully chosen precise statement of the problem which is
then transformed into a constrained shortest path problem.
In its generic form the method leaves certain parts open
but is applicable to a large variety of $q$-gram filters and may be
extensible even to other classes of filters. We also give a full
algorithm for a specific subclass. For this subclass, the algorithm
has been implemented and used succesfully in an experimental
comparison.
Keywords:
approximate string matching, filter algorithm, gapped q-grams, constrained shortest paths
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Karkkainen2002,
AUTHOR = {K{\"a}rkk{\"a}inen, Juha},
EDITOR = {Penttonen, Martti and Meineche Schmidt, Erik},
TITLE = {Computing the threshold for q-gram filters},
BOOKTITLE = {Algorithm theory, SWAT 2002 : 8th Scandinavian Workshop on Algorithm Theory},
PUBLISHER = {Springer},
YEAR = {2002},
VOLUME = {2368},
PAGES = {348--357},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Turku, Finland},
MONTH = {July},
ISBN = {3-540-43866-1},
}


Entry last modified by Christine Kiesel, 03/02/2010
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
03/10/2003 08:44:54 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Juha Kaerkkainen
Juha Kaerkkainen
Edit Dates
27.08.2003 14:40:12
27.08.2003 14:38:28
27.08.2003 14:18:19
03/10/2003 08:46:19 PM
03/10/2003 08:44:54 PM