2026-07-23T07:58:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6070 2024-03-06T10:37:33Z ddc:004 open_access

Encoding Two-Dimensional Range Top-k Queries Jo, Seungbum Lingala, Rahul Satti, Srinivasa Rao Encoding model top-k query range minimum query We consider various encodings that support range top-k queries on a two-dimensional array containing elements from a total order. For an m x n array, we first propose an almost optimal encoding for answering one-sided top-k queries, whose query range is restricted to [1 ... m][1 .. a], for 1 <= a <= n. Next, we propose an encoding for the general top-k queries that takes m^2 * lg(binom((k+1)n)(n)) + m * lg(m) + o(n) bits. This generalizes the one-dimensional top-k encoding of Gawrychowski and Nicholson [ICALP, 2015]. Finally, for a 2 x n array, we obtain a 2 lg(binom(3n)(n)) + 3n + o(n)-bit encoding for answering top-2 queries. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Seungbum Jo and Rahul Lingala and Srinivasa Rao Satti 2016 Is Part Of LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2016.3 urn:nbn:de:0030-drops-60704 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.3 eng https://creativecommons.org/licenses/by/3.0/legalcode