Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
World Wide Web
Published in: World Wide Web 2/2023

07-10-2022

FPIRPQ: Accelerating regular path queries on knowledge graphs

Authors: Xin Wang, Wenqi Hao, Yuzhou Qin, Baozhu Liu, Pengkai Liu, Yanyan Song, Qingpeng Zhang, Xiaofei Wang

Published in: World Wide Web | Issue 2/2023

Log in

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

search-config
loading …

Abstract

With the growing popularity and application of knowledge-based artificial intelligence, the scale of knowledge graph data is dramatically increasing. As an essential type of query for RDF graphs, Regular Path Queries (RPQs) have attracted increasing research efforts, which explore RDF graphs in a navigational manner. Moreover, path indexes have proven successful for semi-structured data management. However, few techniques can be used effectively in practice for processing RPQ on large-scale knowledge graphs. In this paper, we propose a novel indexing solution named FPIRPQ (Frequent Path Index for Regular Path Queries) by leveraging Frequent Path Mining (FPM). Unlike the existing approaches to RPQs processing, FPIRPQ takes advantage of frequent paths, which are statistically derived from the data to accelerate RPQs. Furthermore, since there is no explicit benchmark targeted for RPQs over RDF graph yet, we design a micro-benchmark including 12 basic queries over synthetic and real-world datasets. The experimental results illustrate that FPIRPQ improves the query efficiency by up to orders of magnitude compared to the state-of-the-art RDF storage engine.
previous article Learning refined features for open-world text classification with class description and commonsense knowledge
next article What have we learned from OpenReview?

