On efficiently finding reverse k-nearest neighbors over uncertain graphs

Reverse k -nearest neighbor ( R k NN ) 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 ou...

Full description

Saved in:
Bibliographic Details
Published in:The VLDB journal 2017-08, Vol.26 (4), p.467-492
Main Authors: Gao, Yunjun, Miao, Xiaoye, Chen, Gang, Zheng, Baihua, Cai, Deng, Cui, Huiyong
Format: Article
Language:English
Subjects:
Adaptive algorithms
Adaptive sampling
Complexity
Computer Science
Cost engineering
Database Management
Graph theory
Graphs
Marketing
Networks
Regular Paper
Resource allocation
Searching
Traffic engineering
Traffic models
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Reverse k -nearest neighbor ( R k NN ) 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 R k NN 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 reverse k - nearest neighbor search on uncertain graphs ( UG-R k NN search for short), where graph edges contain uncertainty. First, to address UG-R k NN 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-R k NN retrieval by seamlessly integrating the three heuristics together. In view of the high complexity of UG-R k NN 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.
ISSN:1066-8888
0949-877X
DOI:10.1007/s00778-017-0460-y