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.
2003
Experimental and Efficient Algorithms
SECOND INTERNATIONAL WORKSHOP ON EXPERIMENTAL AND EFFICIENT ALGORITHMS
P. CRESCENZI; R. GROSSI; G. ITALIANO
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/2512
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 8
social impact