Density Biased Sampling: An Improved Method for Data Mining and Clustering

Summary: Density biased sampling under-samples dense regions and over-samples sparse ones, preserving original densities with weighted samples. Single-pass, memory-efficient algorithm; uniform sampling is a special case, with up to 6× gains on Zipf-like clusters for mining and clustering. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3175
Venue: SIGMOD
Year: 2000
Pagerank: 6.3835403e-05
Overall Rank: 4,177 | 70.95%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Christopher R. Palmer
2. Christos Faloutsos

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,404	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS	8.8837279e-05
2,789	Optimal Sampling from Sliding Windows	2009	PODS	8.1249652e-05
3,654	Using Trees to Depict a Forest	2009	VLDB	6.873144e-05
6,883	C2P: Clustering based on Closest Pairs	2001	VLDB	4.8960306e-05
7,759	Dscaler: Synthetically Scaling A Given Relational Database	2016	VLDB	4.6593145e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
14	Online Aggregation	1997	SIGMOD	0.0010801504
33	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00077324389
59	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064501896
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036625711
341	CURE: An Efficient Clustering Algorithm for Large Databases	1998	SIGMOD	0.00026810548
638	On B-tree Indices for Skewed Distributions	1992	VLDB	0.00018798677
783	Random Sampling from Hash Files	1990	SIGMOD	0.00016704834
5,982	Modeling skewed distributions using multifractals and the '80-20 law'	1996	VLDB	5.2446136e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,324	Clustering Stream Data by Exploring the Evolution of Density Mountain	2018	VLDB	5.5691645e-05
5,065	Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search	2002	SIGMOD	5.7247716e-05
1,816	Incremental Clustering for Mining in a Data Warehousing Environment	1998	VLDB	0.0001045313
6,019	Uncertain Centroid based Partitional Clustering of Uncertain Data	2012	VLDB	5.2415551e-05
11,466	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.1945683e-05
4,350	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.2645054e-05
7,890	Mining a Search Engine’s Corpus: Efficient Yet Unbiased Sampling and Aggregate Estimation	2011	SIGMOD	4.6249533e-05
3,264	Dynamic Density Based Clustering	2017	SIGMOD	7.3094408e-05
1,860	Approximation Algorithms for Clustering Uncertain Data	2008	PODS	0.0001028857
3,313	Quality and Efficiency in Kernel Density Estimates for Large Data	2013	SIGMOD	7.2381634e-05