Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Towards an Efficient Approach to Manage Graph Data Evolution: Conceptual Modelling and Experimental Assessments

  • Conference paper
  • First Online:
Research Challenges in Information Science (RCIS 2021)

Part of the book series: Lecture Notes in Business Information Processing ((LNBIP,volume 415))

Included in the following conference series:

Abstract

This paper describes a new temporal graph modelling solution to organize and memorize changes in a business application. To do so, we enrich the basic graph by adding the concepts of states and instances. Our model has first the advantage of representing a complete temporal evolution of the graph, at the level of: (i) the graph structure, (ii) the attribute set of entities/relationships and (iii) the attributes’ value of entities/relationships. Then, it has the advantage of memorizing in an optimal manner evolution traces of the graph and retrieving easily temporal information about a graph component. To validate the feasibility of our proposal, we implement our proposal in Neo4j, a data store based on property graph model. We then compare its performance in terms of storage and querying time to the classical modelling approach of temporal graph. Our results show that our model outperforms the classical approach by reducing disk usage by 12 times and saving up to 99% queries’ runtime.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 99.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 129.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Denoted \(G_1, G_2, ..., G_T\) where \(G_i\) is an image of the entire graph at the time instance i and [1; T] is the timeline of the application.

  2. 2.

    Graph topology is the way in which nodes and edges are arranged within a graph.

  3. 3.

    https://virtuoso.openlinksw.com/.

  4. 4.

    https://jena.apache.org/documentation/tdb/.

  5. 5.

    d is an ALLEN temporal operator to express that a time interval X occurs “during” a time interval Y, i.e. XdY [1].

  6. 6.

    \(\circ \) is an ALLEN temporal operator to express that a time interval X “overlaps” a time interval Y, i.e. \(X \circ Y\) [1].

  7. 7.

    http://www.tpc.org/tpc_documents_current_versions/pdf/tpc-ds_v2.13.0.pdf.

  8. 8.

    The operator keys allows to extract the schema of a node or an edge. https://neo4j.com/docs/cypher-manual/current/functions/list/.

