English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Paper

Optimal Encodings for Range Min-Max and Top-k

MPS-Authors
/persons/resource/persons118149

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

/persons/resource/persons101850

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

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
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: https://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.