摘要：In the context of the sliding-window set membership problem, and caching policies that require knowledge of item recency, we formalize the problem of Recency on a stream. Informally, the query asks, "when was the last time I saw item x?" Existing structures, such as hash tables, can support a recency query by augmenting item occurrences with timestamps. To support recency queries on a window of W items, this might require Î~(W log W) bits. We propose a succinct data structure for Recency. By combining sliding-window dictionaries in a hierarchical structure, and careful design of the underlying hash tables, we achieve a data structure that returns a 1 ε approximation to the recency of every item in O(log(ε W)) time, in only (1 o(1))(1 ε)(â"¬ Wlog(ε^(-1))) bits. Here, â"¬ is the information-theoretic lower bound on the number of bits for a set of size W, in a universe of cardinality N.
关键词：Succinct Data Structures; Data Streams; Sliding Dictionary
