We consider skewed distributions of strings, in which any two such strings share a common prefix much longer than that expected in uniformly distributed (random) strings. For instance, this is the case of URL addresses, IP addresses, or XML path strings, all representing paths in some hierarchical order. As strings sharing a portion of the path have a quite long common prefix, we need to avoid the time-consuming repeated examination of these common prefixes while handling the linked data structures storing them. For this purpose, we show how to implement search data structures that can operate on strings with long prefixes in common. Despite the simplicity and the generality of the method, our experimental study shows that it is quite competitive with several optimized and tuned implementations currently available in the literature.
SEARCH DATA STRUCTURES FOR SKEWED STRINGS / P. CRESCENZI; R. GROSSI; G. ITALIANO. - STAMPA. - (2003), pp. 81-96. (Intervento presentato al convegno SECOND INTERNATIONAL WORKSHOP ON EXPERIMENTAL AND EFFICIENT ALGORITHMS) [10.1007/3-540-44867-5_7].
SEARCH DATA STRUCTURES FOR SKEWED STRINGS
CRESCENZI, PIERLUIGI;
2003
Abstract
We consider skewed distributions of strings, in which any two such strings share a common prefix much longer than that expected in uniformly distributed (random) strings. For instance, this is the case of URL addresses, IP addresses, or XML path strings, all representing paths in some hierarchical order. As strings sharing a portion of the path have a quite long common prefix, we need to avoid the time-consuming repeated examination of these common prefixes while handling the linked data structures storing them. For this purpose, we show how to implement search data structures that can operate on strings with long prefixes in common. Despite the simplicity and the generality of the method, our experimental study shows that it is quite competitive with several optimized and tuned implementations currently available in the literature.I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.