| EDWARD FREDKIN, Bolt Beranek and Newman, Inc., Cambridge, Mass.
Trie memory is a method for storing and retrieving information, particularly useful for function-argument (or item-term) pairs. It offers advantages such as shorter access time, ease of addition or deletion, convenience in handling arguments of varying lengths, and the ability to exploit redundancies in stored information. However, it is relatively inefficient in storage space usage, though this is less significant for large stores. The paper describes various trie memory paradigms, compares them with other memory systems, and discusses their applications.
The basic trie memory structure involves a set of registers, with each register having cells for each character in an alphabet. Initially, all cells point to a special register α. As words are stored, addresses are introduced into cells, creating paths through the memory. Storage and retrieval involve following these paths, with retrieval determining membership by checking if a path leads back to a terminal register.
Trie memory can be extended using nexuses, which are directed connections between elements. This allows for more general descriptions of trie memory structures. The paper also discusses storage, retrieval, and deletion operations, emphasizing the ability of trie memory to handle redundancy efficiently.
The paper explores different types of trie memories, including binary and N-dimensional trie memories. Binary trie memories use two cells per register, reducing storage requirements. N-dimensional trie memories use a multidimensional structure to minimize the effect of increasing register numbers, allowing efficient storage and retrieval.
The analysis of space utilization in trie memories shows that efficiency increases with the number of dimensions and the length of stored sequences. Simulation studies indicate that N-dimensional trie memories can achieve high efficiency, with more than half the total space usable for storage. The paper also discusses the capability of trie memory to remove redundancies by abstracting common sequences into models, improving storage efficiency.
Trie memory offers several advantages, including handling diverse-length sequences, ease of addition and deletion, high speed in storage and access, elimination of n-gram redundancies, and inherent symbolic addressing. These features make trie memory suitable for various applications, including computer memory systems and associative memory.
The paper concludes that trie memory is a viable paradigm for information storage and retrieval, particularly in large systems organized on a multidimensional plan. It also discusses the development of trie memory computers and apperceptive memory systems, which leverage trie memory's capabilities for efficient information handling.Trie memory is a method for storing and retrieving information, particularly useful for function-argument (or item-term) pairs. It offers advantages such as shorter access time, ease of addition or deletion, convenience in handling arguments of varying lengths, and the ability to exploit redundancies in stored information. However, it is relatively inefficient in storage space usage, though this is less significant for large stores. The paper describes various trie memory paradigms, compares them with other memory systems, and discusses their applications.
The basic trie memory structure involves a set of registers, with each register having cells for each character in an alphabet. Initially, all cells point to a special register α. As words are stored, addresses are introduced into cells, creating paths through the memory. Storage and retrieval involve following these paths, with retrieval determining membership by checking if a path leads back to a terminal register.
Trie memory can be extended using nexuses, which are directed connections between elements. This allows for more general descriptions of trie memory structures. The paper also discusses storage, retrieval, and deletion operations, emphasizing the ability of trie memory to handle redundancy efficiently.
The paper explores different types of trie memories, including binary and N-dimensional trie memories. Binary trie memories use two cells per register, reducing storage requirements. N-dimensional trie memories use a multidimensional structure to minimize the effect of increasing register numbers, allowing efficient storage and retrieval.
The analysis of space utilization in trie memories shows that efficiency increases with the number of dimensions and the length of stored sequences. Simulation studies indicate that N-dimensional trie memories can achieve high efficiency, with more than half the total space usable for storage. The paper also discusses the capability of trie memory to remove redundancies by abstracting common sequences into models, improving storage efficiency.
Trie memory offers several advantages, including handling diverse-length sequences, ease of addition and deletion, high speed in storage and access, elimination of n-gram redundancies, and inherent symbolic addressing. These features make trie memory suitable for various applications, including computer memory systems and associative memory.
The paper concludes that trie memory is a viable paradigm for information storage and retrieval, particularly in large systems organized on a multidimensional plan. It also discusses the development of trie memory computers and apperceptive memory systems, which leverage trie memory's capabilities for efficient information handling.