License
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://drops.dagstuhl.de/opus/volltexte/2018/10017/
Go to the corresponding LIPIcs Volume Portal


Jo, Seungbum ; Satti, Srinivasa Rao

Encoding Two-Dimensional Range Top-k Queries Revisited

pdf-format:
LIPIcs-ISAAC-2018-69.pdf (0.5 MB)


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
Seminar: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 27.11.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI