Span-reachability querying in large temporal graphs

Wen, D; Yang, B; Zhang, Y; Qin, L; Cheng, D; Zhang, W

Span-reachability querying in large temporal graphs

Wen, D Yang, B Zhang, Y

Qin, L

Cheng, D Zhang, W

Permalink

Publisher:: Springer Science and Business Media LLC
Publication Type:: Journal Article
Citation:: VLDB Journal, 2021, pp. 1-19
Issue Date:: 2021-01-01

Closed Access

	Filename	Description	Size
	Span.pdf	Published version	963.2 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Wen, D
dc.contributor.author	Yang, B
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062
dc.contributor.author	Cheng, D
dc.contributor.author	Zhang, W
dc.date.accessioned	2022-01-29T01:10:09Z
dc.date.available	2022-01-29T01:10:09Z
dc.date.issued	2021-01-01
dc.identifier.citation	VLDB Journal, 2021, pp. 1-19
dc.identifier.issn	1066-8888
dc.identifier.issn	0949-877X
dc.identifier.uri	http://hdl.handle.net/10453/153780
dc.description.abstract	Reachability is a fundamental problem in graph analysis. In applications such as social networks and collaboration networks, edges are always associated with timestamps. Most existing works on reachability queries in temporal graphs assume that two vertices are related if they are connected by a path with non-decreasing timestamps (time-respecting) of edges. This assumption fails to capture the relationship between entities involved in the same group or activity with no time-respecting path connecting them. In this paper, we define a new reachability model, called span-reachability, designed to relax the time order dependency and identify the relationship between entities in a given time period. We adopt the idea of two-hop cover and propose an index-based method to answer span-reachability queries. Several optimizations are also given to improve the efficiency of index construction and query processing. We conduct extensive experiments on eighteen real-world datasets to show the efficiency of our proposed solution.
dc.language	en
dc.publisher	Springer Science and Business Media LLC
dc.relation	http://purl.org/au-research/grants/arc/FT170100128
dc.relation	http://purl.org/au-research/grants/arc/DP180103096
dc.relation	http://purl.org/au-research/grants/arc/DP210101393
dc.relation	http://purl.org/au-research/grants/arc/DP210101347
dc.relation	http://purl.org/au-research/grants/arc/FT200100787
dc.relation.ispartof	VLDB Journal
dc.relation.isbasedon	10.1007/s00778-021-00715-z
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	0804 Data Format, 0805 Distributed Computing, 0806 Information Systems
dc.subject.classification	Information Systems
dc.title	Span-reachability querying in large temporal graphs
dc.type	Journal Article
utslib.for	0804 Data Format
utslib.for	0805 Distributed Computing
utslib.for	0806 Information Systems
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	closed_access	*
dc.date.updated	2022-01-29T01:10:08Z
pubs.publication-status	Published

Abstract:

Reachability is a fundamental problem in graph analysis. In applications such as social networks and collaboration networks, edges are always associated with timestamps. Most existing works on reachability queries in temporal graphs assume that two vertices are related if they are connected by a path with non-decreasing timestamps (time-respecting) of edges. This assumption fails to capture the relationship between entities involved in the same group or activity with no time-respecting path connecting them. In this paper, we define a new reachability model, called span-reachability, designed to relax the time order dependency and identify the relationship between entities in a given time period. We adopt the idea of two-hop cover and propose an index-based method to answer span-reachability queries. Several optimizations are also given to improve the efficiency of index construction and query processing. We conduct extensive experiments on eighteen real-world datasets to show the efficiency of our proposed solution.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/153780