Cell-Probe Lower Bounds for Prefix Sums

2009/06/07 by Emanuele Viola, Viola, Emanuele
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CC #cs.DS

paper · pdf · doi:10.48550/arxiv.0906.1370

arxiv created 2009/06/07 · arxiv updated 2009/12/01

Abstract

We prove that to store n bits x so that each prefix-sum query Sum(i) := sum_{k < i} x_k can be answered by non-adaptively probing q cells of log n bits, one needs memory > n + n/log^O(q) n. Our bound matches a recent upper bound of n + n/log^Omega(q) n by Patrascu (FOCS 2008), also non-adaptive. We also obtain a n + n/log^2^O(q) n lower bound for storing a string of balanced brackets so that each Match(i) query can be answered by non-adaptively probing q cells. To obtain these bounds we show that a too efficient data structure allows us to break the correlations between query answers.

Related

• An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture
• The Cell Probe Complexity of Succinct Data Structures
• A Lower Bound for Succinct Rank Queries
• Logarithmic Lower Bounds in the Cell-Probe Model
• Lower bounds for predecessor searching in the cell probe model