Asymptotic normality for the size of graph tries built from M-ary tree labelings

DOI10.1016/J.TCS.2023.114011arXiv2101.09871OpenAlexW3123191161MaRDI QIDQ6132968FDOQ6132968

Tsan-Cheng Yu, Michael Fuchs

Publication date: 21 July 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Graph tries are a new and interesting data structure proposed by Jacquet in 2014. They generalize the classical trie data structure which has found many applications in computer science and is one of the most popular data structure on words. For his generalization, Jacquet considered the size (or space requirement) and derived an asymptotic expansion for the mean and the variance when graph tries are built from $n$ independently chosen random labelings of a rooted $M$-ary tree. Moreover, he conjectured a central limit theorem for the (suitably normalized) size as the number of labelings tends to infinity. In this paper, we verify this conjecture with the method of moments.

Full work available at URL: https://arxiv.org/abs/2101.09871

zbMATH Keywords

central limit theoremmethod of momentstriesspace requirementgraph tries

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Mellin transforms and asymptotics: Harmonic sums
• A general limit theorem for recursive algorithms and combinatorial structures
• Analytical depoissonization and its applications
• An analytic approach to the asymptotic variance of trie statistics and related structures
• Title not available (Why is that?)
• A general central limit theorem for shape parameters of \(m\)-ary tries and PATRICIA tries
• A multivariate view of random bucket digital search trees
• On the variance of a class of inductive valuations of data structures for digital search
• Hidden word statistics
• Trie structure for graph sequences
• Process convergence for the complexity of radix selection on Markov sources
• Title not available (Why is that?)
• Variance of Size in Regular Graph Tries

This page was built for publication: Asymptotic normality for the size of graph tries built from M-ary tree labelings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6132968)