On the variance of a class of inductive valuations of data structures for digital search

DOI10.1016/0304-3975(94)00306-4zbMath0874.68077OpenAlexW1966082969MaRDI QIDQ672993

Werner Schachinger

Publication date: 28 February 1997

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

Full work available at URL: https://doi.org/10.1016/0304-3975(94)00306-4

zbMATH Keywords

binary triesPatricia tries

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05)

Related Items (9)

A general central limit theorem for shape parameters of \(m\)-ary tries and PATRICIA tries ⋮ On the variety of shapes in digital trees ⋮ Asymptotic normality for the size of graph tries built from M-ary tree labelings ⋮ An analytic approach to the asymptotic variance of trie statistics and related structures ⋮ Unnamed Item ⋮ Dependence between path-length and size in random digital trees ⋮ On 2-protected nodes in random digital trees ⋮ On the variance of the internal path length of generalized digital trees -- the Mellin convolution approach ⋮ The Wiener Index of Random Digital Trees

Uses Software

• PATRICIA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
• On the balance property of Patricia tries: External path length viewpoint
• On The variance of the extremal path length in a symmetric digital trie
• On a functional equation arising in the analysis of a protocol for a multi-access broadcast channel
• Digital Search Trees Revisited
• Exact and asymptotic distributions in digital and binary search trees
• On some applications of formulae of Ramanujan in the analysis of algorithms
• Partial-Match Retrieval Algorithms
• On the Complexity of Finite Sequences
• Dynamic hashing
• MULTIDIMENSIONAL DIGITAL SEARCHING AND SOME NEW PARAMETERS IN TRIES
• Multidimensional digital searching—alternative data structures
• Trie size in a dynamic list structure
• New results on the size of tries
• The average CRI-length of a tree collision resolution algorithm in presence of multiplicity-dependent capture effects
• Partial match retrieval of multidimensional data
• File structures using hashing functions

This page was built for publication: On the variance of a class of inductive valuations of data structures for digital search