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: h1fbd80ea7a4e65d2
Venue: VLDB
Year: 2004
Pagerank: 7.8340314e-05
Overall Rank: 2,939 | 80.25%
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,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
2,243	Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring	2005	SIGMOD	8.7678247e-05
2,874	KLEE: A Framework for Distributed Top-k Query Algorithms	2005	VLDB	7.9221111e-05
3,656	Best Position Algorithms for Top-k Queries	2007	VLDB	7.1256193e-05
6,745	Categorical Skylines for Streaming Data	2008	SIGMOD	5.6908052e-05
7,168	Adaptive Stream Filters for Entity-based Queries with Non-Value Tolerance	2005	VLDB	5.5947893e-05
8,282	Online Topic-Aware Entity Resolution Over Incomplete Data Streams	2021	SIGMOD	5.3629192e-05
10,329	Distributed Stream KNN Join	2021	SIGMOD	5.0333462e-05
12,868	LEE WAVE: Level-Wise Distribution of Wavelet Coefficients for Processing kNN Queries over Distributed Streams	2008	VLDB	4.9793485e-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.0011405675
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052121228
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.0004503446
90	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00034860244
264	A Class of Data Structures for Associative Searching	1984	PODS	0.00022757762
279	The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries	1997	SIGMOD	0.00022308048
2,631	Reverse Nearest Neighbor Aggregates Over Data Streams	2002	VLDB	8.1996438e-05
3,016	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.7483267e-05
3,211	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.536045e-05
3,320	Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches	2000	VLDB	7.4302233e-05
4,003	Continually Evaluating Similarity-Based Pattern Queries on a Streaming Time Series	2002	SIGMOD	6.8604652e-05
6,432	A Regression-Based Temporal Pattern Mining Scheme for Data Streams	2003	VLDB	5.78833e-05

Semantically Similar Papers

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