References

  1. Allen, J.F.: Maintaining knowledge about temporal intervals. Commun. ACM 26(11), 832–843 (1983). https://doi.org/10.1145/182.358434

    Article  MATH  Google Scholar 

  2. Aslay, C., Nasir, M.A.U., De Francisci Morales, G., Gionis, A.: Mining frequent patterns in evolving graphs. In: Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pp. 923–932. ACM, October 2018

    Google Scholar 

  3. Beheshti, S.M.R., Motahari-Nezhad, H.R., Benatallah, B.: Temporal Provenance Model (TPM): Model and Query Language. arXiv:1211.5009 [cs] abs/1211.5009, November 2012

  4. Brunsmann, J.: Semantic exploration of archived product lifecycle metadata under schema and instance evolution. In: SDA, pp. 37–47. Citeseer (2011)

    Google Scholar 

  5. Cattuto, C., Quaggiotto, M., Panisson, A., Averbuch, A.: Time-varying social networks in a graph database: a Neo4j use case. In: First International Workshop on Graph Data Management Experiences and Systems, GRADES 2013, pp. 1–6. Association for Computing Machinery (2013). https://doi.org/10.1145/2484425.2484442

  6. Desmier, E., Plantevit, M., Robardet, C., Boulicaut, J.-F.: Cohesive co-evolution patterns in dynamic attributed graphs. In: Ganascia, J.-G., Lenca, P., Petit, J.-M. (eds.) DS 2012. LNCS (LNAI), vol. 7569, pp. 110–124. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33492-4_11

    Chapter  Google Scholar 

  7. Fournier-Viger, P., He, G., Lin, J.C.-W., Gomes, H.M.: Mining attribute evolution rules in dynamic attributed graphs. In: Song, M., Song, I.-Y., Kotsis, G., Tjoa, A.M., Khalil, I. (eds.) DaWaK 2020. LNCS, vol. 12393, pp. 167–182. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-59065-9_14

    Chapter  Google Scholar 

  8. Hartmann, T., Fouquet, F., Moawad, A., Rouvoy, R., Le Traon, Y.: GreyCat: efficient what-if analytics for data in motion at scale. Inf. Syst. 83, 101–117 (2019). https://doi.org/10.1016/j.is.2019.03.004

    Article  Google Scholar 

  9. Holme, P., Saramäki, J.: Temporal networks. Phys. Rep. 519(3), 97–125 (2012)

    Article  Google Scholar 

  10. 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. ACM (2016)

    Google Scholar 

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

  12. Khurana, U., Deshpande, A.: Storing and Analyzing Historical Graph Data at Scale. arXiv:1509.08960 [cs], September 2015

  13. Koloniari, G., Souravlias, D., Pitoura, E.: On Graph Deltas for Historical Queries. arXiv:1302.5549 [cs] (2013)

  14. Kosmatopoulos, A., Giannakopoulou, K., Papadopoulos, A.N., Tsichlas, K.: An overview of methods for handling evolving graph sequences. In: Karydis, I., Sioutas, S., Triantafillou, P., Tsoumakos, D. (eds.) ALGOCLOUD 2015. LNCS, vol. 9511, pp. 181–192. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29919-8_14

    Chapter  Google Scholar 

  15. Kosmatopoulos, A., Gounaris, A., Tsichlas, K.: Hinode: implementing a vertex-centric modelling approach to maintaining historical graph data. Computing 101(12), 1885–1908 (2019). https://doi.org/10.1007/s00607-019-00715-6

    Article  MathSciNet  Google Scholar 

  16. Li, J., et al.: Predicting path failure in time-evolving graphs. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2019, pp. 1279–1289. Association for Computing Machinery (2019)

    Google Scholar 

  17. Maduako, I., Wachowicz, M., Hanson, T.: STVG: an evolutionary graph framework for analyzing fast-evolving networks. J. Big Data 6(1), 55 (2019). https://doi.org/10.1186/s40537-019-0218-z

    Article  Google Scholar 

  18. Moffitt, V.Z., Stoyanovich, J.: Towards sequenced semantics for evolving graphs (2017). https://doi.org/10.5441/002/EDBT.2017.41

  19. Pernelle, N., Saïs, F., Mercier, D., Thuraisamy, S.: RDF data evolution: automatic detection and semantic representation of changes. In: SEMANTiCS (2016)

    Google Scholar 

  20. Ravat, F., Song, J., Teste, O., Trojahn, C.: Improving the performance of querying multidimensional RDF data using aggregates. In: Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing, SAC 2019, pp. 2275–2284. Association for Computing Machinery (2019)

    Google Scholar 

  21. Ravat, F., Song, J., Teste, O., Trojahn, C.: Efficient querying of multidimensional RDF data with aggregates: comparing NoSQL, RDF and relational data stores. Int. J. Inf. Manag. 54, 102089 (2020)

    Article  Google Scholar 

  22. Ren, C., Lo, E., Kao, B., Zhu, X., Cheng, R.: On querying historical evolving graph sequences. Proc. VLDB Endow. 4(11), 726–737 (2011)

    Article  Google Scholar 

  23. Rodriguez, M.A., Neubauer, P.: Constructions from Dots and Lines. arXiv:1006.2361 [cs] (2010)

  24. Rossi, R.A., Gallagher, B., Neville, J., Henderson, K.: Modeling dynamic behavior in large evolving graphs. In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining - WSDM 2013, pp. 667–676. ACM Press (2013)

    Google Scholar 

  25. Roussakis, Y., Chrysakis, I., Stefanidis, K., Flouris, G., Stavrakas, Y.: A flexible framework for understanding the dynamics of evolving RDF datasets. In: Arenas, M., et al. (eds.) ISWC 2015. LNCS, vol. 9366, pp. 495–512. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-25007-6_29

    Chapter  Google Scholar 

  26. Xiangyu, L., Yingxiao, L., Xiaolin, G., Zhenhua, Y.: An efficient snapshot strategy for dynamic graph storage systems to support historical queries. IEEE Access 8, 90838–90846 (2020). https://doi.org/10.1109/ACCESS.2020.2994242

    Article  Google Scholar 

  27. Yang, Y., Yu, J.X., Gao, H., Pei, J., Li, J.: Mining most frequently changing component in evolving graphs. World Wide Web 17(3), 351–376 (2014)

    Article  Google Scholar 

  28. 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). https://doi.org/10.14569/IJACSA.2016.070273

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IRIT-CNRS (UMR 5505) - Université Toulouse 1 Capitole (UT1), 2 Rue du Doyen Gabriel Marty, 31042, Toulouse Cedex 09, France

    Landy Andriamampianina, Franck Ravat, Jiefu Song & Nathalie Vallès-Parlangeau

  2. Activus Group, 1 Chemin du Pigeonnier de la Cépière, 31100, Toulouse, France

    Landy Andriamampianina & Jiefu Song

Authors
  1. Landy Andriamampianina
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Franck Ravat
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jiefu Song
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Nathalie Vallès-Parlangeau
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Landy Andriamampianina .

Editor information

Editors and Affiliations

  1. Conservatoire National des Arts et Métiers, Paris, France

    Samira Cherfi

  2. Fondazione Bruno Kessler, Trento, Italy

    Anna Perini

  3. University Paris 1 Panthéon-Sorbonne, Paris, France

    Selmin Nurcan

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Andriamampianina, L., Ravat, F., Song, J., Vallès-Parlangeau, N. (2021). Towards an Efficient Approach to Manage Graph Data Evolution: Conceptual Modelling and Experimental Assessments. In: Cherfi, S., Perini, A., Nurcan, S. (eds) Research Challenges in Information Science. RCIS 2021. Lecture Notes in Business Information Processing, vol 415. Springer, Cham. https://doi.org/10.1007/978-3-030-75018-3_31

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-75018-3_31

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-75017-6

  • Online ISBN: 978-3-030-75018-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation