2026-07-25T12:52:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10017 2024-03-06T10:45:21Z ddc:004 open_access

Encoding Two-Dimensional Range Top-k Queries Revisited Jo, Seungbum Satti, Srinivasa Rao Encoding model top-k query range minimum query We consider the problem of encoding two-dimensional arrays, whose elements come from a total order, for answering Top-k queries. The aim is to obtain encodings that use space close to the information-theoretic lower bound, which can be constructed efficiently. For 2 x n arrays, we first give upper and lower bounds on space for answering sorted and unsorted 3-sided Top-k queries. For m x n arrays, with m <=n and k <=mn, we obtain (m lg{(k+1)n choose n}+4nm(m-1)+o(n))-bit encoding for answering sorted 4-sided Top-k queries. This improves the min{(O(mn lg{n}),m^2 lg{(k+1)n choose n} + m lg{m}+o(n))}-bit encoding of Jo et al. [CPM, 2016] when m = o(lg{n}). This is a consequence of a new encoding that encodes a 2 x n array to support sorted 4-sided Top-k queries on it using an additional 4n bits, in addition to the encodings to support the Top-k queries on individual rows. This new encoding is a non-trivial generalization of the encoding of Jo et al. [CPM, 2016] that supports sorted 4-sided Top-2 queries on it using an additional 3n bits. We also give almost optimal space encodings for 3-sided Top-k queries, and show lower bounds on encodings for 3-sided and 4-sided Top-k queries. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Seungbum Jo and Srinivasa Rao Satti 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.69 urn:nbn:de:0030-drops-100179 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.69 eng https://creativecommons.org/licenses/by/3.0/legalcode