New framework links memory and query costs in matrix data structures
Systematic Data Structure Lower Bounds via the Query-with-Sketch Model
Data Structures and AlgorithmsComputational Complexity
Summary
This paper looks at how computers store and quickly access information from a special kind of table called a matrix. The authors study how much extra memory and how many checks to memory spots are needed to answer certain questions about the matrix after some preparation. They introduce a new model that helps prove limits on these trade-offs, showing when it’s impossible to have both very little extra memory and very fast answers. Their findings also provide evidence supporting a longstanding idea about how much space certain data tasks require.
What this means in practice
- •For database engineers: Design more efficient query systems that balance memory use and speed based on fundamental limits shown by this framework.
- •For network protocol designers: Understand how much memory redundancy and query effort are needed for fast lookups in network data structures handling adjacency-like matrices.
A theory result. No direct application yet.
Authors
Sumegha Garg, Songhua He, Yuanzhi Li, Periklis A. Papakonstantinou, Xin Yang
Abstract
We study data structure lower bounds for the Approximate Matrix Powering (AMP) problem. Given a substochastic, symmetric matrix $\mathbf{M}\in\mathbb{R}^{n\times n}$ and parameters $k$ and $α$, the goal is to preprocess $\mathbf{M}$ so as to answer entry queries $(u,v)\mapsto \mathbf{M}^{k}[u,v]$ up to additive error $1/n^α$. We focus on AMP in the succinct and systematic regime, in which the data structure stores $\mathbf{M}$ verbatim, uses an additional $r$ bits of redundancy, and must answer queries by probing only a small number of entries of $\mathbf{M}$. Our main conceptual contribution is a general framework for proving probe--redundancy trade-offs for systematic data structures. We introduce the query-with-sketch model and develop a min-entropy-based approach that lifts conditional min-entropy bounds in the absence of redundancy to probe lower bounds in the presence of redundancy. We then establish these min-entropy bounds using problem-specific analytic and algebraic tools, for the downstream applications to AMP and its variants. As a consequence, our results provide new unconditional evidence toward a conjecture of Patrascu and Roditty (2010) on the space required for constant-time set-disjointness queries.