2 papers
cs.DS2026
Average-Case Optimal Encodings and Efficient Worst-Case Indices for Element Distinctness Queries
Philip Bille, Johannes Fischer, Inge Li Gørtz +1
We study the data structure version of the \emph{element distinctness problem}: preprocess an array of elements from an alphabet of size to answer \textsc{All-Distinct} que…
cs.DS2025
Compressibility Measures and Succinct Data Structures for Piecewise Linear Approximations
Paolo Ferragina, Filippo Lari
We study the problem of deriving compressibility measures for Piecewise Linear Approximations (PLAs), i.e., error-bounded approximations of a set of two-dimensional increasing data…