Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor

Summary: MaxBRNN: locate a region that maximizes BRNNs. MaxOverlap: an efficient algorithm that exploits problem structure to avoid exponential search, delivering orders-of-magnitude speedups over prior methods; validated on server placement problems. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h1fc48990f77b3a48
Venue: VLDB
Year: 2009
Pagerank: 7.737708e-05
Overall Rank: 3,029 | 79.64%
DOI: 10.14778/1687627.1687754

Incoming Non-self Citations Over Time

Authors

1. Raymond Chi-Wing Wong (Hong Kong University of Science and Technology)
2. M. Tamer Özsu (University of Waterloo)
3. Philip S. Yu (University of Illinois Chicago)
4. Ada Wai-Chee Fu (Chinese University of Hong Kong)
5. Lian Liu (Hong Kong University of Science and Technology)

BibTeX Citation

@article{wong_vldb09,
        title = {{Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor}},
        author = {Wong, Raymond Chi-Wing and Özsu, M. Tamer and Yu, Philip S. and Fu, Ada Wai-Chee and Liu, Lian},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687754},
        url = {https://doi.org/10.14778/1687627.1687754},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,085	A Scalable Algorithm for Maximizing Range Sum in Spatial Databases	2012	VLDB	7.6629324e-05
3,781	Approximate MaxRS in Spatial Databases	2013	VLDB	7.0249074e-05
4,547	Identifying the Most Influential Data Objects with Reverse Top-k Queries	2010	VLDB	6.5425744e-05
6,155	On Optimal Worst-Case Matching	2013	SIGMOD	5.8685178e-05
6,815	Efficient Algorithms for Optimal Location Queries in Road Networks	2014	SIGMOD	5.6735074e-05
6,830	Maximizing Bichromatic Reverse Spatial and Textual k Nearest Neighbor Queries	2016	VLDB	5.6691409e-05
7,742	Towards Best Region Search for Data Exploration	2016	SIGMOD	5.4614459e-05
10,762	RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem	2026	VLDB	4.9793485e-05
11,665	Expanding Reverse Nearest Neighbors	2024	VLDB	4.9793485e-05
12,181	The Maximum Trajectory Coverage Query in Spatial Databases	2019	VLDB	4.9793485e-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
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
545	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016607433
1,700	Discovery of Influence Sets in Frequently Updated Databases	2001	VLDB	9.8424892e-05
2,367	Capacity Constrained Assignment in Spatial Databases	2008	SIGMOD	8.5623448e-05
2,406	On Efficient Spatial Matching	2007	VLDB	8.5169461e-05
2,806	On Computing Top-t Most Influential Spatial Sites	2005	VLDB	7.9836326e-05
3,439	Progressive Computation of the Min-Dist Optimal-Location Query	2006	VLDB	7.2994607e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,892	Efficient Computation of Reverse Skyline Queries	2007	VLDB
2	3,774	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
3	2,806	On Computing Top-t Most Influential Spatial Sites	2005	VLDB
4	74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB
5	1,571	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB
6	9,525	Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates	2015	SIGMOD
7	2,406	On Efficient Spatial Matching	2007	VLDB
8	3,320	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB
9	6,155	On Optimal Worst-Case Matching	2013	SIGMOD
10	6,830	Maximizing Bichromatic Reverse Spatial and Textual k Nearest Neighbor Queries	2016	VLDB