Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches

Summary: Introduces contrast plots and P-sphere trees for NN search, targeting “good” high-dimensional data where sublinear search is feasible. Offers a tunable space–time tradeoff with performance predictable from a data characteristic, including variants outperforming alternatives. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 8859
Venue: VLDB
Year: 2000
Pagerank: 7.5667715e-05
Overall Rank: 3,282 | 77.49%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Jonathan Goldstein (Microsoft)
2. Raghu Ramakrishnan (University of Wisconsin)

BibTeX Citation

@article{goldstein_vldb00,
        title = {{Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches}},
        author = {Goldstein, Jonathan and Ramakrishnan, Raghu},
        journal = {PVLDB},
        series = {{VLDB} '00},
        pages = {429--440},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
581	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016153395
690	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.0001492934
2,886	Approximate NN Queries on Streams with Guaranteed Error/performance Bounds	2004	VLDB	7.9957585e-05
2,979	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.8984588e-05
4,657	Finding Near Neighbors Through Cluster Pruning	2007	PODS	6.5830079e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	690	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD
2	21	Similarity Search in High Dimensions via Hashing	1999	VLDB
3	784	Near Neighbor Search in Large Metric Spaces	1995	VLDB
4	1,281	Continuous Nearest Neighbor Search	2002	VLDB
5	581	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD
6	8,765	Contorting High Dimensional Data for Efficient Main Memory KNN Processing	2003	SIGMOD
7	3,363	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD
8	805	Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan	2016	VLDB
9	2,158	What is the nearest neighbor in high dimensional spaces?	2000	VLDB
10	1,137	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS