Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

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

Action:

login to update

Options:








Author, Editor

Author(s):

Kärkkäinen, Juha

dblp



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

URL of the conference:

http://www.cs.utu.fi/swat2002/

URL for downloading the paper:

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
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
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section