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/2020

13-02-2020

Cluster query: a new query pattern on temporal knowledge graph

Authors: Jinjing Huang, Wei Chen, An Liu, Weiqing Wang, Hongzhi Yin, Lei Zhao

Published in: World Wide Web | Issue 2/2020

Log in

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

search-config
loading …

Abstract

A temporal knowledge graph (TKG) is theoretically a temporal graph. Recently, systems have been developed to support snapshot queries over temporal graphs. However, snapshot queries can only give separate answers. To retrieve forward-backward correlation facts from temporal knowledge graph, cluster query is proposed in this paper. To deal with the query, the logical view and physical model are presented. Subsequently, five corresponding basic query patters of unit matching are studied, and then the complete matchings are also addressed. To improve the query performance, index-based methods and pruning strategies are adopted. Experiments are conducted to evaluate cluster queries on three real datasets. The experimental results show the effectiveness and efficiency of cluster queries on temporal knowledge graphs.
previous article A relationship extraction method for domain knowledge graph construction
next article Semi-supervised clustering with deep metric learning and graph embedding

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
Literature
1.
Bollacker, K. D., Cook, R. P., Tufts, P.: Freebase: A shared database of structured general human knowledge. In: Proceedings of the 22nd conference on artificial intelligence (AAAI), pp. 1962–1963 (2007)
2.
3.
Suchanek, F. M., Kasneci, G., Weikum, G.: Yago: A core of semantic knowledge. In: Proceedings of the 16th international conference on World Wide Web (WWW), p.p 697–706 (2007)
4.
Bizer, C., Lehmann, J., Kobilarov, G., Auer, S., Becker, C., Cyganiak, R., Hellmann, S.: Dbpedia - a crystallization point for the web of data Web Semantics: Science. Services and Agents on the World Wide Web 7(3), 154–165 (2009)CrossRef
5.
Gutierrez, C., Hurtado, C. A., Vaisman, A. A.: Temporal RDF. In: Proceedings of the 2nd European semantic Web conference (ESWC), pp. 93–107 (2005)
6.
Gutierrez, C., Hurtado, C. A., Vaisman, A. A.: Introducing time into RDF. IEEE Transaction on Knowledge and Data Engineering 19(2), 207–218 (2007)CrossRef
7.
Dylla, M., Sozio, M., Theobald, M.: Resolving temporal conflicts in inconsistent RDF knowledge bases. In: Proceedings of Datenbanksysteme für Business, Technologie und Web (BTW), pp. 474–493 (2011)
8.
Dylla, M., Miliaraki, I., Theobald, M.: A temporal-probabilistic database model for information extraction. PVLDB 6(14), 1810–1821 (2013)
9.
Chekol, M. W., Pirro, G., Schoenfisch, J., Stuckenschmidt, H.: Marring uncertainty and time in knowledge graphs. In: Proceedings of the 31st AAAI conference on artificial intelligence (AAAI), pp 88–94 (2017)
10.
Trivedi, R., Dai, H., Wang, Y., Song, L.: Know-evolve: Deep temporal reasoning for dynamic knowledge graphs. In: proceedings of the 34th international conference on machine learning (ICML), pp. 3462–3471 (2017)
11.
Zhao, Y., Zheng, K., Li, Y., Su, H., Liu, J., Zhou, X.: Destination-aware task assignment in spatial crowdsourcing: A worker decomposition approach. IEEE Transactions on Knowledge and Data Engineering (2019)
12.
Lian, D., Zheng, K., Ge, Y., Cao, L., Chen, E., Xie, X.: Geomf++:, Scalable location recommendation via joint geographical modeling and matrix factorization. ACM Trans. Inf. Syst. 36(3), 33:1–33:29 (2018)CrossRef
13.
Zheng, K., Zhao, Y., Lian, D., Zheng, B., Liu, G., Zhou, X.: Reference-based framework for spatio-temporal trajectory compression and query processing. IEEE Trans. Knowl. Data Eng. 05, 1–1 (2019)
14.
Li, L., Zheng, K., Wang, S., Hua, W., Zhou, X.: Go slow to go fast: minimal on-road time route scheduling with parking facilities using historical trajectory. VLDB J. 27(3), 321–345 (2018)CrossRef
15.
Zheng, B., Su, H., Hua, W., Zheng, K., Zhou, X., Li, G.: Efficient clue-based route search on road networks. IEEE Trans. Knowl Data Eng. 29 (9), 1846–1859 (2017)CrossRef
16.
Pėrez, J., Arenas, M., Gutierrez, C.: Semantics and complexity of SPARQL. ACM Trans. Database Syst. 34(3), 16:1–16:45 (2009)CrossRef
17.
Quilitz, B., Leser, U.: Querying distributed RDF data sources with SPARQL. In: Proceedings of the 5th European semantic Web conference (ESWC), pp. 524–538 (2008)
18.
Abadi, D. J., Marcus, A., Madden, S., Hollenbach, K.: Sw-store: A vertically partitioned DBMS for semantic web data management. The VLDB J. 18(2), 385–406 (2009)CrossRef
19.
Wu, B., Zhou, Y., Yuan, P., Liu, L., Jin, H.: Scalable SPARQL querying using path partitioning. In: Proceedings of the 31st IEEE international conference on data engineering (ICDE), pp. 795–806 (2015)
20.
Abdelaziz, I., Harbi, R., Khayyat, Z., Kalnis, P.: A survey and experimental comparison of distributed SPARQL engines for very large RDF data. PVLDB 10(13), 2049–2060 (2017)
21.
Angles, R., Gutierrez, C.: Querying RDF data from a graph database perspective. In: Proceedings of the 2nd European semantic Web conference (ESWC), pp. 346–360 (2005)
22.
Zou, L., Tamer Ȯzsu, M., Chen, L., Shen, X., Huang, R., Zhao, D.: gstore: a graph-based SPARQL query engine. The VLDB Journal 23(4), 565–590 (2014)CrossRef
23.
Yang, S., Han, F., Wu, Y., Yan, X.: Fast top-k search in knowledge graphs. In: Proceedings of the 32nd IEEE international conference on data engineering (ICDE), pp. 990–1001 (2016)
24.
Yahya, M., Barbosa, D., Berberich, K., Wang, Q., Weikum, G.: Relationship queries on extended knowledge graphs. In: Proceedings of the 9th ACM international conference on web search and data mining (WSDM), pp. 605–614 (2016)
25.
Jayaram, N., Gupta, M., Khan, A., Li, C., Yan, X., Elmasri, R.: GQBE: querying knowledge graphs by example entity tuples. In: Proceedings of the 30th IEEE international conference on data engineering (ICDE), pp. 1250–1253 (2014)
26.
Zheng, W., Lian, X., Zou, L., Hong, L., Zhao, D.: Online subgraph skyline analysis over knowledge graphs. IEEE Trans Knowl Data Eng 28(7), 1805–1819 (2016)CrossRef
27.
Yahya, M., Berberich, K., Ramanath, M., Weikum, G.: Exploratory querying of extended knowledge graphs. PVLDB 9(13), 1521–1524 (2016)
28.
Cheng, J., Yu, J. X., Ding, B., Yu, P. S., Wang, H.: Fast graph pattern matching. In: Proceedings of the 24th international conference on data engineering (ICDE), pp. 913–922 (2008)
29.
Zou, L., Chen, L., Ȯzsu, M.T.: Distancejoin: Pattern match query in a large graph database. PVLDB 2(1), 886–897 (2009)
30.
Lee, J., Han, W., Kasperovics, R., Lee, J.: An in-depth comparison of subgraph isomorphism algorithms in graph databases. PVLDB 6(2), 133–144 (2012)
31.
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)
32.
Ma, S., Cao, Y., Fan, W., Huai, J., Wo, T.: Strong simulation: Capturing topology in graph pattern matching. ACM Trans. Database Syst. 39(1), 4:1–4:46 (2014)MathSciNetCrossRef
33.
Song, C., Ge, T., Chen, C. X., Wang, J.: Event pattern matching over graph streams. PVLDB 8(4), 413–424 (2014)
34.
Xu, Y., Huang, J., Liu, A., Li, Z., Yin, H., Zhao, L.: Time-constrained graph pattern matching in a large temporal graph. In: Proceedings of the the 1st international joint conference on web and big data (APWEB-WAIM), pp. 100–115 (2017)
35.
Zheng, K., Zheng, Y., Yuan, N. J., Shang, S., Zhou, X.: Online discovery of gathering patterns over trajectories. IEEE Trans. Knowl Data Eng. 26(8), 1974–1988 (2014)CrossRef
36.
Liu, G., Liu, Y., Zheng, K., Liu, A., Li, Z., Wang, Y., Zhou, X.: MCS-GPM: multi-constrained simulation based graph pattern matching in contextual social graphs. IEEE Trans. Knowl. Data Eng. 30(6), 1050–1064 (2018)CrossRef
37.
Allen, J. F.: Maintaining knowledge about temporal intervals. Commun. ACM 26(11), 832–843 (1983)CrossRef
38.
Lee, J., Clifton, C. W.: Top-k frequent itemsets via differentially private fp-trees. In: The 20th ACM SIGKDD international conference on knowledge discovery and data mining(KDD), pp. 931–940 (2014)
39.
Cordella, L. P., Foggia, P., Sansone, C., Vento, M.: A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach Intell. 26(10), 1367–1372 (2004)CrossRef
40.
He, H., Singh, A. K.: Graphs-at-a-time: query language and access methods for graph databases. In: Proceedings of the ACM SIGMOD international conference on management of data, SIGMOD 2008, Vancouver, BC, Canada, June 10-12, 2008, pp. 405–418 (2008)
Metadata
Title
Cluster query: a new query pattern on temporal knowledge graph
Authors
Jinjing Huang
Wei Chen
An Liu
Weiqing Wang
Hongzhi Yin
Lei Zhao
Publication date
13-02-2020
Publisher
Springer US
Published in
World Wide Web / Issue 2/2020
Print ISSN: 1386-145X
Electronic ISSN: 1573-1413
DOI
https://doi.org/10.1007/s11280-019-00754-1

Other articles of this Issue 2/2020

World Wide Web 2/2020 Go to the issue

EditorialNotes

Preface to the Special Issue on Graph Data Management in Online Social Networks

OriginalPaper

From crowdsourcing to crowdmining: using implicit human intelligence for better understanding of crowdsourced data

OriginalPaper

Misinformation-oriented expert finding in social networks

OriginalPaper

Fault tolerant data transmission reduction method for wireless sensor networks

OriginalPaper

Three-hop velocity attenuation propagation model for influence maximization in social networks

OriginalPaper

A QoS-aware virtual machine scheduling method for energy conservation in cloud-based cyber-physical systems

Premium Partner

    Image Credits