2026-07-24T17:51:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13393 2024-03-06T10:51:52Z ddc:004 open_access

Recency Queries with Succinct Representation Holland, William L. Wirth, Anthony Zobel, Justin Succinct Data Structures Data Streams Sliding Dictionary 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik William L. Holland and Anthony Wirth and Justin Zobel 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.49 urn:nbn:de:0030-drops-133931 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.49 eng https://creativecommons.org/licenses/by/3.0/legalcode