Weighted random assignments with application to hashing

Andrew Chi Chih Yao

doi:10.1007/3-540-54945-5_47

Weighted random assignments with application to hashing

Andrew Chi Chih Yao

Faculty of Electronic and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In this talk we will study the optimal solution to a class of random assignment problems with dependent weights. The result is then used to show that, in double hashing, the expected retrieval cost with respect to an optimal static hash table is O(1) even if the table is full. This confirms a conjecture of Gonnet and Munro (SIAM J. on Computing 8 (1979), 463-478).

Original language	English
Title of host publication	ISA 1991 Algorithms - 2nd International Symposium on Algorithms, Proceedings
Editors	R.C.T. Lee, Wen-Lian Hsu
Publisher	Springer Verlag
ISBN (Print)	9783540549451
DOIs	https://doi.org/10.1007/3-540-54945-5_47
State	Published - 1991
Event	2nd Annual International Symposium on Algorithms, ISA 1991 - Taipei, China Duration: 16 Dec 1991 → 18 Dec 1991

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	557 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	2nd Annual International Symposium on Algorithms, ISA 1991
Country/Territory	China
City	Taipei
Period	16/12/91 → 18/12/91

Access to Document

10.1007/3-540-54945-5_47

Cite this

Yao, A. C. C. (1991). Weighted random assignments with application to hashing. In R. C. T. Lee, & W.-L. Hsu (Eds.), ISA 1991 Algorithms - 2nd International Symposium on Algorithms, Proceedings (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 557 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-54945-5_47

@inproceedings{1e28b83d9a114c1eb6412c5dd4aca684,

title = "Weighted random assignments with application to hashing",

abstract = "In this talk we will study the optimal solution to a class of random assignment problems with dependent weights. The result is then used to show that, in double hashing, the expected retrieval cost with respect to an optimal static hash table is O(1) even if the table is full. This confirms a conjecture of Gonnet and Munro (SIAM J. on Computing 8 (1979), 463-478).",

author = "Yao, \{Andrew Chi Chih\}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1991.; 2nd Annual International Symposium on Algorithms, ISA 1991 ; Conference date: 16-12-1991 Through 18-12-1991",

year = "1991",

doi = "10.1007/3-540-54945-5\_47",

language = "英语",

isbn = "9783540549451",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

editor = "R.C.T. Lee and Wen-Lian Hsu",

booktitle = "ISA 1991 Algorithms - 2nd International Symposium on Algorithms, Proceedings",

}

Yao, ACC 1991, Weighted random assignments with application to hashing. in RCT Lee & W-L Hsu (eds), ISA 1991 Algorithms - 2nd International Symposium on Algorithms, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 557 LNCS, Springer Verlag, 2nd Annual International Symposium on Algorithms, ISA 1991, Taipei, China, 16/12/91. https://doi.org/10.1007/3-540-54945-5_47

Weighted random assignments with application to hashing. / Yao, Andrew Chi Chih.
ISA 1991 Algorithms - 2nd International Symposium on Algorithms, Proceedings. ed. / R.C.T. Lee; Wen-Lian Hsu. Springer Verlag, 1991. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 557 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Weighted random assignments with application to hashing

AU - Yao, Andrew Chi Chih

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1991.

PY - 1991

Y1 - 1991

N2 - In this talk we will study the optimal solution to a class of random assignment problems with dependent weights. The result is then used to show that, in double hashing, the expected retrieval cost with respect to an optimal static hash table is O(1) even if the table is full. This confirms a conjecture of Gonnet and Munro (SIAM J. on Computing 8 (1979), 463-478).

AB - In this talk we will study the optimal solution to a class of random assignment problems with dependent weights. The result is then used to show that, in double hashing, the expected retrieval cost with respect to an optimal static hash table is O(1) even if the table is full. This confirms a conjecture of Gonnet and Munro (SIAM J. on Computing 8 (1979), 463-478).

UR - https://www.scopus.com/pages/publications/85031285612

U2 - 10.1007/3-540-54945-5_47

DO - 10.1007/3-540-54945-5_47

M3 - 会议稿件

AN - SCOPUS:85031285612

SN - 9783540549451

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

BT - ISA 1991 Algorithms - 2nd International Symposium on Algorithms, Proceedings

A2 - Lee, R.C.T.

A2 - Hsu, Wen-Lian

PB - Springer Verlag

T2 - 2nd Annual International Symposium on Algorithms, ISA 1991

Y2 - 16 December 1991 through 18 December 1991

ER -

Weighted random assignments with application to hashing

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this