FLORE (FLOrence REsearch) è il repository istituzionale ad accesso pieno e aperto dell'Università degli Studi di Firenze.
Raccoglie, documenta e conserva le informazioni sulla produzione scientifica dell'Università e costituisce l'Anagrafe della ricerca dell'Ateneo.
EnglishWe 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.
| Titolo: | SEARCH DATA STRUCTURES FOR SKEWED STRINGS |
| Autori di Ateneo: | |
| Autori: | CRESCENZI, PIERLUIGI; R. GROSSI; G. ITALIANO |
| Anno di registrazione: | 2003 |
| Titolo del libro: | Experimental and Efficient Algorithms |
| Titolo del congresso: | SECOND INTERNATIONAL WORKSHOP ON EXPERIMENTAL AND EFFICIENT ALGORITHMS |
| 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. |
| Handle: | http://hdl.handle.net/2158/2512 |
| Appare nelle tipologie: | 4a - Articolo in atti di congresso |
File in questo prodotto:
Copyright © 2021