License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2016.3
URN: urn:nbn:de:0030-drops-60704
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6070/
Jo, Seungbum ;
Lingala, Rahul ;
Satti, Srinivasa Rao
Encoding Two-Dimensional Range Top-k Queries
Abstract
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.
BibTeX - Entry
@InProceedings{jo_et_al:LIPIcs:2016:6070,
author = {Seungbum Jo and Rahul Lingala and Srinivasa Rao Satti},
title = {{Encoding Two-Dimensional Range Top-k Queries}},
booktitle = {27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
pages = {3:1--3:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-012-5},
ISSN = {1868-8969},
year = {2016},
volume = {54},
editor = {Roberto Grossi and Moshe Lewenstein},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6070},
URN = {urn:nbn:de:0030-drops-60704},
doi = {10.4230/LIPIcs.CPM.2016.3},
annote = {Keywords: Encoding model, top-k query, range minimum query}
}
|
Keywords: |
|
Encoding model, top-k query, range minimum query |
|
Collection: |
|
27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
27.06.2016 |
