Influence Sets Based on Reverse Nearest Neighbor Queries Flip Korn and S. Muthukrishnan   View Paper (PDF)   Return to Research Sessions Abstract 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. References Note: References link to DBLP on the Web. [1] ... [2] Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger : The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990 : 322-331 [3] Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger : Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993 : 237-246 [4] Bernard Chazelle , Leonidas J. Guibas : Fractional Cascading: I. A Data Structuring Technique. Algorithmica 1(2) : 133-162(1986) [5] Keinosuke Fukunaga , Patrenahalli M. Narendra : A Branch and Bound Algorithms for Computing k-nearest Neighbors. IEEE TC 24(7) : 750-753(1975) [6] Volker Gaede , Oliver Günther : Multidimensional Access Methods. Computing Surveys 30(2) : 170-231(1998) [7] Antonin Guttman : R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984 : 47-57 [8] Gisli R. Hjaltason , Hanan Samet : Incremental Distance Join Algorithms for Spatial Databases. SIGMOD Conference 1998 : 237-248 [9] Gisli R. Hjaltason , Hanan Samet : Distance Browsing in Spatial Databases. TODS 24(2) : 265-318(1999) [10] Kamal Jain , Vijay V. Vazirani : Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems. FOCS 1999 : 2-13 [11] David G. Kirkpatrick : Optimal Search in Planar Subdivisions. SIAM J. Comput. 12(1) : 28-35(1983) [12] Flip Korn , Nikolaos Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas : Fast Nearest Neighbor Search in Medical Image Databases. VLDB 1996 : 215-226 [13] Bernd-Uwe Pagel , Hans-Werner Six , Heinrich Toben , Peter Widmayer : Towards an Analysis of Range Query Performance in Spatial Data Structures. PODS 1993 : 214-221 [14] Madhukar R. Korupolu , C. Greg Plaxton , Rajmohan Rajaraman : Analysis of a Local Search Heuristic for Facility Location Problems. SODA 1998 : 1-10 [15] Nick Roussopoulos , Stephen Kelley , Frédéic Vincent : Nearest Neighbor Queries. SIGMOD Conference 1995 : 71-79 [16] Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos : The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987 : 507-518 [17] ... BIBTEX @inproceedings{DBLP:conf/sigmod/KornM00,   author    = {Flip Korn and                 S. Muthukrishnan},    editor    = {Weidong Chen and                 Jeffrey F. Naughton and                 Philip A. Bernstein},    title     = {Influence Sets Based on Reverse Nearest Neighbor Queries},    booktitle = {Proceedings of the 2000 ACM SIGMOD International Conference on                 Management of Data, May 16-18, 2000, Dallas, Texas, USA},    journal   = {SIGMOD Record},    publisher = {ACM},    volume    = {29},    number    = {2},    year      = {2000},    isbn      = {1-58113-218-2},    pages     = {201-212},    crossref  = {DBLP:conf/sigmod/2000},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.