Top

Software and Systems Modeling

Published in:

02-11-2020 | Regular Paper

Improving query performance on dynamic graphs

Authors: Gala Barquero, Javier Troya, Antonio Vallecillo

Published in: Software and Systems Modeling | Issue 4/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Querying large models efficiently often imposes high demands on system resources such as memory, processing time, disk access or network latency. The situation becomes more complicated when data are highly interconnected, e.g. in the form of graph structures, and when data sources are heterogeneous, partly coming from dynamic systems and partly stored in databases. These situations are now common in many existing social networking applications and geo-location systems, which require specialized and efficient query algorithms in order to make informed decisions on time. In this paper, we propose an algorithm to improve the memory consumption and time performance of this type of queries by reducing the amount of elements to be processed, focusing only on the information that is relevant to the query but without compromising the accuracy of its results. To this end, the reduced subset of data is selected depending on the type of query and its constituent filters. Three case studies are used to evaluate the performance of our proposal, obtaining significant speedups in all cases.

previous article Towards a model-driven approach for multiexperience AI-based user interfaces

next article Analysis of variability models: a systematic literature review

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 "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

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

Available only for authorised users

Note that we used the in-memory implementation for OrientDB and the BerkeleyDB backend [28] for JanusGraph.

Even if CrateDB is not a graph database, we included it in our study because of its high scalability.

A TraversalParent in Gremlin includes steps that imply one or more subqueries, namely where, and, or and not.

The SDR algorithm adds an initial graph step at the beginning of a traversal subquery. For this reason, a traversal subquery always has one more step than its size, i.e. S.size = 4 in this case.

Acharya, S., Gibbons, P.B., Poosala, V.: Congressional samples for approximate answering of group-by queries. In: Proc. of SIGMOD’00, pp. 487–498. ACM (2000). https://doi.org/10.1145/342009.335450

Agarwal, S., Panda, A., Mozafari, B., Iyer, A.P., Madden, S., Stoica, I.: Blink and it’s done: interactive queries on very large data. PVLDB 5(12), 1902–1905 (2012). https://doi.org/10.14778/2367502.2367533CrossRef

Angles, R., Arenas, M., Barceló, P., Hogan, A., Reutter, J.L., Vrgoc, D.: Foundations of modern query languages for graph databases. ACM Comput. Surv. 50(5), 68:1–68:40 (2017). https://doi.org/10.1145/3104031CrossRef

Apache Spark: Spark streaming programming. https://spark.apache.org/docs/latest/streaming-programming-guide.html. Accessed May 2019

Apache Spark: GraphFrames. https://graphframes.github.io/graphframes/docs/_site/index.html. Accessed Nov 2019

Apache TinkerPop: The Gremlin graph traversal machine and language. https://tinkerpop.apache.org/gremlin.html. Accessed Jan 2020

Babcock, B., Chaudhuri, S., Das, G.: Dynamic sample selection for approximate query processing. In: Proc. of SIGMOD’03, pp. 539–550. ACM (2003). https://doi.org/10.1145/872757.872822

Barceló, P.: Querying graph databases. In: Proc. of PODS’13, pp. 175–188. ACM (2013). https://doi.org/10.1145/2463664.2465216

Barquero, G., Burgueño, L., Troya, J., Vallecillo, A.: Extending complex event processing to graph-structured information. In: Proc. of MODELS’18, pp. 166–175. ACM (2018). https://doi.org/10.1145/3239372.3239402

10.

Barquero, G., Troya, J., Vallecillo, A.: Trading accuracy for performance in data processing applications. J. Object Technol. 18(2), 9:1–9:24 (2019). https://doi.org/10.5381/jot.2019.18.2.a9CrossRef

11.

Barquero, G., Troya, J., Vallecillo, A.: SDR algorithm git repository. https://github.com/atenearesearchgroup/SDRalgorithm. Accessed Jan 2020

12.

Barquero, G., Troya, J., Vallecillo, A.: SDR algorithm website. http://atenea.lcc.uma.es/projects/SDRAlg.html. Accessed Jan 2020

13.

BBVA: The impact of the Mobile World Congress in a dynamic visualization by BBVA and CartoDB (2013). https://www.bbva.com/en/impact-mobile-world-congress-dynamic-visualization-bbva-cartodb/. Accessed Jan 2020

14.

