Spatial Queries with Two kNN Predicates

Summary: Extends spatial query processing to two kNN predicates (two kNN-selects, two kNN-joins, or a join+select), introducing conceptually correct QEPs and novel optimization algorithms. Experiments show orders-of-magnitude speedups over naive plans, demonstrating practical efficiency for complex location-based queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10537
Venue: VLDB
Year: 2012
Pagerank: 5.3904242e-05
Overall Rank: 8,659 | 40.60%
DOI: 10.14778/2350229.2350231

Incoming Non-self Citations Over Time

Authors

1. Ahmed M. Aly (Purdue University)
2. Walid G. Aref (Purdue University)
3. Mourad Ouzzani (Qatar Computing Research Institute)

BibTeX Citation

@article{aly_vldb12,
        title = {{Spatial Queries with Two kNN Predicates}},
        author = {Aly, Ahmed M. and Aref, Walid G. and Ouzzani, Mourad},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {11},
        pages = {1100--1111},
        doi = {10.14778/2350229.2350231},
        url = {https://doi.org/10.14778/2350229.2350231},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,080	Processing Moving kNN Queries Using Influential Neighbor Sets	2015	VLDB	5.3251649e-05
11,850	Top-k Queries over Digital Traces	2019	SIGMOD	5.093636e-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
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
28	Nearest Neighbor Queries	1995	SIGMOD	0.00052102434
1,201	SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases	2004	SIGMOD	0.00011674339
1,620	Continuous Nearest Neighbor Monitoring in Road Networks	2006	VLDB	0.00010206305
5,405	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	6.2291247e-05
12,442	SimDB: A Similarity-aware Database System	2010	SIGMOD	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,681	Discovery of Influence Sets in Frequently Updated Databases	2001	VLDB
2	9,356	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB
3	3,462	Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates	2003	VLDB
4	1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
5	2,205	Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring	2005	SIGMOD
6	3,581	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD
7	665	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB
8	449	Query Processing in Spatial Network Databases	2003	VLDB
9	3,562	Location-based Spatial Queries	2003	SIGMOD
10	1,441	Efficient Processing of Top-k Spatial Preference Queries	2011	VLDB