English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  One-Gapped q-Gram Filters for Levenshtein Distance

Burkhardt, S., & Kärkkäinen, J. (2002). One-Gapped q-Gram Filters for Levenshtein Distance. In Combinatorial Pattern Matching: 13th Annual Symposium, CPM 2002 (pp. 225-234). Berlin, Germany: Springer.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-300B-B Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-300E-5
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Burkhardt, Stefan1, Author           
Kärkkäinen, Juha1, Author           
Apostolico, Alberto2, Editor
Takeda, Masayuki, Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2Max Planck Society, ou_persistent13              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2003-09-082002
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 202073
Other: Local-ID: C1256428004B93B8-E631B996E8179208C1256CA2005D83B6-Burkhardt2002
 Degree: -

Event

show
hide
Title: CPM 2002
Place of Event: Fukuoka, Japan
Start-/End Date: 2002-07-03 - 2002-07-05

Legal Case

show

Project information

show

Source 1

show
hide
Title: Combinatorial Pattern Matching : 13th Annual Symposium, CPM 2002
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 225 - 234 Identifier: ISBN: 3-540-43862-9

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 2373 Sequence Number: - Start / End Page: - Identifier: -