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: 3176
Venue: SIGMOD
Year: 2000
Pagerank: 6.3768049e-05
Overall Rank: 4,177 | 70.98%
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,403	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS	8.8738166e-05
2,807	Optimal Sampling from Sliding Windows	2009	PODS	8.096649e-05
3,651	Using Trees to Depict a Forest	2009	VLDB	6.8727613e-05
6,892	C2P: Clustering based on Closest Pairs	2001	VLDB	4.8889412e-05
7,760	Dscaler: Synthetically Scaling A Given Relational Database	2016	VLDB	4.6548456e-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.0010813443
33	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00077399244
60	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064450997
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
340	CURE: An Efficient Clustering Algorithm for Large Databases	1998	SIGMOD	0.00026854084
639	On B-tree Indices for Skewed Distributions	1992	VLDB	0.00018782897
764	Random Sampling from Hash Files	1990	SIGMOD	0.00016958917
5,967	Modeling skewed distributions using multifractals and the '80-20 law'	1996	VLDB	5.247088e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,061	Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search	2002	SIGMOD	5.717245e-05
1,803	Incremental Clustering for Mining in a Data Warehousing Environment	1998	VLDB	0.00010481475
10,280	FB*: A Compact Index for Efficient and Exact Density-based Clustering	2026	VLDB	4.1905499e-05
6,023	Uncertain Centroid based Partitional Clustering of Uncertain Data	2012	VLDB	5.2365238e-05
11,469	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.1905499e-05
4,347	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.2588401e-05
7,890	Mining a Search Engine’s Corpus: Efficient Yet Unbiased Sampling and Aggregate Estimation	2011	SIGMOD	4.6205184e-05
3,078	Dynamic Density Based Clustering	2017	SIGMOD	7.6041723e-05
1,863	Approximation Algorithms for Clustering Uncertain Data	2008	PODS	0.00010287379
3,220	Quality and Efficiency in Kernel Density Estimates for Large Data	2013	SIGMOD	7.3590708e-05