• DocumentCode
    893272
  • Title

    New results on the size of tries

  • Author

    Régnier, Mireille ; Jacquet, Philippe

  • Author_Institution
    INRIA, Le Chesnay, France
  • Volume
    35
  • Issue
    1
  • fYear
    1989
  • fDate
    1/1/1989 12:00:00 AM
  • Firstpage
    203
  • Lastpage
    205
  • Abstract
    A precise asymptotic expansion of the variance of the size of a trie built on random binary strings is presented. This data structure appears in some hashing schemes and communications protocols. The variance is asymptotically linear, and numerical results are given. The reader is referred to an earlier work for formal proofs
  • Keywords
    data structures; information theory; protocols; communications protocols; data structure; hashing schemes; numerical results; precise asymptotic expansion; random binary strings; size variance; trie structure; Analysis of variance; Data structures; Information retrieval; Memory; Protocols; Random variables; Tree data structures;
  • fLanguage
    English
  • Journal_Title
    Information Theory, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9448
  • Type

    jour

  • DOI
    10.1109/18.42197
  • Filename
    42197
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=893272