Publication Type
Journal Article
Version
acceptedVersion
Publication Date
8-2017
Abstract
Reverse k-nearest neighbor (RkNN) query on graphs returns the data objects that take a specified query object q as one of their k-nearest neighbors. It has significant influence in many real-life applications including resource allocation and profile-based marketing. However, to the best of our knowledge, there is little previous work on RkNN search over uncertain graph data, even though many complex networks such as traffic networks and protein–protein interaction networks are often modeled as uncertain graphs. In this paper, we systematically study the problem of reversek-nearest neighbor search on uncertain graphs (UG-RkNN search for short), where graph edges contain uncertainty. First, to address UG-RkNN search, we propose three effective heuristics, i.e., GSP, EGR, and PBP, which minimize the original large uncertain graph as a much smaller essential uncertain graph, cut down the number of possible graphs via the newly introduced graph conditional dominance relationship, and reduce the validation cost of data nodes in order to improve query efficiency. Then, we present an efficient algorithm, termed as SDP, to support UG-RkNN retrieval by seamlessly integrating the three heuristics together. In view of the high complexity of UG-RkNN search, we further present a novel algorithm called TripS, with the help of an adaptive stratified sampling technique. Extensive experiments using both real and synthetic graphs demonstrate the performance of our proposed algorithms.
Keywords
uncertain graph, RkNN search, stratified sampling, querying processing
Discipline
Databases and Information Systems
Research Areas
Data Science and Engineering
Publication
VLDB Journal
Volume
26
Issue
4
First Page
467
Last Page
492
ISSN
1066-8888
Identifier
10.1007/s00778-017-0460-y
Publisher
Springer Verlag (Germany)
Citation
GAO, Yunjun; MIAO, Xiaoye; CHEN, Gang; ZHENG, Baihua; CAI, Deng; and CUI, Huiyong.
On efficiently finding reverse K-nearest neighbors over uncertain graphs. (2017). VLDB Journal. 26, (4), 467-492.
Available at: https://ink.library.smu.edu.sg/sis_research/3708
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org./10.1007/s00778-017-0460-y