A survey of typical attributed graph queries
- PDF / 3,125,633 Bytes
- 50 Pages / 439.642 x 666.49 pts Page_size
- 71 Downloads / 198 Views
A survey of typical attributed graph queries Yanhao Wang1 · Yuchen Li2 · Ju Fan3 · Chang Ye2 · Mingke Chai3 Received: 21 March 2020 / Revised: 27 July 2020 / Accepted: 25 September 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Graphs are commonly used for representing complex structures such as social relationships, biological interactions, and knowledge bases. In many scenarios, graphs not only represent topological relationships but also store the attributes that denote the semantics associated with their vertices and edges, known as attributed graphs. Attributed graphs can meet demands for a wide range of applications, and thus a variety of queries on attributed graphs have been proposed. However, these diverse types of attributed graph queries have not been systematically investigated yet. In this paper, we provide an extensive survey of several typical types of attributed graph queries. We propose a taxonomy of attributed graph queries based on query inputs and outputs. We summarize the definitions of queries that fall into each category and present a fine-grained classification of queries within each category by analyzing the semantics and algorithmic motivations behind these queries. Moreover, we discuss the insights of how existing studies address the technical challenges of query processing and outline several promising future research directions. Keywords Attributed graph · Knowledge base · Query definition · Query processing · Taxonomy · Survey
1 Introduction Due to the rising complexity of data generated in the big data era, numerous applications have ubiquitously used graphs for storing complex information. Generally, a graph consists of a set of vertices (a.k.a. nodes) representing the entities and edges representing the relationships between entities. Furthermore, many real-world graphs known as attributed
Electronic supplementary material The online version of this article (https://doi.org/10.1007/s11280-020-00849-0) contains supplementary material, which is available to authorized users. Ju Fan
[email protected]
Extended author information available on the last page of the article.
World Wide Web
graphs associate the vertices and edges with attributes, e.g., types, numbers, and texts1 , to capture rich knowledge embedded in the graph structure. To extract information from attributed graphs, an extensive number of queries with different semantics have been proposed to meet the demand for a diverse range of applications. Some examples are listed as follows. –
–
–
Social networks can be seen as attributed graphs: users are vertices and their profiles are vertex attributes; user relationships are edges and the information about the relationships (e.g., type and strength) constitutes edge attributes. For relationship discovery, one may issue a query to find how two persons A and B are connected, e.g., “What is the shortest path from A to B through online interactions?. To analyze the relationships between different user groups, we may need a summary to a
Data Loading...
