Zusammenfassung

Die Schätzung der Kosten eines Abfrageplans ist eines der schwierigsten Probleme der Abfrageoptimierung. Dazu gehört auch die Abschätzung der Kardinalität von Suchmustern für Zeichenketten, insbesondere von Mehrwortzeichenketten wie Phrasen oder Textschnipseln. Auf den ersten Blick sind Suffixbäume eine Lösung für dieses Problem. Um den Speicherverbrauch eines Suffixbaums zu verringern, wird der Baum oft bis zu einer bestimmten Tiefe beschnitten. Diese Beschneidungsmethode nimmt jedoch langen Zeichenfolgen mehr Informationen "weg" als kurzen. Dieses Problem ist besonders schwerwiegend bei Mengen von langen Zeichenfolgen, die hier untersucht werden. In diesem Artikel schlagen wir entsprechende Pruning-Techniken vor. Unsere Ansätze entfernen Zeichen mit geringem Informationswert. Die verschiedenen Varianten bestimmen den Informationswert eines Zeichens auf unterschiedliche Weise, z. B. durch Verwendung der bedingten Entropie in Bezug auf die vorherigen Zeichen in der Zeichenkette. Unsere Experimente zeigen, dass unser Verfahren im Gegensatz zu dem bekannten beschnittenen Suffixbaum deutlich bessere Schätzungen liefert, wenn die Baumgröße um 60 % oder weniger reduziert wird. Aufgrund der Redundanz natürlicher Sprache liefern unsere Beschneidungsverfahren kaum Fehler bei einer Verringerung der Baumgröße um bis zu 50%.

KITopen

Zitierweise

Bibtex:
@techreport{Willkomm:2021:10.5445/IR/1000128678,
author = {Jens Willkomm und Martin Schäler und Klemens Böhm},
title = {Accurate Cardinality Estimation of Co-occurring Words Using Suffix Trees (Extended Version)},
year = {2021},
copyright = {Open Access},
doi = {10.5445/IR/1000128678},
keywords = {Abfrageoptimierung, Kardinalitätsschätzung, Suffixbaum},
Sprache = {de},
publisher = {Karlsruher Institut für Technologie (KIT)},
}