TRIE – four letters taken from the word reTRIEval. A TRIE is a digital tree structure also known as a Prefix or Radix tree. This is an extremely fast and compact data structure where a node’s key is encoded in the node’s position in the tree. TRIEs were invented by Edward Fredkin at MIT in 1960, and generated renewed interest in the 2000s when employed by Google for its autocomplete feature. This is the mechanism Google uses when a user enters a word into a search box, and Google automatically starts to complete the search string. It requires searching a web-scale index as fast as the user can type. Infinidat adapted the structure for storage virtualization, specifically for providing extremely efficient and high-speed mappings between virtualization address layers. (Definition from Mainline Information Systems.)