Document Open Access Logo

Investigation of Database Models for Evolving Graphs

Authors Alexandros Spitalas, Anastasios Gounaris , Kostas Tsichlas, Andreas Kosmatopoulos

PDF
Thumbnail PDF

File

LIPIcs.TIME.2021.6.pdf
  • Filesize: 1.49 MB
  • 13 pages

Document Identifiers

Author Details

Alexandros Spitalas
  • Aristotle University of Thessaloniki, Greece
Anastasios Gounaris
  • Aristotle University of Thessaloniki, Greece
Kostas Tsichlas
  • University of Patras, Greece
Andreas Kosmatopoulos
  • Aristotle University of Thessaloniki, Greece

Acknowledgements

The open access publication of this article was supported by the Alpen-Adria-Universität Klagenfurt, Austria.

Cite As Get BibTex

Alexandros Spitalas, Anastasios Gounaris, Kostas Tsichlas, and Andreas Kosmatopoulos. Investigation of Database Models for Evolving Graphs. In 28th International Symposium on Temporal Representation and Reasoning (TIME 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 206, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.TIME.2021.6

Abstract

We deal with the efficient implementation of storage models for time-varying graphs. To this end, we present an improved approach for the HiNode vertex-centric model based on MongoDB. This approach, apart from its inherent space optimality, exhibits significant improvements in global query execution times, which is the most challenging query type for entity-centric approaches. Not only significant speedups are achieved but more expensive queries can be executed as well, when compared to an implementation based on Cassandra due to the capability to exploit indices to a larger extent and benefit from in-database query processing.

Subject Classification

ACM Subject Classification
  • Information systems → Database design and models
Keywords
  • Temporal Graphs
  • Indexing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5):387-408, 2012. Google Scholar
  2. U. Khurana and A. Deshpande. Storing and analyzing historical graph data at scale. In EDBT, 2016. Google Scholar
  3. Udayan Khurana and Amol Deshpande. Efficient snapshot retrieval over historical graph data. In 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia, April 8-12, 2013, pages 997-1008, 2013. Google Scholar
  4. Udayan Khurana and Amol Deshpande. Storing and analyzing historical graph data at scale. In EDBT, pages 77-88, 2016. Google Scholar
  5. Andreas Kosmatopoulos, Kalliopi Giannakopoulou, Apostolos N Papadopoulos, and Kostas Tsichlas. An overview of methods for handling evolving graph sequences. In Algorithmic Aspects of Cloud Computing, pages 181-192. Springer, 2016. Google Scholar
  6. Andreas Kosmatopoulos, Anastasios Gounaris, and Kostas Tsichlas. Hinode: implementing a vertex-centric modelling approach to maintaining historical graph data. Computing, March 2019. URL: https://doi.org/10.1007/s00607-019-00715-6.
  7. Andreas Kosmatopoulos, Kostas Tsichlas, Anastasios Gounaris, Spyros Sioutas, and Evaggelia Pitoura. Hinode: an asymptotically space-optimal storage model for historical queries on graphs. Distributed and Parallel Databases, 2017. URL: https://doi.org/10.1007/s10619-017-7207-z.
  8. Alan G. Labouseur, Jeremy Birnbaum, Paul W. Olsen, Sean R. Spillane, Jayadevan Vijayan, Jeong-Hyon Hwang, and Wook-Shin Han. The g* graph database: efficiently managing large distributed dynamic graphs. Distributed and Parallel Databases, 33(4):479-514, 2015. Google Scholar
  9. Grzegorz Malewicz, Matthew H Austern, Aart JC Bik, James C Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. Pregel: a system for large-scale graph processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pages 135-146. ACM, 2010. Google Scholar
  10. Jayanta Mondal and Amol Deshpande. Managing large dynamic graphs efficiently. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, SIGMOD '12, pages 145-156, 2012. Google Scholar
  11. Chenghui Ren, Eric Lo, Ben Kao, Xinjie Zhu, and Reynold Cheng. On querying historical evolving graph sequences. PVLDB, 4(11):726-737, 2011. Google Scholar
  12. Betty Salzberg and Vassilis J Tsotras. Comparison of access methods for time-evolving data. ACM Computing Surveys (CSUR), 31(2):158-221, 1999. Google Scholar
  13. Konstantinos Semertzidis, Evaggelia Pitoura, and Kostas Lillis. Timereach: Historical reachability queries on evolving graphs. In Proceedings of the 18th International Conference on Extending Database Technology, EDBT 2015, Brussels, Belgium, March 23-27, 2015., pages 121-132, 2015. Google Scholar
  14. Bin Shao, Haixun Wang, and Yatao Li. Trinity: a distributed graph engine on a memory cloud. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2013, pages 505-516, 2013. Google Scholar
  15. Sean R. Spillane, Jeremy Birnbaum, Daniel Bokser, Daniel Kemp, Alan G. Labouseur, Paul W. Olsen, Jayadevan Vijayan, Jeong-Hyon Hwang, and Jun-Weon Yoon. A demonstration of the G_∗ graph database system. In 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia, April 8-12, 2013, pages 1356-1359, 2013. Google Scholar
  16. Juliette Stehlé, Nicolas Voirin, Alain Barrat, Ciro Cattuto, Vittoria Colizza, Lorenzo Isella, Corinne Régis, Jean-François Pinton, Nagham Khanafer, Wouter Van den Broeck, and et al. Simulation of an seir infectious disease model on the dynamic contact network of conference attendees. BMC Medicine, 9(1), 2011. Google Scholar
  17. Yajun Yang, Jeffrey Xu Yu, Hong Gao, Jian Pei, and Jianzhong Li. Mining most frequently changing component in evolving graphs. World Wide Web, 17(3):351-376, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact