تقرير
Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
| العنوان: | Optimal Non-Adaptive Cell Probe Dictionaries and Hashing |
|---|---|
| المؤلفون: | Larsen, Kasper Green, Pagh, Rasmus, Persiano, Giuseppe, Pitassi, Toniann, Yeo, Kevin, Zamir, Or |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms |
| الوصف: | We present a simple and provably optimal non-adaptive cell probe data structure for the static dictionary problem. Our data structure supports storing a set of n key-value pairs from [u]x[u] using s words of space and answering key lookup queries in t = O(lg(u/n)/ lg(s/n)) nonadaptive probes. This generalizes a solution to the membership problem (i.e., where no values are associated with keys) due to Buhrman et al. We also present matching lower bounds for the non-adaptive static membership problem in the deterministic setting. Our lower bound implies that both our dictionary algorithm and the preceding membership algorithm are optimal, and in particular that there is an inherent complexity gap in these problems between no adaptivity and one round of adaptivity (with which hashing-based algorithms solve these problems in constant time). Using the ideas underlying our data structure, we also obtain the first implementation of a n-wise independent family of hash functions with optimal evaluation time in the cell probe model. Comment: Appears at ICALP 2024. This paper is a merge and revision of two previous reports [PY20] and [LPPZ23] |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2308.16042 |
| رقم الأكسشن: | edsarx.2308.16042 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |