TY - GEN
T1 - On the statistical dependencies of coalesced hashing and their implications for both full and limited independence
AU - Siegel, Alan
N1 - Funding Information:
Supported in part by NSF grants CCR-8906949 and CCR-9204202
Funding Information:
by NSF grants
PY - 1995/1/22
Y1 - 1995/1/22
N2 - This paper gives the first optimal bounds for coalesced hashing schemes in the case of limited randomness, and thereby establishes the analytic performance of these schemes in a model that supports formal randomized computation. As a byproduct of this work, we attain a much simpler analysis of coalesced hashing schemes, which provides more information about the statistics of the underlying processes. We present the generating functions that govern the chain distribution and probe performance for coalesced hashing schemes, including asymptotic formulations when cellars are used.
AB - This paper gives the first optimal bounds for coalesced hashing schemes in the case of limited randomness, and thereby establishes the analytic performance of these schemes in a model that supports formal randomized computation. As a byproduct of this work, we attain a much simpler analysis of coalesced hashing schemes, which provides more information about the statistics of the underlying processes. We present the generating functions that govern the chain distribution and probe performance for coalesced hashing schemes, including asymptotic formulations when cellars are used.
UR - http://www.scopus.com/inward/record.url?scp=85039799045&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85039799045&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85039799045
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 10
EP - 19
BT - Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
PB - Association for Computing Machinery
T2 - 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
Y2 - 22 January 1995 through 24 January 1995
ER -