[2209.06038] A Hash Table Without Hash Functions, and How to Get the Most Out of...
source link: https://arxiv.org/abs/2209.06038
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science > Data Structures and Algorithms
[Submitted on 13 Sep 2022 (v1), last revised 15 Sep 2022 (this version, v2)]
A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits
This paper considers the basic question of how strong of a probabilistic guarantee can a hash table, storing n (1 + \Theta(1)) \log n-bit key/value pairs, offer? Past work on this question has been bottlenecked by limitations of the known families of hash functions: The only hash tables to achieve failure probabilities less than 1 / 2^{\polylog n} require access to fully-random hash functions -- if the same hash tables are implemented using the known explicit families of hash functions, their failure probabilities become 1 / \poly(n).
To get around these obstacles, we show how to construct a randomized data structure that has the same guarantees as a hash table, but that \emph{avoids the direct use of hash functions}. Building on this, we are able to construct a hash table using O(n) random bits that achieves failure probability 1 / n^{n^{1 - \epsilon}} for an arbitrary positive constant \epsilon.
In fact, we show that this guarantee can even be achieved by a \emph{succinct dictionary}, that is, by a dictionary that uses space within a 1 + o(1) factor of the information-theoretic optimum.
Finally we also construct a succinct hash table whose probabilistic guarantees fall on a different extreme, offering a failure probability of 1 / \poly(n) while using only \tilde{O}(\log n) random bits. This latter result matches (up to low-order terms) a guarantee previously achieved by Dietzfelbinger et al., but with increased space efficiency and with several surprising technical components.
| Subjects: | Data Structures and Algorithms (cs.DS) |
| Cite as: | arXiv:2209.06038 [cs.DS] |
| (or arXiv:2209.06038v2 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2209.06038 |
Submission history
From: William Kuszmaul [view email][v1] Tue, 13 Sep 2022 14:40:35 UTC (30 KB)
[v2] Thu, 15 Sep 2022 21:04:32 UTC (30 KB)
Recommend
-
24
I released a new project A Simple GPU Hash Table on Github. It is a simple GPU hash table capable of hundreds of mill...
-
13
Freezers as an analogy for hash table behavior While I was out of town on vacation recently, there was a cluster of advisories about malicious HTTP GET and POST requests. In short, crafting the right sort of request and directing...
-
2
Josh Bentley September 14, 2022 3 minute read
-
10
Pensieve: 2209 2022-09-25 22:34 所观所读所玩所听 Netflix上看了Cyberpunk: Edgerunner, 感觉像一个大号版的爱死机或黑镜. 里面那些经...
-
9
Helen Han December 5, 2022 ...
-
6
[Submitted on 22 Sep 2022 (v1), last revised 3 Dec 2022 (this version, v2)] A Generalist Neural Algorithmic Learner...
-
6
[Submitted on 5 Sep 2022] Induced Cycles and Paths Are Harder Than You Think Download PDF...
-
6
[Submitted on 19 Sep 2022] Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours
-
12
[Submitted on 21 Sep 2022 (v1), last revised 12 Nov 2022 (this version, v2)] Improved Approximation for Two-Edge-Connectivity
-
3
[Submitted on 27 Sep 2022 (v1), last revised 7 Dec 2022 (this version, v2)] Measurement of the Electron Magnetic Moment...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK