Multidimensional digital searching—alternative data structures
Peter Kirschenhofer, Helmut Prodinger · Random Structures and Algorithms · 1994
Abstract We analyze the average cost of partial match queries in M ‐dimensional Digital Search Trees and Patricia Tries. Our results allow a precise comparison of the average behavior of these data structures with the M ‐dimensional Tries studied by Flajolet and Puech [ J. Assoc. Comput. Mach. , 33 , 371–407 (1986)]. It turns out that Patricia is superior to Digital Search Tres, the latter ones being superior to Tries. © 1994 John Wiley & Sons, Inc.