Adaptive Algorithms for Cache-Efficient Trie Search

In this paper, we present cache-efficient algorithms for trie search. Thereare three key features of these algorithms. First, they use different datastructures (partitioned-array, B-tree, hashtable, vectors) to representdifferent nodes in a trie. The choice of the data structure depends on cachecharacteristics as well as the fanout of the node. Second, they adapt tochanges in the fanout at a node by dynamically switching the data structureused to represent the node. Third, the size and the layout of individual datastructures is determined based on the size of the symbols in the alphabet aswell as characteristics of the cache(s). We evaluate the performance of thesealgorithms on real and simulated memory hierarchies. Our evaluation indicatesthat these algorithms out-perform alternatives that are otherwise efficient butdo not take cache characteristics into consideration. A comparison of thenumber of instructions executed indicates that these algorithms derive theirperformance advantage primarily by making better use of the memory hierarchy.