de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

Optimal Encodings for Range Min-Max and Top-k

MPG-Autoren
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;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

arXiv:1411.6581.pdf
(Preprint), 444KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0024-446C-8
Zusammenfassung
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.