EUVIMEDEUVIMED entdecken
Crossref

Approximate String Processing

Marios Hadjieleftheriou, Divesh Srivastava

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →