Approximate String Processing
Foundations and Trends in Databases · 2011
DOI: 10.1561/1900000010 ↗Kurz gefasst
Fachartikel in der Zeitschrift Foundations and Trends in Databases, 2011. Verfasst von Marios Hadjieleftheriou und 1 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 79 Literaturangaben.
Abstract (Originalsprache)
One of the most important primitive data types in modern data processing is text. Text data are known to have a variety of inconsistencies (e.g., spelling mistakes and representational variations). For that reason, there exists a large body of literature related to approximate processing of text. This monograph focuses specifically on the problem of approximate string matching, where, given a set of strings S and a query string υ, the goal is to find all strings s ∈ S that have a user specified degree of similarity to υ. Set S could be, for example, a corpus of documents, a set of web pages, or an attribute of a relational table. The similarity between strings is always defined with respect to a similarity function that is chosen based on the characteristics of the data and application at hand. This work presents a survey of indexing techniques and algorithms specifically designed for approximate string matching. We concentrate on inverted indexes, filtering techniques, and tree data structures that can be used to evaluate a variety of set based and edit based similarity functions. We focus on all-match and top-k flavors of selection and join queries, and discuss the applicability, advantages and disadvantages of each technique for every query type.
Zitieren
APA
Hadjieleftheriou, M., & Srivastava, D. (2011). Approximate String Processing. Foundations and Trends in Databases. https://doi.org/10.1561/1900000010
Vancouver
Hadjieleftheriou M, Srivastava D. Approximate String Processing. Foundations and Trends in Databases. 2011. doi:10.1561/1900000010
BibTeX
@article{Hadjieleftheriou2011,
author = {Hadjieleftheriou, Marios and Srivastava, Divesh},
title = {Approximate String Processing},
journal = {Foundations and Trends in Databases},
year = {2011},
doi = {10.1561/1900000010}
}
EUVIMED