Bergmann, G., Horváth, Á., Ráth, I., Varró, D., Balogh, A., Balogh, Z., Ökrös, A.: Incremental evaluation of model queries over EMF models. In: Proc. of MODELS’10, pp. 76–90 (2010). https://doi.org/10.1007/978-3-642-16145-2_6

15.

Bergmann, G., Ökrös, A., Ráth, I., Varró, D., Varró, G.: Incremental pattern matching in the VIATRA model transformation system. In: Proc. of GRAMOT’08, pp. 25–32. ACM (2008)

16.

Besta, M., Fischer, M., Kalavri, V., Kapralov, M., Hoefler, T.: Practice of streaming and dynamic graphs: concepts, models, systems, and parallelism. CoRR arXiv:1912.12740 (2019)

17.

Besta, M., Peter, E., Gerstenberger, R., Fischer, M., Podstawski, M., Barthels, C., Alonso, G., Hoefler, T.: Demystifying graph databases: analysis and taxonomy of data organization, system designs, and graph queries. CoRR arXiv:1910.09017 (2019)

18.

Callidus Software Inc.: OrientDB. The database designed for the modern world. https://orientdb.com/. Accessed June 2020

19.

Chaudhuri, S., Das, G., Datar, M., Motwani, R., Narasayya, V.R.: Overcoming limitations of sampling for aggregation queries. In: Proc. of ICDE’01, pp. 534–542. IEEE Computer Society (2001). https://doi.org/10.1109/ICDE.2001.914867

20.

Chaudhuri, S., Das, G., Narasayya, V.R.: A robust, optimization-based approach for approximate answering of aggregate queries. In: Proc. of SIGMOD’01, pp. 295–306. ACM (2001). https://doi.org/10.1145/375663.375694

21.

Chaudhuri, S., Ding, B., Kandula, S.: Approximate query processing: no silver bullet. In: Proc. of SIGMOD’17, pp. 511–519. ACM (2017). https://doi.org/10.1145/3035918.3056097

22.

Cugola, G., Margara, A.: Processing flows of information: from data stream to complex event processing. ACM Comput. Surv. 44(3), 15:1–15:62 (2012). https://doi.org/10.1145/2187671.2187677CrossRef

23.

Etzion, O., Niblett, P.: Event Processing in Action. Manning Publications, New York (2010)

24.

Fan, W., Geerts, F., Cao, Y., Deng, T., Lu, P.: Querying big data by accessing small data. In: Proc. of PODS’15, pp. 173–184. ACM (2015). https://doi.org/10.1145/2745754.2745771

25.

Fan, W., Li, J., Ma, S., Tang, N., Wu, Y., Wu, Y.: Graph pattern matching: From intractable to polynomial time. PVLDB 3(1), 264–275 (2010). https://doi.org/10.14778/1920841.1920878CrossRef

26.

Fan, W., Wang, X., Wu, Y.: Querying big graphs within bounded resources. In: Proc. of SIGMOD’14, pp. 301–312. ACM (2014). https://doi.org/10.1145/2588555.2610513

27.

Gonzalez, J.E., Xin, R.S., Dave, A., Crankshaw, D., Franklin, M.J., Stoica, I.: GraphX: graph processing in a distributed dataflow framework. In: Proc. of OSDI’14, pp. 599–613 (2014)

28.

Group, C.M.D.: BerkeleyDB. https://dbdb.io/db/berkeley-db. Accessed July 2020

29.

Holzschuher, F., Peinl, P.D.R.: Performance of graph query languages: comparison of cypher, gremlin and native access in Neo4j. In: Proc. of GraphQ@EDBT/ICDT’13, pp. 195–204 (2013). https://doi.org/10.1145/2457317.2457351

30.

JanusGraph: Distributed, open source, massively scalable graph database . https://janusgraph.org/. Accessed June 2020

31.

Johann, S., Egyed, A.: Instant and incremental transformation of models. In: Proc. of ASE’04, pp. 362–365. IEEE Computer Society (2004). https://doi.org/10.1109/ASE.2004.10047

32.

Jouault, F., Tisi, M.: Towards incremental execution of ATL transformations. In: Proc. of ICMT’10, LNCS, vol. 6142, pp. 123–137. Springer (2010). https://doi.org/10.1007/978-3-642-13688-7_9

33.

Kafka, A.: Apache Kafka. A distributed streaming platform. https://kafka.apache.org/intro. Accessed May 2019

