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)

Paper ID: 1483
Venue: PODS
Year: 2009
Pagerank: 5.093636e-05
Overall Rank: 12,488 | 14.33%
DOI: 10.1145/1559795.1559815

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Flavio Chierichetti (Sapienza University)
2. Ravi Kumar (Yahoo)
3. Sergei Vassilvitskii (Yahoo)

BibTeX Citation

@inproceedings{chierichetti_pods09,
        address = {New York, NY, USA},
        series = {{PODS} '09},
        title = {{Similarity Caching}},
        url = {https://dl.acm.org/doi/10.1145/1559795.1559815},
        doi = {10.1145/1559795.1559815},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chierichetti, Flavio and Kumar, Ravi and Vassilvitskii, Sergei},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
135	An Evaluation of Buffer Management Strategies for Relational Database Systems	1985	VLDB	0.00030209257

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,838	Improving Adaptable Similarity Query Processing by Using Approximations	1998	VLDB
2	2,250	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD
3	2,101	A Cost Model for Similarity Queries in Metric Spaces	1998	PODS
4	11,751	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS
5	7,715	Cache-oblivious High-performance Similarity Join	2019	SIGMOD
6	690	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD
7	3,834	Effective Caching of Shortest Paths for Location-Based Services	2012	SIGMOD
8	21	Similarity Search in High Dimensions via Hashing	1999	VLDB
9	7,942	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD
10	5,666	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS