2026-09-05T06:57:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25935 2026-06-23T13:12:26Z ddc:004 open_access

Indexing and Encoding Arrays for Element Distinctness Queries Fischer, Johannes Lari, Filippo element distinctness range queries lower bounds succinct data structures We introduce the data structure variant of the well-known element distinctness problem. Given an array of n elements, the goal is to preprocess the array into a data structure that supports queries asking whether all elements within a given query range are distinct. This has applications in text indexing and possibly also in other algorithmic domains. In the indexing model (where access to the input array is allowed), we design a data structure using O((n log b)/b) bits and answering queries in the time needed to solve an online element distinctness instance of size O(b), for any b ≥ 1. As a concrete instantiation of this, there exists an index that answers queries in O(log log log n) time using O({n log²(log log log n)}/{log log log n}) bits of additional space. Moving to the encoding model (where access to the input array is not allowed), we begin by proving an information-theoretic lower bound for the space usage of 2n-O(log n) bits, and then design a matching encoding with O(1) time queries. We then consider the case in which the alphabet size σ is constant. In this setting, the lower bound can be refined to n log(r_σ) - 3 log(σ+2) + O(1) bits, where r_σ = 4cos²(π/(σ+2)). This lower bound is matched by an encoding with O(1) time queries. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Johannes Fischer and Filippo Lari 2026 Is Part Of LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2026.9 urn:nbn:de:0030-drops-259350 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.9 eng https://creativecommons.org/licenses/by/4.0/legalcode