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: ha698e603b9488d7e
Venue: VLDB
Year: 2000
Pagerank: 7.4302233e-05
Overall Rank: 3,320 | 77.68%
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
576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016121388
674	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00014886692
2,939	Approximate NN Queries on Streams with Guaranteed Error/performance Bounds	2004	VLDB	7.8340314e-05
3,016	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.7483267e-05
4,728	Finding Near Neighbors Through Cluster Pruning	2007	PODS	6.4473669e-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	674	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD
2	20	Similarity Search in High Dimensions via Hashing	1999	VLDB
3	802	Near Neighbor Search in Large Metric Spaces	1995	VLDB
4	1,304	Continuous Nearest Neighbor Search	2002	VLDB
5	576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD
6	8,927	Contorting High Dimensional Data for Efficient Main Memory KNN Processing	2003	SIGMOD
7	3,325	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD
8	713	Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan	2016	VLDB
9	2,113	What is the nearest neighbor in high dimensional spaces?	2000	VLDB
10	1,157	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS