Compact Data Structures and Query Processing for Temporal Graphs

PhD Thesis
by Diego Caro A. <diegocaro at udec cl>

Advisor: Dr. M. Andrea Rodríguez
Co-Advisor: Dr. Nieves R. Brisaboa
Department of Computer Science
University of Concepción, Chile

The thesis + slides are freely available.

Abstract

Temporal graphs represent vertices and binary relations that change along time. A temporal graph could be represented as several static graphs (or snapshots), one per each time point in the lifetime of the graph. The main problem of this representation is the space usage when edges remain unchanged for long periods of time, as consecutive snapshots tend to be very similar between them. Consequently, most of the space correspond to a replication of previous snapshots.

In this thesis, we explore alternative representations of temporal graphs that are efficient in space and in time to answer adjacency operations. On one hand, a representation based on a log of changes stores the time instant when edges appear or disappear. A multidimensional binary matrix, on the other hand, stores data of edges and their valid time intervals as cells in a 4D matrix, which reduces space while maintaining a good retrieval time.

Publications

Journal

• D. Caro, A. Rodríguez, N. R. Brisaboa, and A. Fariña, “Compressed \(k^d\)-tree for temporal graphs,” Knowledge and Information Systems, pp. 1–43, Dec. 2015. DOI: http://dx.doi.org/10.1007/s10115-015-0908-6
• D. Caro, M. Andrea Rodríguez, and N. R. Brisaboa, “Data structures for temporal graphs based on compact sequence representations,” Information Systems, vol. 51, pp. 1–26, Jul. 2015. DOI: http://dx.doi.org/10.1016/j.is.2015.02.002
• N. R. Brisaboa, D. Caro, A. Fariña, and M. A. Rodríguez, "Using Compressed Suffix-Arrays for a Compact Representation of Temporal-Graphs", Information Sciences, vol. 465, pp. 459-483, Oct. 2018. DOI: https://doi.org/10.1016/j.ins.2018.07.023

International Conferences

• N. R. Brisaboa, D. Caro, A. Fariña, and M. A. Rodríguez, "A Compressed Suffix-Array Strategy for Temporal-Graph Indexing," presented at the Proceedings of the 21st International Symposium on String Processing and Information Retrieval - Volume 8799, Ouro Preto, Brazil, 2014, vol. 8799, pp. 77–88. DOI: http://dx.doi.org/10.1007/978-3-319-11918-2_8
• G. D. Bernardo, N. R. Brisaboa, D. Caro, and M. A. Rodriguez, “Compact Data Structures for Temporal Graphs,” presented at the Data Compression Conference (DCC), 2013, 2013, p. 477. DOI: http://dx.doi.org/10.1109/DCC.2013.59

International Workshops

• D. Caro, "A compressed hexatree for temporal-graph indexing... or how to compress the \(k^4\)-tree," presented at the SPIRE 2014 Workshop on Compression, Text, and Algorithms (WCTA 2014), Ouro Preto, Brazil.

Code and datasets

Visit http://github.com/diegocaro/temporalgraphs.

Acknowledgements

Through the journey of pursuing the PhD I received support from people all over the world. With these words I would like to say thank you to all of them. In particular, I would like to say thanks to Diego Seco for his help in the preliminary discussions of the structures, to Antonio Fariña for his infinite support in the development and implementation of many data structures, to Guillermo de Bernardo and Susana Ladra for introduce me to the \(k^2\) world, to Gonzalo Navarro and Simon Gog for their suggestions on the improvement of the data structures and the experimental evaluation, and to Claudio Sanhueza from Yahoo! Labs Chile who helped me to obtain datasets for the experimental evaluation.

And of course, I would like to say thank to my co-phd-workers José Fuentes, Erick Elejalde, Natalia Jaña, Sandra Álvarez, Guillermo de Bernardo and Leticia González.

This work was partially supported by a CONICYT doctoral fellowship 21120569, by Fondecyt 1140428, and by Fondef D09I1185.

The idea of creating this web site was borrowed from my friend and colleage José Fuentes.