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):

Burkhardt, Stefan
Kärkkäinen, Juha

dblp
dblp



Editor(s):

Apostolico, Alberto
Takeda, Masayuki

dblp
dblp

Not MPII Editor(s):

Takeda, Masayuki

BibTeX cite key*:

Burkhardt2002

Title, Booktitle

Title*:

One-Gapped q-Gram Filters for Levenshtein Distance

Booktitle*:

Combinatorial Pattern Matching : 13th Annual Symposium, CPM 2002

Event, URLs

URL of the conference:

http://www.i.kyushu-u.ac.jp/cpm2002/

URL for downloading the paper:

http://www.mpi-sb.mpg.de/~stburk/PAPERS/cpm_02.ps

Event Address*:

Fukuoka, Japan

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:

2373

Number:


Month:

July

Pages:

225-234

Year*:

2002

VG Wort Pages:


ISBN/ISSN:

3-540-43862-9

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

We have recently shown that $q$-gram filters based on gapped $q$-grams
instead of the usual contiguous $q$-grams can provide orders of
magnitude faster and/or more efficient filtering for the Hamming
distance. In this paper, we extend the results for the Levenshtein
distance, which is more problematic for gapped $q$-grams because an
insertion or deletion in a gap affects a $q$-gram while a
replacement does not. To keep this effect under control, we
concentrate on gapped $q$-grams with just one gap. We demostrate with
experiments that the resulting filters provide a significant
improvement over the contiguous $q$-gram filters. We also develop new
techniques for dealing with complex $q$-gram filters.

Keywords:

Approximate String Matching, Filter Algorithms, Gapped q-Grams, Levenshtein Distance



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{Burkhardt2002,
AUTHOR = {Burkhardt, Stefan and K{\"a}rkk{\"a}inen, Juha},
EDITOR = {Apostolico, Alberto and Takeda, Masayuki},
TITLE = {One-Gapped q-Gram Filters for {L}evenshtein Distance},
BOOKTITLE = {Combinatorial Pattern Matching : 13th Annual Symposium, CPM 2002},
PUBLISHER = {Springer},
YEAR = {2002},
VOLUME = {2373},
PAGES = {225--234},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Fukuoka, Japan},
MONTH = {July},
ISBN = {3-540-43862-9},
}


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)
Stefan Burkhardt
Created
01/02/2003 06:01:25 PM
Revisions
8.
7.
6.
5.
4.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
08.09.2003 16:42:52
08.09.2003 16:42:08
08.09.2003 16:40:40
27.08.2003 14:51:45
09.05.2003 15:11:26
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section