文章基本信息

标题：Encoding Two-Dimensional Range Top-k Queries
本地全文：下载
作者：Seungbum Jo ; Rahul Lingala ; Srinivasa Rao Satti 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：54
页码：3:1-3:11
DOI：10.4230/LIPIcs.CPM.2016.3
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Encoding model; top-k query; range minimum query