1. Home
  2. /
  3. 9/9/2021: An overview of...

9/9/2021: An overview of Compact Data Structures, José Fuentes, University of Concepción

Speaker/presenter: José Fuentes

i) Presentation description:

The aim of compact data structures (CDS) is to represent data in space close to its theoretic lower bound while keeping the ability to support fast operations. They are different from classical compression techniques in that CDS do not need to decompress the data in order to support the operations. Thus, CDS can be seen as a good balance between compression and fast data access. Notable examples of CDS are compact bitarrays, compact trees, compact planar graphs, compact rasters and compact text indexes, etc (see [1] for more examples). Among the research groups working on CDS, Latin American researchers, in particular from Chile, highlight their contributions [2].



[1] Navarro, G. (2016). Compact Data Structures — A Practical Approach. Cambridge University Press.

[2] Arroyuelo, D., Fuentes-Sepúlveda, J. and Seco, D. (2020). Three success stories about compact data structures. Commun. ACM 63, 11 (November 2020), 64–65. DOI:https://doi.org/10.1145/3416971

[3] Lucchese, C., Nardini, F.M., Orlando, S., Perego, R., Tonellotto, N., and Venturini, R. (2017). QuickScorer: Efficient Traversal of Large Ensembles of Decision Trees. Machine Learning and Knowledge Discovery in Databases.