Database Paper Browser

Back to papers

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
9188
Venue
VLDB
Year
2004
Pagerank
7.7002798e-05
Overall Rank
3,018 | 79.01%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank Citing Paper Year Venue Pagerank
1,576 Continuous Nearest Neighbor Monitoring in Road Networks 2006 VLDB 0.00011286717
1,784 Continuous Monitoring of Top-k Queries over Sliding Windows 2006 SIGMOD 0.00010567363
2,360 Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring 2005 SIGMOD 8.9605432e-05
2,989 KLEE: A Framework for Distributed Top-k Query Algorithms 2005 VLDB 7.7733083e-05
4,186 Best Position Algorithms for Top-k Queries 2007 VLDB 6.3764858e-05
6,335 Adaptive Stream Filters for Entity-based Queries with Non-Value Tolerance 2005 VLDB 5.1056594e-05
6,677 Categorical Skylines for Streaming Data 2008 SIGMOD 4.9657435e-05
8,005 Online Topic-Aware Entity Resolution Over Incomplete Data Streams 2021 SIGMOD 4.6081461e-05
9,953 Distributed Stream KNN Join 2021 SIGMOD 4.2405999e-05
12,385 LeeWave: Level-Wise Distribution of Wavelet Coefficients for Processing kNN Queries over Distributed Streams 2008 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

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
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016162015
43 Models and Issues in Data Stream Systems 2002 PODS 0.00072723062
79 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00056242144
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.0004429571
216 A Class of Data Structures for Associative Searching 1984 PODS 0.00033542705
284 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00028994728
2,702 Reverse Nearest Neighbor Aggregates Over Data Streams 2002 VLDB 8.2725214e-05
3,050 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.6512619e-05
3,061 Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches 2000 VLDB 7.6382127e-05
3,300 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.2516103e-05
4,210 Continually Evaluating Similarity-Based Pattern Queries on a Streaming Time Series 2002 SIGMOD 6.3566839e-05
6,342 A Regression-Based Temporal Pattern Mining Scheme for Data Streams 2003 VLDB 5.1034654e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,579 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 6.9502303e-05
1,010 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014652858
1,542 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 0.00011456321
7,239 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB 4.792836e-05
11,554 On the I/O Complexity of the k-Nearest Neighbors Problem 2020 PODS 4.1945683e-05
3,665 Ad-hoc Top-k Query Answering for Data Streams 2007 VLDB 6.8633354e-05
9,953 Distributed Stream KNN Join 2021 SIGMOD 4.2405999e-05
11,207 Closest Pairs Search Over Data Stream 2023 SIGMOD 4.1945683e-05
4,724 Nearest-Neighbor Searching Under Uncertainty 2012 PODS 5.9697823e-05
2,702 Reverse Nearest Neighbor Aggregates Over Data Streams 2002 VLDB 8.2725214e-05