Make It Count: Rank-Query Algorithm Space Bounds

Abstract

Streaming models have been a primary focus in recent years on data storage and what queries can be effectively answered in sublinear space. The stream receives items in the form (x,w), where w represents the weight of key x, and we focus on algorithms that return the estimated rank of x, calculated as ∑j<xwj where wj is the true weight of each key j that is smaller than x. We take both a data structure and algorithmic approach over general space lower bound questions related to rank queries. For data structures, Dyadic CountSketch \cite{DCS} was proposed to efficiently solve rank-queries in the strict turnstile model (weights of keys can never drop below 0), and then we show that modifying q-digest \cite{q-digest} can serve as an efficient structure for the bounded deletion setting. The second main part deals with general space complexity lower bounds focused on one-pass rank-query streaming algorithms.