E-resources
-
Peng, You; Lin, Xuemin; Zhang, Ying; Zhang, Wenjie; Qin, Lu; Zhou, Jingren
The VLDB journal, 09/2021, Volume: 30, Issue: 5Journal Article
Graph is a ubiquitous structure representing entities and their relationships applied in many areas such as social networks, web graphs, and biological networks. One of the fundamental tasks in graph analytics is to investigate the relations between two vertices (e.g., users, items, and entities) such as how a vertex A influences another vertex B , or to what extent A and B are similar to each other, based on the graph topology structure. For this purpose, we study the problem of hop-constrained s - t simple path enumeration in this paper, which aims to list all simple paths from a source vertex s to a target vertex t with hop-constraint k . We first propose a polynomial delay algorithm, namely BC-DFS, based on a barrier-based pruning technique. Then, a join-oriented algorithm, namely JOIN, is designed to further enhance the query response time. On the theoretical side, BC-DFS is a polynomial delay algorithm with O ( km ) time per output where m is the number of edges in the graph. This time complexity is similar to the best known theoretical result for the polynomial delay algorithms of this problem. On the practical side, our comprehensive experiments on 15 real-life networks demonstrate the superior performance of the BC-DFS algorithm compared to the state-of-the-art techniques. It is also reported that the JOIN algorithm can further significantly enhance the query response time. In this paper, we also study the hop-constrained path enumeration problem with diversity constraint and propose a block-oriented algorithm, namely SCB. To further speed up the computation, hybrid lower bounds based on reverse shortest-path tree are also developed, namely SCB+. The experiments show our proposed methods significantly improve the query time and scalability comparing with baselines.
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
If the library membership card is not in the list,
add a new one.
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|
Source: Personal bibliographies
and: SICRIS
The material is available in full text. If you wish to order the material anyway, click the Continue button.