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
9189
Venue
VLDB
Year
2004
Pagerank
7.6995792e-05
Overall Rank
3,018 | 79.03%
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,580 Continuous Nearest Neighbor Monitoring in Road Networks 2006 VLDB 0.00011272266
1,773 Continuous Monitoring of Top-k Queries over Sliding Windows 2006 SIGMOD 0.00010600438
2,342 Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring 2005 SIGMOD 9.0005088e-05
2,992 KLEE: A Framework for Distributed Top-k Query Algorithms 2005 VLDB 7.7661927e-05
4,178 Best Position Algorithms for Top-k Queries 2007 VLDB 6.3757762e-05
6,337 Adaptive Stream Filters for Entity-based Queries with Non-Value Tolerance 2005 VLDB 5.1008035e-05
6,680 Categorical Skylines for Streaming Data 2008 SIGMOD 4.960978e-05
8,008 Online Topic-Aware Entity Resolution Over Incomplete Data Streams 2021 SIGMOD 4.6037276e-05
9,952 Distributed Stream KNN Join 2021 SIGMOD 4.236537e-05
12,393 LeeWave: Level-Wise Distribution of Wavelet Coefficients for Processing kNN Queries over Distributed Streams 2008 VLDB 4.1905499e-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.0016113151
43 Models and Issues in Data Stream Systems 2002 PODS 0.00072660894
78 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00056385781
129 The X-tree: An Index Structure for High-Dimensional Data 1996 VLDB 0.00044255276
217 A Class of Data Structures for Associative Searching 1984 PODS 0.00033533621
301 The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries 1997 SIGMOD 0.00028396714
2,698 Reverse Nearest Neighbor Aggregates Over Data Streams 2002 VLDB 8.2763494e-05
3,062 Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches 2000 VLDB 7.6348035e-05
3,123 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.5270618e-05
3,301 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.2450912e-05
4,210 Continually Evaluating Similarity-Based Pattern Queries on a Streaming Time Series 2002 SIGMOD 6.3509527e-05
6,339 A Regression-Based Temporal Pattern Mining Scheme for Data Streams 2003 VLDB 5.0989397e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,574 Efficient k-NN Search on Vertically Decomposed Data 2002 SIGMOD 6.9520978e-05
1,535 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 0.00011461371
1,013 HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces 2018 VLDB 0.00014632051
7,235 Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search 2025 VLDB 4.7882389e-05
11,558 On the I/O Complexity of the k-Nearest Neighbors Problem 2020 PODS 4.1905499e-05
3,665 Ad-hoc Top-k Query Answering for Data Streams 2007 VLDB 6.8631567e-05
9,952 Distributed Stream KNN Join 2021 SIGMOD 4.236537e-05
11,209 Closest Pairs Search Over Data Stream 2023 SIGMOD 4.1905499e-05
4,721 Nearest-Neighbor Searching Under Uncertainty 2012 PODS 5.9647585e-05
2,698 Reverse Nearest Neighbor Aggregates Over Data Streams 2002 VLDB 8.2763494e-05