Random Sampling from Hash Files

Summary: Evaluates random sampling from hash files on storage across static (open addressing, overflow chains) and dynamic hash schemes (Linear/Extendible). Iterative and batch sampling; analyzes cost by successful search; dynamic hashing boosts sampling efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h445bb258c1b7c1eb
Venue: SIGMOD
Year: 1990
Pagerank: 0.00011420642
Overall Rank: 1,229 | 91.74%
DOI: 10.1145/93597.98746

Incoming Non-self Citations Over Time

Authors

1. Frank Olken (Lawrence Berkeley National Laboratory)
2. Doron Rotem (Lawrence Berkeley National Laboratory)
3. Ping Xu (San Francisco State University)

BibTeX Citation

@inproceedings{olken_sigmod90,
        title = {{Random Sampling from Hash Files}},
        author = {Olken, Frank and Rotem, Doron and Xu, Ping},
        series = {{SIGMOD} '90},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/93597.98746},
        url = {https://dl.acm.org/doi/10.1145/93597.98746},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
220	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00024344086
489	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017441895
1,090	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012077577
1,460	Online Maintenance of Very Large Random Samples on Flash Storage	2008	VLDB	0.0001058438
1,467	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00010567959
2,322	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.6361485e-05
4,217	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD	6.7271293e-05
4,313	Density Biased Sampling: An Improved Method for Data Mining and Clustering	2000	SIGMOD	6.6699869e-05
7,527	Algebraic Optimization of Computations over Scientific Databases	1993	VLDB	5.5016558e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040035279
181	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026389403
477	Random Sampling from B+ trees	1989	VLDB	0.00017632787
1,110	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB	0.00011984945
1,416	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010734049

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,023	Distribution-Dependent Hashing Functions and Their Characteristics	1975	SIGMOD
2	5,265	External Perfect Hashing	1985	SIGMOD
3	477	Random Sampling from B+ trees	1989	VLDB
4	2,862	Concurrency and Linear Hashing	1985	PODS
5	5,707	A Mapping Function for the Directory of a Multidimensional Extendible Hashing	1984	VLDB
6	13,532	A Dynamic Perfect Hash Function Defined by an Extended Hash Indicator Table	1984	VLDB
7	2,799	Unified Dynamic Hashing	1984	VLDB
8	9,155	Hashing in Practice, Analysis of Hashing and Universal Hashing	1988	SIGMOD
9	8,546	A Dynamic Hash File for Random and Sequential Accessing	1983	VLDB
10	3,929	A Single-File Version of Linear Hashing with Partial Expansions	1982	VLDB