Top

Hint

Swipe to navigate through the chapters of this book

Published in:

Read chapter Read first chapter

2023 | OriginalPaper | Chapter

MAGMA: Proposing a Massive Historical Graph Management System

Authors : Alexandros Spitalas, Kostas Tsichlas

Published in: Algorithmic Aspects of Cloud Computing

Publisher: Springer International Publishing

Abstract

In recent years, maintaining the history of graphs has become more and more imperative due to the emergence of related applications in a number of fields like health services, social interactions, and map guidance. Historical graphs focus on being able to store and query the whole evolution of the graph and not just the latest instance. In this paper we have two goals: 1) provide a concise survey of the state-of-art with respect to systems in historical graph management since no such comprehensive discussion exists and 2) propose an architecture for a distributed historical graph management system (named MAGMA - MAssive Graph MAnagement) based on previous research work of the authors.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter SQL Query Optimization in Distributed NoSQL Databases for Cloud-Based Applications

next chapter New Results in Priority-Based Bin Packing

Andriamampianina, L., Ravat, F., Song, J., Vallès-Parlangeau, N.: A generic modelling to capture the temporal evolution in graphs. In: 16e journées EDA : Business Intelligence & Big Data (EDA 2020), vol. RNTI-B-16, pp. 19–32. Lyon, France (2020). https://hal.science/hal-03109670

Besta, M., Fischer, M., Kalavri, V., Kapralov, M., Hoefler, T.: Practice of streaming processing of dynamic graphs: concepts, models, and systems (2021)

Bok, K., Kim, G., Lim, J., Yoo, J.: Historical graph management in dynamic environments. Electronics 9(6), 895 (2020). https://doi.org/10.3390/electronics9060895

Byun, J.: Enabling time-centric computation for efficient temporal graph traversals from multiple sources. IEEE Transactions on Knowledge and Data Engineering, p. 1 (2020). https://doi.org/10.1109/TKDE.2020.3005672

Byun, J., Woo, S., Kim, D.: Chronograph: enabling temporal graph traversals for efficient information diffusion analysis over time. IEEE Trans. Knowl. Data Eng. 32(3), 424–437 (2020). https://doi.org/10.1109/TKDE.2019.2891565 CrossRef

Christ, L., Gomez, K., Rahm, E., Peukert, E.: Distributed graph pattern matching on evolving graphs (2020)

Dhulipala, L., Blelloch, G.E., Shun, J.: Low-latency graph streaming using compressed purely-functional trees. In: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 918–934. PLDI 2019, Association for Computing Machinery, New York, NY, USA (2019)

Ding, M., Yang, M., Chen, S.: Storing and querying large-scale spatio-temporal graphs with high-throughput edge insertions. arXiv preprint arXiv:1904.09610 (2019)

Gandhi, S., Simmhan, Y.: An interval-centric model for distributed computing over temporal graphs. In: 2020 IEEE 36th International Conference on Data Engineering (ICDE), pp. 1129–1140 (2020). https://doi.org/10.1109/ICDE48307.2020.00102

10.

Gedik, B., Bordawekar, R.: Disk-based management of interaction graphs. IEEE Trans. Knowl. Data Eng. 26(11), 2689–2702 (2014). https://doi.org/10.1109/TKDE.2013.2297930

11.

Gonzalez, J.E., Low, Y., Gu, H., Bickson, D., Guestrin, C.: PowerGraph: distributed graph-parallel computation on natural graphs, pp. 17–30. OSDI2012, USENIX Association (2012)

12.

Han, W., Li, K., Chen, S., Chen, W.: Auxo: a temporal graph management system. Big Data Min. Anal. 2(1), 58–71 (2019). https://doi.org/10.26599/BDMA.2018.9020030

13.

Han, W., et al.: Chronos: a graph engine for temporal graph analysis. In: Proceedings of the Ninth European Conference on Computer Systems. EuroSys 2014, Association for Computing Machinery, New York, NY, USA (2014). https://doi.org/10.1145/2592798.2592799

14.

Hartmann, T., Fouquet, F., Jimenez, M., Rouvoy, R., Le Traon, Y.: Analyzing complex data in motion at scale with temporal graphs (2017). https://doi.org/10.18293/SEKE2017-048

15.

Huang, H., Song, J., Lin, X., Ma, S., Huai, J.: TGraph: a temporal graph data management system. In: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, pp. 2469–2472. CIKM 2016, Association for Computing Machinery, New York, NY, USA (2016). https://doi.org/10.1145/2983323.2983335

16.

Iyer, A.P., Li, L.E., Das, T., Stoica, I.: Time-evolving graph processing at scale. In: Proceedings of the Fourth International Workshop on Graph Data Management Experiences and Systems, pp. 1–6 (2016)

17.

Iyer, A.P., Pu, Q., Patel, K., Gonzalez, J.E., Stoica, I.: TEGRA: efficient ad-hoc analytics on evolving graphs. In: 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21), pp. 337–355. USENIX Association (2021). https://www.usenix.org/conference/nsdi21/presentation/iyer

18.

Ju, X., Williams, D., Jamjoom, H., Shin, K.G.: Version traveler: fast and memory-efficient version switching in graph processing systems. In: 2016 USENIX Annual Technical Conference (USENIX-ATC 16), pp. 523–536 (2016)

19.

Junghanns, M., Petermann, A., Teichmann, N., Gómez, K., Rahm, E.: Analyzing extended property graphs with apache flink. In: Proceedings of the 1st ACM SIGMOD Workshop on Network Data Analytics. NDA 2016, Association for Computing Machinery, New York, NY, USA (2016). https://doi.org/10.1145/2980523.2980527

20.