Dont have a licence yet? Then find out more about our products and how to get one 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 "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
Footnotes
Literature
1.
Ernst, P., Meng, C., Siu, A., Weikum, G.: Knowlife: A knowledge graph for health and life sciences. IEEE Computer Society (2014)
2.
Shi, L., Li, S., Yang, X., Qi, J., Pan, G., Zhou, B.: Semantic health knowledge graph: semantic integration of heterogeneous medical knowledge and services. BioMed research international 2017 (2017)
3.
Rotmensch, M., Halpern, Y., Tlimat, A., Horng, S., Sontag, D.: Learning a health knowledge graph from electronic medical records. Scientific Reports 7(1), 1–11 (2017)CrossRef
4.
Liu, J., Lu, Z., Du, W.: Combining enterprise knowledge graph and news sentiment analysis for stock price prediction. In: Proceedings of the 52nd Hawaii International Conference on System Sciences (2019)
5.
Ulicny, B.: Constructing knowledge graphs with trust. In: 4Th International Workshop on Methods for Establishing Trust of (Open) Data, Bentlehem, USA (2015)
6.
Chen, P., Lu, Y., Zheng, V.W., Chen, X., Yang, B.: Knowedu: a system to construct knowledge graph for education. Ieee Access 6, 31553–31563 (2018)CrossRef
7.
Grévisse, C., Manrique, R., Mariño, O., Rothkugel, S.: Knowledge graph-based teacher support for learning material authoring. In: Colombian Conference on Computing, pp 177–191. Springer (2018)
8.
Consortium, W.W.W., et al.: Rdf 1.1 concepts and abstract syntax (2014)
9.
Consortium, W.W.W., et al.: Sparql 1.1 query language (2013)
10.
Kostylev, E.V., Reutter, J.L., Romero, M., Vrgoč, D.: Sparql with property paths. In: International Semantic Web Conference, pp 3–18. Springer (2015)
11.
Wang, X., Wang, S., Xin, Y., Yang, Y., Li, J., Wang, X.: Distributed pregel-based provenance-aware regular path query processing on rdf knowledge graphs. World Wide Web, 1–32 (2019)
12.
Liu, B., Wang, X., Liu, P., Li, S., Wang, X.: Pairpq: An efficient path index for regular path queries on knowledge graphs. In: Asia-Pacific Web (APWeb) and Web-Age Information Management (WAIM) Joint International Conference on Web and Big Data, pp 106–120. Springer (2021)
13.
Yan, X., Han, J.: gspan: Graph-based substructure pattern mining. In: 2002 IEEE International Conference on Data Mining, 2002. Proceedings, pp 721–724. IEEE (2002)
14.
Holder, L.B., Cook, D.J., Djoko, S., et al.: Substucture discovery in the subdue system. In: KDD Workshop, pp. 169–180, Washington, DC, USA (1994)
15.
Ghazizadeh, S., Chawathe, S.S.: Seus: Structure extraction using summaries. In: International Conference on Discovery Science, pp 71–85. Springer (2002)
16.
Goldman, R., Widom, J.: Dataguides: Enabling Query Formulation and Optimization in Semistructured Databases. Technical report, Stanford (1997)
17.
18.
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to automata theory, languages, and computation. Acm Sigact News 32(1), 60–65 (2001)CrossRefMATH
19.
Milo, T., Suciu, D.: Index structures for path expressions. In: International Conference on Database Theory, pp 277–295. Springer (1999)
20.
Kaushik, R., Shenoy, P., Bohannon, P., Gudes, E.: Exploiting local similarity for indexing paths in graph-structured data. In: Proceedings 18th International Conference on Data Engineering, pp 129–140. IEEE (2002)
21.
Chen, Q., Lim, A., Ong, K.W.: D (k)-index: An adaptive structural summary for graph-structured data. In: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, pp 134–144 (2003)
22.
He, H., Yang, J.: Multiresolution indexing of xml for frequent queries. In: Proceedings. 20th International Conference on Data Engineering, pp 683–694. IEEE (2004)
23.
Erling, O., Mikhailov, I.: Rdf support in the virtuoso dbms. In: Networked Knowledge-Networked Media, pp 7–24. Springer (2009)
24.
Das, S., Agrawal, D., El Abbadi, A.: G-store: A scalable data store for transactional multi key access in the cloud. In: Proceedings of the 1st ACM Symposium on Cloud Computing, pp 163–174 (2010)
25.
Liu, B., Wang, X., Liu, P., Li, S., Zhang, X., Yang, Y.: Knowledge graph database system with unified model and query languages. Ruan Jian Xue Bao/Journal of Software (in Chinese) 32(3), 781–804 (2021)
26.
27.
Zhu, F., Qu, Q., Lo, D., Yan, X., Han, J., Yu, P.S.: Mining top-k large structural patterns in a massive network. Proceedings of the VLDB Endowment 4(11), 807–818 (2011)CrossRef
28.
Vanetik, N., Gudes, E., Shimony, S.E.: Computing frequent graph patterns from semistructured data. In: 2002 IEEE International Conference on Data Mining, 2002. Proceedings., pp. 458–465. IEEE (2002)
29.
Bonifati, A., Martens, W., Timm, T.: An analytical study of large sparql query logs. VLDB J. 29(2), 655–679 (2020)CrossRef
30.
Guo, Y., Pan, Z., Heflin, J.: Lubm: a benchmark for owl knowledge base systems. Journal of Web Semantics 3(2-3), 158–182 (2005)CrossRef
31.
Lehmann, J., Isele, R., Jakob, M., Jentzsch, A., Kontokostas, D., Mendes, P.N., Hellmann, S., Morsey, M., Van Kleef, P., Auer, S., et al.: Dbpedia–a large-scale, multilingual knowledge base extracted from wikipedia. Semantic Web 6(2), 167–195 (2015)CrossRef
Metadata
Title
FPIRPQ: Accelerating regular path queries on knowledge graphs
Authors
Xin Wang
Wenqi Hao
Yuzhou Qin
Baozhu Liu
Pengkai Liu
Yanyan Song
Qingpeng Zhang
Xiaofei Wang
Publication date
07-10-2022
Publisher
Springer US
Published in
World Wide Web / Issue 2/2023
Print ISSN: 1386-145X
Electronic ISSN: 1573-1413
DOI
https://doi.org/10.1007/s11280-022-01103-5

Other articles of this Issue 2/2023

World Wide Web 2/2023 Go to the issue

OriginalPaper

Influence-Aware Successive Point-of-Interest Recommendation

OriginalPaper

A text and GNN based controversy detection method on social media

Editorial

Guest Editorial: WWWJ Special Issue of the 22th International Conference on Web Information Systems Engineering (WISE 2021)

OriginalPaper

Multi-task hourglass network for online automatic diagnosis of developmental dysplasia of the hip

OriginalPaper

Improving medical experts’ efficiency of misinformation detection: an exploratory study

OriginalPaper

Learning refined features for open-world text classification with class description and commonsense knowledge

Premium Partner

    Image Credits