Smoothed Analysis of Trie Height by Star-like PFAs

Eckhardt, Stefan; Kosub, Sven; Nowak, Johannes

Smoothed Analysis of Trie Height by Star-like PFAs

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2020

Autor:innen

Eckhardt, Stefan

Kosub, Sven

Nowak, Johannes

Publikationstyp

Preprint

Publikationsstatus

Published

Zusammenfassung

Tries are general purpose data structures for information retrieval. The most significant parameter of a trie is its height H which equals the length of the longest common prefix of any two string in the set A over which the trie is built. Analytical investigations of random tries suggest that Exp(H)\in O(log |A|)), although H is unbounded in the worst case. Moreover, sharp results on the distribution function of H are known for many different random string sources. But because of the inherent weakness of the modeling behind average-case analysis---analyses being dominated by random data---these results can utterly explain the fact that in many practical situations the trie height is logarithmic. We propose a new semi-random string model and perform a smoothed analysis in order to give a mathematically more rigorous explanation for the practical findings. The perturbation functions which we consider are based on probabilistic finite automata (PFA) and we show that the transition probabilities of the representing PFA completely characterize the asymptotic growth of the smoothed trie height. Our main result is of dichotomous nature---logarithmic or unbounded---and is certainly not surprising at first glance, but we also give quantitative upper and lower bounds, which are derived using multivariate generating function in order to express the computations of the perturbing PFA. A direct consequence is the logarithmic trie height for edit perturbations(i.e., random insertions, deletions and substitutions).

Fachgebiet (DDC)

004 Informatik

Schlagwörter

Analysis of Algorithms, Trie

Zitieren

ISO 690

ECKHARDT, Stefan, Sven KOSUB, Johannes NOWAK, 2020. Smoothed Analysis of Trie Height by Star-like PFAs

BibTex

@unpublished{Eckhardt2020-03-09T12:55:36ZSmoot-55838,
  year={2020},
  title={Smoothed Analysis of Trie Height by Star-like PFAs},
  author={Eckhardt, Stefan and Kosub, Sven and Nowak, Johannes}
}

RDF

<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/55838">
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-12-10T10:41:25Z</dc:date>
    <dc:creator>Kosub, Sven</dc:creator>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/55838"/>
    <dc:creator>Nowak, Johannes</dc:creator>
    <dc:contributor>Eckhardt, Stefan</dc:contributor>
    <dc:contributor>Kosub, Sven</dc:contributor>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:language>eng</dc:language>
    <dc:creator>Eckhardt, Stefan</dc:creator>
    <dc:contributor>Nowak, Johannes</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:abstract xml:lang="eng">Tries are general purpose data structures for information retrieval. The most significant parameter of a trie is its height H which equals the length of the longest common prefix of any two string in the set A over which the trie is built. Analytical investigations of random tries suggest that Exp(H)\in O(log |A|)), although H is unbounded in the worst case. Moreover, sharp results on the distribution function of H are known for many different random string sources. But because of the inherent weakness of the modeling behind average-case analysis---analyses being dominated by random data---these results can utterly explain the fact that in many practical situations the trie height is logarithmic. We propose a new semi-random string model and perform a smoothed analysis in order to give a mathematically more rigorous explanation for the practical findings. The perturbation functions which we consider are based on probabilistic finite automata (PFA) and we show that the transition probabilities of the representing PFA completely characterize the asymptotic growth of the smoothed trie height. Our main result is of dichotomous nature---logarithmic or unbounded---and is certainly not surprising at first glance, but we also give quantitative upper and lower bounds, which are derived using multivariate generating function in order to express the computations of the perturbing PFA. A direct consequence is the logarithmic trie height for edit perturbations(i.e., random insertions, deletions and substitutions).</dcterms:abstract>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:issued>2020-03-09T12:55:36Z</dcterms:issued>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2021-12-10T10:41:25Z</dcterms:available>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:rights>terms-of-use</dc:rights>
    <dcterms:title>Smoothed Analysis of Trie Height by Star-like PFAs</dcterms:title>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Ja