Khurana, U., Deshpande, A.: Efficient snapshot retrieval over historical graph data. In: 2013 IEEE 29th International Conference on Data Engineering (ICDE), pp. 997–1008 (2013). https://doi.org/10.1109/ICDE.2013.6544892

21.

Khurana, U., Deshpande, A.: Storing and analyzing historical graph data at scale. In: Pitoura, E., et al. (eds.) Proceedings of the 19th International Conference on Extending Database Technology, EDBT 2016, Bordeaux, France, 15–16 March 2016, pp. 65–76. OpenProceedings.org (2016). https://doi.org/10.5441/002/edbt.2016.09

22.

Kosmatopoulos, A., Gounaris, A., Tsichlas, K.: Hinode: implementing a vertex-centric modelling approach to maintaining historical graph data. Computing 101(12), 1885–1908 (2019)

23.

Kosmatopoulos, A., Tsichlas, K., Gounaris, A., Sioutas, S., Pitoura, E.: Hinode: an asymptotically space-optimal storage model for historical queries on graphs. Distrib. Parall. Databases 35(3–4), 249–285 (2017)

24.

Kumar, P., Huang, H.H.: GraphOne: a data store for real-time analytics on evolving graphs. ACM Trans. Storage 15(4) (2020). https://doi.org/10.1145/3364180

25.

Labouseur, A.G., et al.: The g* graph database: efficiently managing large distributed dynamic graphs. Distrib. Parall. Databases 33(4), 479–514 (2015)

26.

Lightenberg, W., Pei, Y., Fletcher, G., Pechenizkiy, M.: Tink: A temporal graph analytics library for apache Flink. In: Companion Proceedings of the The Web Conference 2018, pp. 71–72 (2018)

27.

Lim, S., Coy, T., Lu, Z., Ren, B., Zhang, X.: NVGraph: enforcing crash consistency of evolving network analytics in NVMM systems. IEEE Trans. Parall. Distrib. System. 31(6), 1255–1269 (2020). https://doi.org/10.1109/TPDS.2020.2965452

28.

Maduako, I., Wachowicz, M., Hanson, T.: STVG: an evolutionary graph framework for analyzing fast-evolving networks. J. Big Data 6(1), 1–24 (2019) CrossRef

29.

Massri, M., Raipin Parvedy, P., Meye, P.: GDBAlive: a temporal graph database built on top of a columnar data store. J. Adv. Inf. Technol. 12, 169–178 (2020). https://doi.org/10.12720/jait.12.3.169-178

30.

Miao, Y., et al.: ImmortalGraph: a system for storage and analysis of temporal graphs. ACM Trans. Storage 11(3), 2700302 (2015). https://doi.org/10.1145/2700302

31.

Moffitt, V., Stoyanovich, J.: Portal: a query language for evolving graphs (2016)

32.

Moffitt, V.Z.: Framework for querying and analysis of evolving graphs, Ph. D. thesis (2017). https://doi.org/10.13140/RG.2.2.16079.64166. https://www.proquest.com/docview/1946186055?pq-origsite=gscholar &fromopenview=true

33.

Moffitt, V.Z., Stoyanovich, J.: Towards sequenced semantics for evolving graphs. In: EDBT, pp. 446–449 (2017)

34.

Ramesh, S., Baranawal, A., Simmhan, Y.: Granite: a distributed engine for scalable path queries over temporal property graphs. J. Parallel Distrib. Comput. 151, 94–111 (2021)

35.

Rost, C., et al.: Distributed temporal graph analytics with GRADOOP. VLDB J. 31, 375–401 (2021). https://doi.org/10.1007/s00778-021-00667-4

36.

Rost, C., Thor, A., Rahm, E.: Analyzing temporal graphs with GRADOOP. Datenbank-Spektrum 19(3), 199–208 (2019)

37.

Sahu, S., Salihoglu, S.: Graphsurge: Graph analytics on view collections using differential computation. In: Proceedings of the 2021 International Conference on Management of Data, pp. 1518–1530 (2021)

38.

Spitalas, A., Gounaris, A., Tsichlas, K., Kosmatopoulos, A.: Investigation of database models for evolving graphs. In: Combi, C., Eder, J., Reynolds, M. (eds.) 28th International Symposium on Temporal Representation and Reasoning, TIME 2021, 27–29 September 2021, Klagenfurt, Austria. LIPIcs, vol. 206, pp. 1–13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021). https://doi.org/10.4230/LIPIcs.TIME.2021.6

39.

Steer, B., Cuadrado, F., Clegg, R.: Raphtory: streaming analysis of distributed temporal graphs. Future Gener. Comput. Syst. 102, 453–464 (2020)

40.

Vijitbenjaronk, W.D., Lee, J., Suzumura, T., Tanase, G.: Scalable time-versioning support for property graph databases. In: 2017 IEEE International Conference on Big Data (Big Data), pp. 1580–1589 (2017). https://doi.org/10.1109/BigData.2017.8258092

41.

Zaki, A., Attia, M., Hegazy, D., Amin, S.: Comprehensive survey on dynamic graph models. Int. J. Adv. Comput. Sci. Appl. 7(2), 573–582 (2016)

Title: MAGMA: Proposing a Massive Historical Graph Management System
Authors: Alexandros Spitalas
Kostas Tsichlas
Publisher: Springer International Publishing
Book: Algorithmic Aspects of Cloud Computing
Print ISBN: 978-3-031-33436-8

Electronic ISBN: 978-3-031-33437-5

Copyright Year: 2023
DOI: https://doi.org/10.1007/978-3-031-33437-5_3

Springer Professional

Hint

Swipe to navigate through the chapters of this book

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"