Efficient dictionaries with non-adaptive queries based on bipartite graph techniques
Online matching games in bipartite expanders: applications to bitprobes and dictionaries with non-adaptive probing
Data Structures and Algorithms
Summary
Dictionaries in computing store pairs of information and quickly answer questions about them. The authors present new ways to build dictionaries where queries check only fixed parts of the data, speeding up access. They also introduce dynamic structures that allow items to be added or removed while still making quick queries. Their method relies on a game played on special graphs called bipartite expanders to efficiently match requests to stored items. This approach leads to better space use and querying speed than previous methods in some cases.
What this means in practice
- •For database engineers: Implement dictionaries with fixed probing patterns for faster query operations in static or dynamic settings.
- •For network system designers: Develop compact and efficient membership query structures that support dynamic updates with guaranteed probe efficiency.
A theory result. No direct application yet.
Authors
Bruno Bauwens, Marius Zimand
Abstract
A dictionary is a data structure which stores pairs (key, value). The operation query on input key returns value if the dictionary contains a pair (key, value) and nil otherwise. A dynamic dictionary also supports the insert and delete operations. The model with cells of bitsize $n + m + 1$ is used, where $n$ and $m$ are the bitsizes of keys and values. We give 2 dictionaries that use $(1+o(1))K$ cells to store $K$ pairs and in which query makes \emph{non-adaptive probes} to the data structure: a static one in which query makes $\smash{\widetilde O(n^2)}$ probes, and a dynamic one in which it makes $\smash{\widetilde O(n^2 \log K)}$ probes. Also, for the first time, a dictionary is given in which all 3 operations are non-adaptive, but the size is larger: $O(nK)$ cells. The constructions are explicit and, consequently, all operations run in time $\poly(n,m)$. 1-bitprobes storage schemes store a set $S \subseteq \{0,1\}^n$ and answer a membership query by reading a single bit. We introduce 1-bitprobes that are {\em dynamic}. Such a scheme is given whose size is smaller than in all previous constructions which are static. The \textsf{query} operation has runtime $n^{O(1)}$. The operations delete and insert have runtime $n^{O(\log n)}$. The proofs rely on a strategy for an online matching game played on a given bipartite graph. An opponent switches left nodes {\em on} and {\em off}. The strategy needs to assign an irrevocable match to a node when it is turned {\em on}. Such games were introduced in the companion paper~\cite{companion-Hall}. The applications in this paper rely on efficient strategies assuming that each node is turned {\em off} after a polynomial number of rounds. We present efficient strategies for (lossless) expanders.