34.

Kalavri, V., Vlassov, V., Haridi, S.: High-level programming abstractions for distributed graph processing. IEEE Trans. Knowl. Data Eng. 30(2), 305–324 (2018). https://doi.org/10.1109/TKDE.2017.2762294CrossRef

35.

Lee, K., Liu, L.: Scaling queries over big RDF graphs with semantic hash partitioning. PVLDB 6(14), 1894–1905 (2013). https://doi.org/10.14778/2556549.2556571CrossRef

36.

Li, K., Li, G.: Approximate query processing: What is new and where to go?—a survey on approximate query processing. Data Sci. Eng. 3(4), 379–397 (2018). https://doi.org/10.1007/s41019-018-0074-4CrossRef

37.

Ltd, M.: Memgraph. Difference from Neo4j’s cypher implementation. https://docs.memgraph.com/memgraph/reference-overview/differences. Accessed Sept 2020

38.

Luckham, D.C.: The Power of Events: An Introduction to Complex Event Processing in Distributed Enterprise Systems. Addison-Wesley, Boston (2002)

39.

Luckham, D.C.: Event Processing for Business: Organizing the Real-Time Enterprise. Wiley, New York (2012)CrossRef

40.

Malewicz, G., Austern, M.H., Bik, A.J.C., Dehnert, J.C., Horn, I., Leiser, N., Czajkowski, G.: Pregel: a system for large-scale graph processing. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2010, Indianapolis, June 6–10, 2010, pp. 135–146 (2010). https://doi.org/10.1145/1807167.1807184

41.

Memgraph Ltd: Memgraph graph database. https://memgraph.com/. Accessed Nov 2019

42.

Memgraph Ltd: Memgraph indexing. https://docs.memgraph.com/memgraph/concepts-overview/indexing. Accessed Sept 2020

43.

Mhedhbi, A., Gupta, P., Khaliq, S., Salihoglu, S.: A+ indexes: lightweight and highly flexible adjacency lists for graph database management systems. CoRR arXiv:2004.00130 (2020)

44.

Neo4j: Neo4j graph platform. https://neo4j.com/. Accessed Jan 2020

45.

Neo4j: Cypher query language. https://neo4j.com/developer/cypher-query-language/. Accessed Nov 2019

46.

Neo4j: Neo4j—indexes for search performance. https://neo4j.com/docs/cypher-manual/current/administration/indexes-for-search-performance/index.html. Accessed Sept 2020

47.

OrientDB: LiveQuery. https://orientdb.com/nosql/livequery/. Accessed July 2020

48.

Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: Bringing order to the web. Tech. rep, Stanford Digital Library Technologies Project (1998)

49.

Peng, P., Zou, L., Chen, L., Zhao, D.: Adaptive distributed RDF graph fragmentation and allocation based on query workload. IEEE Trans. Knowl. Data Eng. 31(4), 670–685 (2019). https://doi.org/10.1109/TKDE.2018.2841389CrossRef

50.

Perliger, A., Pedahzur, A.: Social network analysis in the study of terrorism and political violence. PS Polit. Sci. Polit. 44(1), 45–50 (2011). https://doi.org/10.1017/S1049096510001848CrossRef

51.

Razavi, A., Kontogiannis, K.: Partial evaluation of model transformations. In: Proc. of ICSE’12, pp. 562–572. IEEE Computer Society (2012). https://doi.org/10.1109/ICSE.2012.6227160

52.

Real, E., Shlens, J., , Pan, S.M.X., Vanhoucke, V.: YouTube-BoundingBoxes dataset. https://research.google.com/youtube-bb/. Accessed Oct 2019

53.

Richardson, M., Domingos, P.M.: The intelligent surfer: probabilistic combination of link and content information in PageRank. In: proc. of NIPS’01, pp. 1441–1448. MIT Press (2001)

54.

Szárnyas, G., Izsó, B., Ráth, I., Harmath, D., Bergmann, G., Varró, D.: IncQuery-D: a distributed incremental model query framework in the cloud. In: Proc. of MODELS’14, pp. 653–669 (2014). https://doi.org/10.1007/978-3-319-11653-2_40

55.

Szárnyas, G., Izsó, B., Ráth, I., Varró, D.: The Train Benchmark: cross-technology performance evaluation of continuous model queries. Softw. Syst. Model. 17(4), 1365–1393 (2018). https://doi.org/10.1007/s10270-016-0571-8CrossRef

