de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Optimal Encodings for Range Min-Max and Top-k

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons118149

Gawrychowski,  Pawel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons101850

Nicholson,  Patrick K.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

arXiv:1411.6581.pdf
(Preprint), 444KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Gawrychowski, P., & Nicholson, P. K. (2014). Optimal Encodings for Range Min-Max and Top-k. Retrieved from http://arxiv.org/abs/1411.6581.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0024-446C-8
Abstract
In this paper we consider various encoding problems for range queries on arrays. In these problems, the goal is that the encoding occupies the information theoretic minimum space required to answer a particular set of range queries. Given an array $A[1..n]$ a range top-$k$ query on an arbitrary range $[i,j] \subseteq [1,n]$ asks us to return the ordered set of indices $\{l_1 ,...,l_k \}$ such that $A[l_m]$ is the $m$-th largest element in $A[i..j]$. We present optimal encodings for range top-$k$ queries, as well as for a new problem which we call range min-max, in which the goal is to return the indices of both the minimum and maximum element in a range.