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: 202062.0, MPI für Informatik / Algorithms and Complexity Group
Computing the threshold for q-gram filters
Authors:Kärkkäinen, Juha
Editors:Penttonen, Martti; Meineche Schmidt, Erik
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2002
Title of Proceedings:Algorithm theory, SWAT 2002 : 8th Scandinavian Workshop on Algorithm Theory
Start Page:348
End Page:357
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Turku, Finland
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
2002-07-03
Review Status:not specified
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2003-08-27
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-43866-1
LOCALID:C1256428004B93B8-BDE5926620208DA2C1256CE5006C7B5E-...
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.