Online Sorted Range Reporting

Gerth Stølting Brodal, Rolf Fagerberg, Mark Greve, Alejandro López-Ortiz

Publikation: Bidrag til bog/antologi/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Resumé

We study the following one-dimensional range reporting problem: On an array A of n elements, support queries that given two indices i ≤ j and an integer k report the k smallest elements in the subarray A[i..j] in sorted order. We present a data structure in the RAM model supporting such queries in optimal O(k) time. The structure uses O(n) words of space and can be constructed in O(n logn) time. The data structure can be extended to solve the online version of the problem, where the elements in A[i..j] are reported one-by-one in sorted order, in O(1) worst-case time per element. The problem is motivated by (and is a generalization of) a problem with applications in search engines: On a tree where leaves have associated rank values, report the highest ranked leaves in a given subtree. Finally, the problem studied generalizes the classic range minimum query (RMQ) problem on arrays.
OriginalsprogEngelsk
TitelAlgorithms and Computation, 20th International ymposium, ISAAC
Vol/bind5878
ForlagSpringer
Publikationsdato2009
Sider173-182
DOI
StatusUdgivet - 2009
BegivenhedAlgorithms and Computation -
Varighed: 24. aug. 2010 → …
Konferencens nummer: 20

Konference

KonferenceAlgorithms and Computation
Nummer20
Periode24/08/2010 → …
NavnLecture Notes in Computer Science
Vol/bind5878

Fingeraftryk

Data structures
Random access storage
Search engines

Citer dette

Brodal, G. S., Fagerberg, R., Greve, M., & López-Ortiz, A. (2009). Online Sorted Range Reporting. I Algorithms and Computation, 20th International ymposium, ISAAC (Bind 5878, s. 173-182). Springer. Lecture Notes in Computer Science, Bind. 5878 https://doi.org/10.1007/978-3-642-10631-6_19
Brodal, Gerth Stølting ; Fagerberg, Rolf ; Greve, Mark ; López-Ortiz, Alejandro. / Online Sorted Range Reporting. Algorithms and Computation, 20th International ymposium, ISAAC. Bind 5878 Springer, 2009. s. 173-182 (Lecture Notes in Computer Science, Bind 5878).
@inproceedings{312bb15003c211dfaefb000ea68e967b,
title = "Online Sorted Range Reporting",
abstract = "We study the following one-dimensional range reporting problem: On an array A of n elements, support queries that given two indices i ≤ j and an integer k report the k smallest elements in the subarray A[i..j] in sorted order. We present a data structure in the RAM model supporting such queries in optimal O(k) time. The structure uses O(n) words of space and can be constructed in O(n logn) time. The data structure can be extended to solve the online version of the problem, where the elements in A[i..j] are reported one-by-one in sorted order, in O(1) worst-case time per element. The problem is motivated by (and is a generalization of) a problem with applications in search engines: On a tree where leaves have associated rank values, report the highest ranked leaves in a given subtree. Finally, the problem studied generalizes the classic range minimum query (RMQ) problem on arrays.",
author = "Brodal, {Gerth St{\o}lting} and Rolf Fagerberg and Mark Greve and Alejandro L{\'o}pez-Ortiz",
year = "2009",
doi = "10.1007/978-3-642-10631-6_19",
language = "English",
volume = "5878",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "173--182",
booktitle = "Algorithms and Computation, 20th International ymposium, ISAAC",
address = "Germany",

}

Brodal, GS, Fagerberg, R, Greve, M & López-Ortiz, A 2009, Online Sorted Range Reporting. i Algorithms and Computation, 20th International ymposium, ISAAC. bind 5878, Springer, Lecture Notes in Computer Science, bind 5878, s. 173-182, Algorithms and Computation, 24/08/2010. https://doi.org/10.1007/978-3-642-10631-6_19

Online Sorted Range Reporting. / Brodal, Gerth Stølting; Fagerberg, Rolf; Greve, Mark; López-Ortiz, Alejandro.

Algorithms and Computation, 20th International ymposium, ISAAC. Bind 5878 Springer, 2009. s. 173-182 (Lecture Notes in Computer Science, Bind 5878).

Publikation: Bidrag til bog/antologi/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

TY - GEN

T1 - Online Sorted Range Reporting

AU - Brodal, Gerth Stølting

AU - Fagerberg, Rolf

AU - Greve, Mark

AU - López-Ortiz, Alejandro

PY - 2009

Y1 - 2009

N2 - We study the following one-dimensional range reporting problem: On an array A of n elements, support queries that given two indices i ≤ j and an integer k report the k smallest elements in the subarray A[i..j] in sorted order. We present a data structure in the RAM model supporting such queries in optimal O(k) time. The structure uses O(n) words of space and can be constructed in O(n logn) time. The data structure can be extended to solve the online version of the problem, where the elements in A[i..j] are reported one-by-one in sorted order, in O(1) worst-case time per element. The problem is motivated by (and is a generalization of) a problem with applications in search engines: On a tree where leaves have associated rank values, report the highest ranked leaves in a given subtree. Finally, the problem studied generalizes the classic range minimum query (RMQ) problem on arrays.

AB - We study the following one-dimensional range reporting problem: On an array A of n elements, support queries that given two indices i ≤ j and an integer k report the k smallest elements in the subarray A[i..j] in sorted order. We present a data structure in the RAM model supporting such queries in optimal O(k) time. The structure uses O(n) words of space and can be constructed in O(n logn) time. The data structure can be extended to solve the online version of the problem, where the elements in A[i..j] are reported one-by-one in sorted order, in O(1) worst-case time per element. The problem is motivated by (and is a generalization of) a problem with applications in search engines: On a tree where leaves have associated rank values, report the highest ranked leaves in a given subtree. Finally, the problem studied generalizes the classic range minimum query (RMQ) problem on arrays.

U2 - 10.1007/978-3-642-10631-6_19

DO - 10.1007/978-3-642-10631-6_19

M3 - Article in proceedings

VL - 5878

T3 - Lecture Notes in Computer Science

SP - 173

EP - 182

BT - Algorithms and Computation, 20th International ymposium, ISAAC

PB - Springer

ER -

Brodal GS, Fagerberg R, Greve M, López-Ortiz A. Online Sorted Range Reporting. I Algorithms and Computation, 20th International ymposium, ISAAC. Bind 5878. Springer. 2009. s. 173-182. (Lecture Notes in Computer Science, Bind 5878). https://doi.org/10.1007/978-3-642-10631-6_19