Influence Sets Based on Reverse Nearest Neighbor Queries

Summary: Formalizes influence sets via reverse nearest neighbor (RNN) queries, a novel, asymmetric notion of influence. Proposes an RNN framework and an efficient R-tree based method for large datasets; experiments on geographic data show logarithmic scaling. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h8bfb3a855cb4ac12
Venue: SIGMOD
Year: 2000
Pagerank: 0.00016599925
Overall Rank: 545 | 96.34%
DOI: 10.1145/342009.335415

Incoming Non-self Citations Over Time

Authors

1. Flip Korn (AT&T)
2. S. Muthukrishnan (AT&T)

BibTeX Citation

@inproceedings{korn_sigmod00,
        title = {{Influence Sets Based on Reverse Nearest Neighbor Queries}},
        author = {Korn, Flip and Muthukrishnan, S.},
        series = {{SIGMOD} '00},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/342009.335415},
        url = {https://dl.acm.org/doi/10.1145/342009.335415},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,477	Efficient Processing of Top-k Spatial Preference Queries	2011	VLDB	0.00010546245
1,571	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010197322
1,650	Continuous Monitoring of Nearest Neighbors on Land Surface	2009	VLDB	9.9739794e-05
1,651	Indexing Land Surface for Efficient kNN Query	2008	VLDB	9.9739794e-05
1,895	Efficient Computation of Reverse Skyline Queries	2007	VLDB	9.4125147e-05
2,407	On Efficient Spatial Matching	2007	VLDB	8.5129142e-05
2,807	On Computing Top-t Most Influential Spatial Sites	2005	VLDB	7.9798533e-05
3,030	Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor	2009	VLDB	7.7340451e-05
3,439	Progressive Computation of the Min-Dist Optimal-Location Query	2006	VLDB	7.2960053e-05
3,776	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	7.0244572e-05
4,548	Identifying the Most Influential Data Objects with Reverse Top-k Queries	2010	VLDB	6.5394775e-05
4,616	Branch-and-Bound Algorithm for Reverse Top-k Queries	2013	SIGMOD	6.4983802e-05
4,799	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD	6.4084993e-05
5,348	FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data	2008	VLDB	6.1698901e-05
5,519	VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries	2010	VLDB	6.0941936e-05
5,916	Reverse k-Ranks Query	2014	VLDB	5.9472799e-05
5,918	Reverse Top-k Search using Random Walk with Restart	2014	VLDB	5.9465067e-05
6,109	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	5.8825187e-05
6,157	On Optimal Worst-Case Matching	2013	SIGMOD	5.8657397e-05
6,834	Maximizing Bichromatic Reverse Spatial and Textual k Nearest Neighbor Queries	2016	VLDB	5.6664572e-05
7,756	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	5.4570169e-05
7,799	Spatially-Decaying Aggregation Over a Network: Model and Algorithms	2004	SIGMOD	5.4490738e-05
7,945	Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN	2009	VLDB	5.4193905e-05
8,409	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	5.3362771e-05
9,298	A General Framework for Modeling and Processing Optimization Queries	2007	VLDB	5.1997281e-05
9,338	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB	5.1898547e-05
10,091	On m-Impact Regions and Standing Top-k Influence Problems	2021	SIGMOD	5.0806786e-05
10,772	RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem	2026	VLDB	4.9769913e-05
11,671	Expanding Reverse Nearest Neighbors	2024	VLDB	4.9769913e-05
12,569	PLASMA-HD: Probing the LAttice Structure and MAkeup of High-dimensional Data	2013	VLDB	4.9769913e-05
12,760	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0019923528
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011402175
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051292389
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045319457
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029048509
839	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.0001354488
1,552	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010270215

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,760	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB
2	8,409	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB
3	10,839	RNSG: A Range-Aware Graph Index for Efficient Range-Filtered Approximate Nearest Neighbor Search	2026	VLDB
4	3,776	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
5	28	Nearest Neighbor Queries	1995	SIGMOD
6	1,571	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB
7	2,634	Reverse Nearest Neighbor Aggregates Over Data Streams	2002	VLDB
8	6,109	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB
9	1,700	Discovery of Influence Sets in Frequently Updated Databases	2001	VLDB
10	2,807	On Computing Top-t Most Influential Spatial Sites	2005	VLDB