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

DOI10.1016/0304-3975(94)00306-4MaRDI QIDQ672993zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• On The variance of the extremal path length in a symmetric digital trie
• scientific article; zbMATH DE number 3961005
• Digital Search Trees Again Revisited: The Internal Path Length Perspective
• MULTIDIMENSIONAL DIGITAL SEARCHING AND SOME NEW PARAMETERS IN TRIES

Cites work

• scientific article; zbMATH DE number 3978406 (Why is no real title available?)
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3080734 (Why is no real title available?)
• scientific article; zbMATH DE number 3111409 (Why is no real title available?)
• Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
• Digital Search Trees Revisited
• Dynamic hashing
• Exact and asymptotic distributions in digital and binary search trees
• File structures using hashing functions
• MULTIDIMENSIONAL DIGITAL SEARCHING AND SOME NEW PARAMETERS IN TRIES
• Multidimensional digital searching—alternative data structures
• New results on the size of tries
• 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
• On some applications of formulae of Ramanujan in the analysis of algorithms
• On the Complexity of Finite Sequences
• On the balance property of Patricia tries: External path length viewpoint
• Partial match retrieval of multidimensional data
• Partial-Match Retrieval Algorithms
• The average CRI-length of a tree collision resolution algorithm in presence of multiplicity-dependent capture effects
• Trie size in a dynamic list structure

Cited in

(9)

• Asymptotic normality for the size of graph tries built from M-ary tree labelings
• A general central limit theorem for shape parameters of m-ary tries and PATRICIA tries
• On 2-protected nodes in random digital trees
• scientific article; zbMATH DE number 1545683 (Why is no real title available?)
• Dependence between path-length and size in random digital trees
• An analytic approach to the asymptotic variance of trie statistics and related structures
• On the variety of shapes in digital trees
• The Wiener index of random digital trees
• On the variance of the internal path length of generalized digital trees -- the Mellin convolution approach

Describes a project that uses

Uses Software

• PATRICIA

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

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