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.ISAAC.2018.69
URN: urn:nbn:de:0030-drops-100179
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10017/
Jo, Seungbum ;
Satti, Srinivasa Rao
Encoding Two-Dimensional Range Top-k Queries Revisited
Abstract
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.
BibTeX - Entry
@InProceedings{jo_et_al:LIPIcs:2018:10017,
author = {Seungbum Jo and Srinivasa Rao Satti},
title = {{Encoding Two-Dimensional Range Top-k Queries Revisited}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {69:1--69:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-094-1},
ISSN = {1868-8969},
year = {2018},
volume = {123},
editor = {Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10017},
URN = {urn:nbn:de:0030-drops-100179},
doi = {10.4230/LIPIcs.ISAAC.2018.69},
annote = {Keywords: Encoding model, top-k query, range minimum query}
}
|
Keywords: |
|
Encoding model, top-k query, range minimum query |
|
Collection: |
|
29th International Symposium on Algorithms and Computation (ISAAC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
06.12.2018 |
