Trie Memory

Trie Memory

| EDWARD FREDKIN
Trie memory is a method for storing and retrieving information, particularly useful for function-argument pairs. It offers several advantages over other memory systems, including shorter access times, ease of addition and deletion, and the ability to handle arguments of varying lengths. However, it is relatively inefficient in terms of storage space utilization. The paper introduces the basic paradigm of trie memory, describes its storage and retrieval procedures, and discusses various classes of registers. It also explores the concept of nexuses and nexus chains, which help in more general descriptions of trie memory. The paper further examines the efficiency of space utilization in trie memories, both theoretically and through Monte Carlo simulations, showing that high-dimensional trie memories can achieve over 50% space utilization. Additionally, it discusses the storage of non-binary functions and the potential for removing redundancies in stored information. The main advantages of trie memory include handling diverse-length sequences, ease of addition and deletion, speed of storage and access, elimination of redundancy, and inherent symbolic addressing. The paper concludes by summarizing the key benefits of trie memory and its potential applications in computer systems.Trie memory is a method for storing and retrieving information, particularly useful for function-argument pairs. It offers several advantages over other memory systems, including shorter access times, ease of addition and deletion, and the ability to handle arguments of varying lengths. However, it is relatively inefficient in terms of storage space utilization. The paper introduces the basic paradigm of trie memory, describes its storage and retrieval procedures, and discusses various classes of registers. It also explores the concept of nexuses and nexus chains, which help in more general descriptions of trie memory. The paper further examines the efficiency of space utilization in trie memories, both theoretically and through Monte Carlo simulations, showing that high-dimensional trie memories can achieve over 50% space utilization. Additionally, it discusses the storage of non-binary functions and the potential for removing redundancies in stored information. The main advantages of trie memory include handling diverse-length sequences, ease of addition and deletion, speed of storage and access, elimination of redundancy, and inherent symbolic addressing. The paper concludes by summarizing the key benefits of trie memory and its potential applications in computer systems.
Reach us at info@study.space