Skyline nearest neighbor search on multi-layer graphs
- Publisher:
- IEEE
- Publication Type:
- Conference Proceeding
- Citation:
- Proceedings - 2019 IEEE 35th International Conference on Data Engineering Workshops, ICDEW 2019, 2019, pp. 259-265
- Issue Date:
- 2019-04-01
Closed Access
Filename | Description | Size | |||
---|---|---|---|---|---|
08750910.pdf | Published version | 217.08 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© 2019 IEEE. Nearest neighbor search is a fundamental problem in graph theory. In real-world applications, the multi-layer graph model is extensively studied to reveal the multi-dimensional relations between the graph entities. In this paper, we formulate a new problem named skyline nearest neighbor search on multi-layer graphs. Given a query vertex u, we aim to compute a set of skyline vertices that are not dominated by other vertices in terms of the shortest distance on all graph layers. We propose an early-termination algorithm instead of naively adopting the traditional skyline procedure as a subroutine. We also investigate the rule to optimize search order in the algorithm and further improve the algorithmic efficiency. The experimental results demonstrate that the optimization strategies work well on different graphs and can speed up the algorithm significantly.
Please use this identifier to cite or link to this item: