Fast compressed tries through path decompositions (Articolo in rivista)

Type
Label
  • Fast compressed tries through path decompositions (Articolo in rivista) (literal)
Anno
  • 2014-01-01T00:00:00+01:00 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
  • 10.1145/2656332 (literal)
Alternative label
  • Grossi R., Ottaviano G. (2014)
    Fast compressed tries through path decompositions
    in ACM journal of experimental algorithmics
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Grossi R., Ottaviano G. (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#url
  • http://www.scopus.com/inward/record.url?eid=2-s2.0-84908090421&partnerID=q2rCbXpz (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 19 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroFascicolo
  • 1 (literal)
Note
  • PuMa (literal)
  • Scopu (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Dipartimento di Informatica, Università di Pisa, Italy; CNR-ISTI, Pisa, Italy (literal)
Titolo
  • Fast compressed tries through path decompositions (literal)
Abstract
  • Tries are popular data structures for storing a set of strings, where common prefixes are represented by common root-to-node paths. More than 50 years of usage have produced many variants and implementations to overcome some of their limitations.We explore new succinct representations of path-decomposed tries and experimentally evaluate the corresponding reduction in space usage and memory latency, comparing with the state of the art.We study the following applications: compressed string dictionary and monotone minimal perfect hash for strings. In compressed string dictionary, we obtain data structures that outperform other state-of-the-art compressed dictionaries in space efficiency while obtaining predictable query times that are competitive with data structures preferred by the practitioners. On real-world datasets, our compressed tries obtain the smallest space (except for one case) and have the fastest lookup times, whereas access times are within 20% slower than the best-known solutions. In monotone minimal perfect hash for strings, our compressed tries perform several times faster than other trie-based monotone perfect hash functions while occupying nearly the same space. On real-world datasets, our tries are approximately 2 to 5 times faster than previous solutions, with a space occupancy less than 10% larger. Categories and Subject Descriptors: H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval; E.1 [Data Structures]: Trees General Terms: Algorithms, Experimentation, Performance. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Prodotto
Autore CNR di
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
Insieme di parole chiave di
data.CNR.it