Non-oblivious hashing

Amos Fiat; Moni Naor; Jeanette P. Schmidt; Alan Siegel

doi:10.1145/62212.62248

Non-oblivious hashing

Amos Fiat, Moni Naor, Jeanette P. Schmidt, Alan Siegel

Computer Science

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

Abstract

Non-oblivious hashing, where the information gathered by performing "unsuccessful" probes determines the probe strategy, is introduced and used to obtain the following results for static lookup on full tables: a. An 0(1) worst case scheme that requires only logarithmic additional memory (improving on the [FKS84] linear space upper bound). b. An almost sure 0(1) probabilistic worst case scheme, without any additional memory (improving on previous logarithmic time upper bounds). c. Enhancements to hashing: Solving (a) and (b) in the multikey record environment, search can be performed under any key in time 0(1); finding the nearest neighbor, the rank, etc. in logarithmic time. Our non-oblivious upper bounds are much better than the appropriate oblivious lower bounds.

Original language	English (US)
Title of host publication	Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988
Publisher	Association for Computing Machinery
Pages	367-376
Number of pages	10
ISBN (Print)	0897912640, 9780897912648
DOIs	https://doi.org/10.1145/62212.62248
State	Published - 1988
Event	20th Annual ACM Symposium on Theory of Computing, STOC 1988 - Chicago, IL, United States Duration: May 2 1988 → May 4 1988

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0737-8017

Other

Other	20th Annual ACM Symposium on Theory of Computing, STOC 1988
Country/Territory	United States
City	Chicago, IL
Period	5/2/88 → 5/4/88

ASJC Scopus subject areas

Software

Access to Document

10.1145/62212.62248

Cite this

Fiat, A, Naor, M, Schmidt, JP & Siegel, A 1988, Non-oblivious hashing. in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 367-376, 20th Annual ACM Symposium on Theory of Computing, STOC 1988, Chicago, IL, United States, 5/2/88. https://doi.org/10.1145/62212.62248

@inproceedings{75cc67b09b7e4d83aab5886ff54c6247,

title = "Non-oblivious hashing",

abstract = "Non-oblivious hashing, where the information gathered by performing {"}unsuccessful{"} probes determines the probe strategy, is introduced and used to obtain the following results for static lookup on full tables: a. An 0(1) worst case scheme that requires only logarithmic additional memory (improving on the [FKS84] linear space upper bound). b. An almost sure 0(1) probabilistic worst case scheme, without any additional memory (improving on previous logarithmic time upper bounds). c. Enhancements to hashing: Solving (a) and (b) in the multikey record environment, search can be performed under any key in time 0(1); finding the nearest neighbor, the rank, etc. in logarithmic time. Our non-oblivious upper bounds are much better than the appropriate oblivious lower bounds.",

author = "Amos Fiat and Moni Naor and Schmidt, {Jeanette P.} and Alan Siegel",

year = "1988",

doi = "10.1145/62212.62248",

language = "English (US)",

isbn = "0897912640",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "367--376",

booktitle = "Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988",

note = "20th Annual ACM Symposium on Theory of Computing, STOC 1988 ; Conference date: 02-05-1988 Through 04-05-1988",

}

TY - GEN

T1 - Non-oblivious hashing

AU - Fiat, Amos

AU - Naor, Moni

AU - Schmidt, Jeanette P.

AU - Siegel, Alan

PY - 1988

Y1 - 1988

N2 - Non-oblivious hashing, where the information gathered by performing "unsuccessful" probes determines the probe strategy, is introduced and used to obtain the following results for static lookup on full tables: a. An 0(1) worst case scheme that requires only logarithmic additional memory (improving on the [FKS84] linear space upper bound). b. An almost sure 0(1) probabilistic worst case scheme, without any additional memory (improving on previous logarithmic time upper bounds). c. Enhancements to hashing: Solving (a) and (b) in the multikey record environment, search can be performed under any key in time 0(1); finding the nearest neighbor, the rank, etc. in logarithmic time. Our non-oblivious upper bounds are much better than the appropriate oblivious lower bounds.

AB - Non-oblivious hashing, where the information gathered by performing "unsuccessful" probes determines the probe strategy, is introduced and used to obtain the following results for static lookup on full tables: a. An 0(1) worst case scheme that requires only logarithmic additional memory (improving on the [FKS84] linear space upper bound). b. An almost sure 0(1) probabilistic worst case scheme, without any additional memory (improving on previous logarithmic time upper bounds). c. Enhancements to hashing: Solving (a) and (b) in the multikey record environment, search can be performed under any key in time 0(1); finding the nearest neighbor, the rank, etc. in logarithmic time. Our non-oblivious upper bounds are much better than the appropriate oblivious lower bounds.

UR - http://www.scopus.com/inward/record.url?scp=0346195541&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0346195541&partnerID=8YFLogxK

U2 - 10.1145/62212.62248

DO - 10.1145/62212.62248

M3 - Conference contribution

AN - SCOPUS:0346195541

SN - 0897912640

SN - 9780897912648

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 367

EP - 376

BT - Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988

PB - Association for Computing Machinery

T2 - 20th Annual ACM Symposium on Theory of Computing, STOC 1988

Y2 - 2 May 1988 through 4 May 1988

ER -

Non-oblivious hashing

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this