Approximate NN Queries on Streams with Guaranteed Error/performance Bounds

Summary: Introduces e-approximate kNN (ekNN) on data streams with an absolute error bound on the k-th distance. Proposes DISC, adaptive space-filling-curve indexing that trades memory for accuracy in streaming workloads, with fast updates and strong empirical validation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9379
Venue: VLDB
Year: 2004
Pagerank: 7.9957585e-05
Overall Rank: 2,886 | 80.21%
DOI: 10.1016/B978-012088469-8.50071-1

Incoming Non-self Citations Over Time

Authors

1. Nick Koudas (AT&T)
2. Beng Chin Ooi (National University of Singapore)
3. Kian-Lee Tan (National University of Singapore)
4. Rui Zhang (National University of Singapore)

BibTeX Citation

@article{koudas_vldb04,
        title = {{Approximate NN Queries on Streams with Guaranteed Error/performance Bounds}},
        author = {Koudas, Nick and Ooi, Beng Chin and Tan, Kian-Lee and Zhang, Rui},
        journal = {PVLDB},
        series = {{VLDB} '04},
        pages = {804--815},
        doi = {10.1016/B978-012088469-8.50071-1},
        url = {https://doi.org/10.1016/B978-012088469-8.50071-1},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,513	Continuous Monitoring of Top-k Queries over Sliding Windows	2006	SIGMOD	0.00010530872
1,620	Continuous Nearest Neighbor Monitoring in Road Networks	2006	VLDB	0.00010206305
2,205	Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring	2005	SIGMOD	8.9591376e-05
2,813	KLEE: A Framework for Distributed Top-k Query Algorithms	2005	VLDB	8.0975254e-05
3,702	Best Position Algorithms for Top-k Queries	2007	VLDB	7.1838636e-05
6,616	Categorical Skylines for Streaming Data	2008	SIGMOD	5.8214223e-05
7,027	Adaptive Stream Filters for Entity-based Queries with Non-Value Tolerance	2005	VLDB	5.7231968e-05
8,105	Online Topic-Aware Entity Resolution Over Incomplete Data Streams	2021	SIGMOD	5.4860105e-05
10,102	Distributed Stream KNN Join	2021	SIGMOD	5.1488731e-05
12,578	LEE WAVE: Level-Wise Distribution of Wavelet Coefficients for Processing kNN Queries over Distributed Streams	2008	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 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.001157935
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052982574
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044853085
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
253	A Class of Data Structures for Associative Searching	1984	PODS	0.00023200431
277	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00022537944
2,587	Reverse Nearest Neighbor Aggregates Over Data Streams	2002	VLDB	8.3747444e-05
2,979	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.8984588e-05
3,150	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.7055991e-05
3,282	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB	7.5667715e-05
3,920	Continually Evaluating Similarity-Based Pattern Queries on a Streaming Time Series	2002	SIGMOD	7.0171134e-05
6,305	A Regression-Based Temporal Pattern Mining Scheme for Data Streams	2003	VLDB	5.9204295e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,363	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD
2	1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
3	705	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB
4	6,133	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB
5	11,751	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS
6	3,317	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB
7	10,102	Distributed Stream KNN Join	2021	SIGMOD
8	11,408	Closest Pairs Search Over Data Stream	2023	SIGMOD
9	4,850	Nearest-Neighbor Searching Under Uncertainty	2012	PODS
10	2,587	Reverse Nearest Neighbor Aggregates Over Data Streams	2002	VLDB