Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring

Summary: Introduces conceptual partitioning (CPM) for continuous k-NN monitoring in dynamic data. CPM prunes updates to near-query objects, supports many static/moving queries, and extends to aggregate NN (ANN) with improved throughput. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hbf7876376b336f63
Venue: SIGMOD
Year: 2005
Pagerank: 8.7678247e-05
Overall Rank: 2,243 | 84.93%
DOI: 10.1145/1066157.1066230

Incoming Non-self Citations Over Time

Authors

1. Kyriakos Mouratidis (Hong Kong University of Science and Technology)
2. Marios Hadjieleftheriou (Boston University)
3. Dimitris Papadias (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{mouratidis_sigmod05,
        title = {{Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring}},
        author = {Mouratidis, Kyriakos and Hadjieleftheriou, Marios and Papadias, Dimitris},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066230},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066230},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,439	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD	0.00010642846
1,652	Continuous Nearest Neighbor Monitoring in Road Networks	2006	VLDB	9.9778734e-05
1,768	The New Casper: Query Processing for Location Services without Compromising Privacy	2006	VLDB	9.6873901e-05
2,194	Monitoring Path Nearest Neighbor in Road Networks	2009	SIGMOD	8.8805644e-05
3,731	An Efficient Query Indexing Mechanism for Filtering Geo-Textual Data	2013	SIGMOD	7.0676307e-05
4,134	ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree Index for Moving Objects	2008	SIGMOD	6.787575e-05
4,141	Behavioral Simulations in MapReduce	2010	VLDB	6.7841596e-05
4,769	Nearest Neighbor Search with Strong Location Privacy	2010	VLDB	6.4253006e-05
4,837	An Experimental Analysis of Iterated Spatial Joins in Main Memory	2013	VLDB	6.3872905e-05
5,346	A General Framework for Geo-Social Query Processing	2013	VLDB	6.1695636e-05
5,749	Efficient Proximity Detection among Mobile Users via Self-Tuning Policies	2010	VLDB	6.0076091e-05
7,941	Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN	2009	VLDB	5.4219572e-05
8,001	Processing and Optimizing Main Memory Spatial-Keyword Queries	2016	VLDB	5.4092483e-05
8,369	Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing	2023	VLDB	5.3450708e-05
9,313	Processing Proximity Relations in Road Networks	2010	SIGMOD	5.1961681e-05
11,722	Closest Pairs Search Over Data Stream	2023	SIGMOD	4.9793485e-05
12,654	FIFO Indexes for Decomposable Problems	2011	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051312804
1,227	SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases	2004	SIGMOD	0.000114264
1,700	Discovery of Influence Sets in Frequently Updated Databases	2001	VLDB	9.8424892e-05
2,631	Reverse Nearest Neighbor Aggregates Over Data Streams	2002	VLDB	8.1996438e-05
2,939	Approximate NN Queries on Streams with Guaranteed Error/performance Bounds	2004	VLDB	7.8340314e-05
3,638	Location-based Spatial Queries	2003	SIGMOD	7.1446219e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,635	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
2	10,326	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
3	1,650	Continuous Monitoring of Nearest Neighbors on Land Surface	2009	VLDB
4	7,289	Continuous Obstructed Nearest Neighbor Queries in Spatial Databases	2009	SIGMOD
5	8,820	Spatial Queries with Two kNN Predicates	2012	VLDB
6	11,240	Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search	2025	VLDB
7	1,304	Continuous Nearest Neighbor Search	2002	VLDB
8	7,941	Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN	2009	VLDB
9	1,652	Continuous Nearest Neighbor Monitoring in Road Networks	2006	VLDB
10	3,522	Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates	2003	VLDB