Efficiently Answering Quality Constrained Shortest Distance Queries in Large Graphs
- Publisher:
- Institute of Electrical and Electronics Engineers (IEEE)
- Publication Type:
- Conference Proceeding
- Citation:
- Proceedings - International Conference on Data Engineering, 2023, 2023-April, pp. 856-868
- Issue Date:
- 2023-01-01
Embargoed
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| 2-s2.0-85167718424 AM.pdf | Accepted version | 941.15 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is currently unavailable due to the publisher's embargo.
One of the fundamental concept in the graph-related problem is the shortest path distance. This problem is widely studied for decades, and has numerous real-life applications. Nevertheless, quality constraints are naturally associated with edges. For instance, finding the distance between two vertices along valid edges (i.e., edges that satisfy a given quality constraint) is also critical. To fill this research gap, we investigate this vital problem, i.e., the quality constraint shortest distance problems. An efficient index structure is proposed based on 2-hop labeling approaches. By using a path dominance relationship into both quality and length information, it is demonstrated that the new index could ensure the minimal property. To further speed up the performance, we present an efficient query processing algorithm. Extensive experimental studies over real-life datasets demonstrates efficiency and effectiveness of our techniques.
Please use this identifier to cite or link to this item: