Improved Compressed String Dictionaries
Use this link to citehttp://hdl.handle.net/2183/24435
MetadataShow full item record
TitleImproved Compressed String Dictionaries
Alternative Title(s)CIKM '19 Proceedings of the 28th ACM International Conference on Information and Knowledge Management
Brisaboa, Nieves R., et al. Improved Compressed String Dictionaries. En Proceedings of the 28th ACM International Conference on Information and Knowledge Management. ACM, 2019. p. 29-38.
[Abstract] We introduce a new family of compressed data structures to efficiently store and query large string dictionaries in main memory. Our main technique is a combination of hierarchical Front-coding with ideas from longest-common-prefix computation in suffix arrays. Our data structures yield relevant space-time tradeoffs in real-world dictionaries. We focus on two domains where string dictionaries are extensively used and efficient compression is required: URL collections, a key element in Web graphs and applications such as Web mining; and collections of URIs and literals, the basic components of RDF datasets. Our experiments show that our data structures achieve better compression than the state-of-the-art alternatives while providing very competitive query times.