KIT | KIT-Bibliothek | Impressum | Datenschutz

Accurate Cardinality Estimation of Co-occurring Words Using Suffix Trees (Extended Version)

Willkomm, Jens; Schäler, Martin; Böhm, Klemens


Estimating the cost of a query plan is one of the hardest problems in query optimization. This includes cardinality estimates of string search patterns, of multi-word strings like phrases or text snippets in particular. At first sight, suffix trees address this problem. To curb the memory usage of a suffix tree, one often prunes the tree to a certain depth. But this pruning method "takes away" more information from long strings than from short ones. This problem is particularly severe with sets of long strings, the setting studied here. In this article, we propose respective pruning techniques. Our approaches remove characters with low information value. The various variants determine a character's information value in different ways, e.g., by using conditional entropy with respect to previous characters in the string. Our experiments show that, in contrast to the well-known pruned suffix tree, our technique provides significantly better estimations when the tree size is reduced by 60% or less. Due to the redundancy of natural language, our pruning techniques yield hardly any error for tree-size reductions of up to 50%.

Volltext §
DOI: 10.5445/IR/1000128678
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Programmstrukturen und Datenorganisation (IPD)
Publikationstyp Forschungsbericht/Preprint
Publikationsmonat/-jahr 03.2021
Sprache Englisch
Identifikator KITopen-ID: 1000128678
Verlag Karlsruher Institut für Technologie (KIT)
Umfang 20 S.
Schlagwörter Query optimization, cardinality estimation, suffix tree
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page