FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data

Summary: FINCH enables reverse k-NN evaluation on 2D location data by tightening the RkNN search region. INCH computes the initial region; FINCH tightens it as results arrive, and a universal reduction extends to bichromatic RkNN, with efficiency gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9927
Venue: VLDB
Year: 2008
Pagerank: 6.1289238e-05
Overall Rank: 5,664 | 61.15%
DOI: 10.14778/1454159.1454162

Incoming Non-self Citations Over Time

Authors

1. Wei Wu (National University of Singapore)
2. Fei Yang (National University of Singapore)
3. Chee-Yong Chan (National University of Singapore)
4. Kian-Lee Tan (National University of Singapore)

BibTeX Citation

@article{wu_vldb08,
        title = {{FINCH: Evaluating Reverse k-Nearest-Neighbor Queries on Location Data}},
        author = {Wu, Wei and Yang, Fei and Chan, Chee-Yong and Tan, Kian-Lee},
        journal = {PVLDB},
        series = {{VLDB} '08},
        volume = {1},
        number = {2},
        pages = {1056--1067},
        doi = {10.14778/1454159.1454162},
        url = {https://doi.org/10.14778/1454159.1454162},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,711	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD	6.5506926e-05
8,760	Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN	2009	VLDB	5.3766157e-05
9,165	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB	5.3101672e-05
9,356	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	5.282937e-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.0020210012
28	Nearest Neighbor Queries	1995	SIGMOD	0.00052102434
546	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016734556
560	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016525569
1,612	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010218134
1,681	Discovery of Influence Sets in Frequently Updated Databases	2001	VLDB	0.00010022485
3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD	7.1780127e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,927	Neighbor-Sensitive Hashing	2016	VLDB
2	6,561	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB
3	546	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD
4	4,711	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD
5	3,118	Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor	2009	VLDB
6	7,378	Maximizing Bichromatic Reverse Spatial and Textual k Nearest Neighbor Queries	2016	VLDB
7	3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
8	9,165	Dimensional Testing for Reverse k-Nearest Neighbor Search	2017	VLDB
9	9,356	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB
10	1,612	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB