Similarity Caching
Summary: Introduce similarity caching: a metric-space caching variant where a query is a hit if some cached point lies within radius r, optimizing misses under competitive analysis. Prove intractability without extra power, then quantify hardness across metrics (general → bounded doubling → Euclidean) and study variable r and miss–similarity trade-offs. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 2 of 2 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 34 | Similarity Search in High Dimensions via Hashing | 1999 | VLDB | 0.00076637636 |
| 128 | An Evaluation of Buffer Management Strategies for Relational Database Systems | 1985 | VLDB | 0.00044535268 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,882 | Improving Adaptable Similarity Query Processing by Using Approximations | 1998 | VLDB | 5.2892937e-05 |
| 2,742 | Cache-Efficient Aggregation: Hashing Is Sorting | 2015 | SIGMOD | 8.1906104e-05 |
| 1,811 | A Cost Model for Similarity Queries in Metric Spaces | 1998 | PODS | 0.00010467197 |
| 11,554 | On the I/O Complexity of the k-Nearest Neighbors Problem | 2020 | PODS | 4.1945683e-05 |
| 709 | Efficient Similarity Search and Classification via Rank Aggregation | 2003 | SIGMOD | 0.00017768547 |
| 7,765 | Cache-oblivious High-performance Similarity Join | 2019 | SIGMOD | 4.6572085e-05 |
| 4,111 | Effective Caching of Shortest Paths for Location-Based Services | 2012 | SIGMOD | 6.4427171e-05 |
| 34 | Similarity Search in High Dimensions via Hashing | 1999 | VLDB | 0.00076637636 |
| 7,522 | Efficient and Tunable Similar Set Retrieval | 2001 | SIGMOD | 4.7180617e-05 |
| 8,763 | Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search | 2015 | PODS | 4.456315e-05 |