56.

Szárnyas, G., Marton, J., Maginecz, J., Varró, D.: Reducing property graph queries to relational algebra for incremental view maintenance. CoRR arXiv:1806.07344 (2018)

57.

The New Yorker: Data from the New Yorker caption contest. https://github.com/nextml/caption-contest-data. Accessed Oct 2019

58.

TinkerPop: Apache TinkerGraph. http://tinkerpop.apache.org/docs/current/reference/#tinkergraph-gremlin. Accessed Oct 2019

59.

TinkerPop: TinkerGraph indices. https://tinkerpop.apache.org/javadocs/3.2.2/full/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraph.html#vertexIndex. Accessed Sept 2020

60.

Tinkerpop, A.: Interface vertex program. http://tinkerpop.apache.org/javadocs/3.1.4/core/org/apache/tinkerpop/gremlin/process/computer/VertexProgram.html. Accessed Jan 2020

61.

Troya, J., Wimmer, M., Burgueño, L., Vallecillo, A.: Towards approximate model transformations. In: Proc. of AMT@MoDELS’14, pp. 44–53. CEUR-WS (2014)

62.

Trushkowsky, B., Kraska, T., Franklin, M.J., Sarkar, P.: Crowdsourced enumeration queries. In: Proc. of ICDE’13, pp. 673–684 (2013). https://doi.org/10.1109/ICDE.2013.6544865

63.

Trushkowsky, B., Kraska, T., Franklin, M.J., Sarkar, P.: Answering enumeration queries with the crowd. Commun. ACM 59(1), 118–127 (2016)CrossRef

64.

Ujhelyi, Z., Bergmann, G., Hegedüs, Á., Horváth, Á., Izsó, B., Ráth, I., Szatmári, Z., Varró, D.: EMF-IncQuery: an integrated development environment for live model queries. Sci. Comput. Program. 98, 80–99 (2015). https://doi.org/10.1016/j.scico.2014.01.004CrossRef

65.

Uta, A., Ghit, B., Dave, A., Boncz, P.A.: [Demo] Low-latency spark queries on updatable data. In: Proc. of SIGMOD’19, pp. 2009–2012 (2019). https://doi.org/10.1145/3299869.3320227

66.

W3C RDF Data Access Working Group: SPARQL query language. https://www.w3.org/TR/rdf-sparql-query/. Accessed Jan 2020

67.

Wang, Y., Parthasarathy, S., Sadayappan, P.: Stratification driven placement of complex data: a framework for distributed data analytics. In: Proc. of ICDE’13, pp. 709–720. IEEE Computer Society (2013). https://doi.org/10.1109/ICDE.2013.6544868

68.

Webber, J., Robinson, I., Eifrem, E.: Graph databases. O’Reilly Media (2013)

69.

Wohlin, C., Runeson, P., Höst, M., Ohlsson, M.C., Regnell, B.: Experimentation in Software Engineering. Springer, Berlin (2012)CrossRef

70.

Wood, P.T.: Graph database. In: Liu, L., Özsu, M.T. (eds.) Encyclopedia of Database Systems, 2nd edn. Springer, New York (2018). https://doi.org/10.1007/978-1-4614-8265-9_183CrossRef

71.

Yang, C.C., Ng, T.D.: Terrorism and crime related weblog social network: link, content analysis and information visualization. In: Proc. of ISI’07, pp. 55–58. IEEE (2007). https://doi.org/10.1109/ISI.2007.379533

Title: Improving query performance on dynamic graphs
Authors: Gala Barquero
Javier Troya
Antonio Vallecillo
Publication date: 02-11-2020
Publisher: Springer Berlin Heidelberg
Published in: Software and Systems Modeling / Issue 4/2021
Print ISSN: 1619-1366
Electronic ISSN: 1619-1374
DOI: https://doi.org/10.1007/s10270-020-00832-3

Springer Professional

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 "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 4/2021

Towards a model-driven approach for multiexperience AI-based user interfaces

A technique for evaluating and improving the semantic transparency of modeling language notations

A formal approach to finding inconsistencies in a metamodel

Virtual network embedding: ensuring correctness and optimality by construction using model transformation and integer linear programming techniques

Guest editorial for EMMSAD’2020 special section

Foundations of information technology based on Bunge’s systemist philosophy of reality

Premium Partner