Premium
Multidimensional digital searching—alternative data structures
Author(s) -
Kirschenhofer Peter,
Prodinger Helmut
Publication year - 1994
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240050112
Subject(s) - computer science , algorithm , information retrieval , theoretical computer science , mathematics
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.