Influence sets based on reverse nearest neighbor queries

By Flip Korn, S. Muthu Muthukrishnan. ACM SIGMOD Conference, 2000

592 citations recorded by the source corpus.

Inherent in the operation of many decision support and continuous referral systems is the notion of the “influence” of a data point on the database. This notion arises in examples such as finding the set of customers affected by the opening of a new store outlet location, notifying the subset of subscribers to a digital library who will find a newly added document most relevant, etc. Standard approaches to determining the influence set of a data point involve range searching and nearest neighbor queries. In this paper, we formalize a novel notion of influence based on reverse neighbor queries and its variants. Since the nearest neighbor relation is not symmetric, the set of points that are closest to a query point (i.e., the nearest neighbors) differs from the set of points that have the query point as their nearest neighbor (called the reverse nearest neighbors). Influence sets based on reverse nearest neighbor (RNN) queries seem to capture the intuitive notion of influence from our motivating examples. We present a general approach for solving RNN queries and an efficient R-tree based method for large data sets, based on this approach. Although the RNN query appears to be natural, it has not been studied previously. RNN queries are of independent interest, and as such should be part of the suite of available queries for processing spatial and multimedia data. In our experiments with real geographical data, the proposed method appears to scale logarithmically, whereas straightforward sequential scan scales linearly. Our experimental study also shows that approaches based on range searching or nearest neighbors are ineffective at finding influence sets of our interest.

Subfields: Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/e09b02bd8a479e4184141b6504a35db61e2cb057

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Reverse kNN Search in Arbitrary Dimensionality (2004, methodology): “Because the RNN-tree is optimized for RNN, but not NN search, Korn and Muthukrishnan [ KM00 ] use an additional (conventional) R-tree on the data points for nearest neighbors and other spatial queries.”
Continuous Nearest Neighbor Search (2002, methodology): “Practical examples of RNN query are provided in [5].”
Nearest neighbor and reverse nearest neighbor queries for moving objects (2002, methodology): “Yang and Lin [25] improve the solution of Korn and Muthukrishnan by introducing the Rdnn-tree, which makes possible to answer both RNN queries and NN queries using a single tree.”
Nearest-Neighbor Searching and Metric Space Dimensions (2005, background): “This problem has arisen as a computational bottleneck in event-driven astrophysical simulations [AT01], and as a notion of “influence” in decision support and referral systems[ KM00 , SFcT03].”
Ranking Outliers Using Symmetric Neighborhood Relationship (2006, methodology): “To get a better estimation of the neighborhood’s density distribution, we propose to take both the nearest neighbors (NNs) and reverse nearest neighbors (RNNs) [14] into account.”
Efficient Computation of Reverse Skyline Queries (2007, methodology): “RNN-tree is optimized for RNN, but not NN search, the authors in [13] propose to use two trees: (1) a traditional”
Unsupervised incremental learning of deep descriptors from video streams (2017, methodology): “We solved this problem by performing descriptor matching according to Reverse Nearest Neighbour (ReNN) [23]:”
On Trip Planning Queries in Spatial Databases (2005, background): “Most research has concentrated on traditional spatial queries and their variants, namely range queries [20], nearest neighbors [15, 21, 31], continuous nearest neighbors [5, 39, 43], group nearest neighbors [28], reverse nearest neighbors [24], etc.”
Deep learning in video multi-object tracking: A survey (2019, methodology): “In [70], the authors reused the visual features extracted by the CNN-based detector, and the association was performed using a Reverse Nearest Neighbor technique [102].”