Please note that eDoc will be permanently shut down in the first quarter of 2021!      Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents



ID: 202073.0, MPI für Informatik / Algorithms and Complexity Group
One-Gapped q-Gram Filters for Levenshtein Distance
Authors:Burkhardt, Stefan; Kärkkäinen, Juha
Editors:Apostolico, Alberto; Takeda, Masayuki
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2002
Title of Proceedings:Combinatorial Pattern Matching : 13th Annual Symposium, CPM 2002
Start Page:225
End Page:234
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Fukuoka, Japan
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
2002-07-03
Review Status:not specified
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2003-09-08
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:ISBN:3-540-43862-9
LOCALID:C1256428004B93B8-E631B996E8179208C1256CA2005D83B6-...
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.