2009.09.14 | Else Magård

Title: Data Structures for Range Median Queries

Speaker: Allan Grønlund Jørgensen, Aarhus University

Abstract:
In this talk we design data structures supporting \\emph{range median} queries, i.e. report the median element in a sub-range of an array. We consider static and dynamic data structures and batched queries. Our data structures support \\emph{range selection} queries, which are more general, and dominance queries (\\emph{range rank}). In the static case our data structure uses linear space and queries are supported in $O(\\log n/\\log\\log n)$ time. Our dynamic data structure uses $O(n\\log n/\\log \\log n)$ space and supports queries and updates in $O((\\log n/\\log\\log n)^2)$ time.

Joint work with: Gerth S. Brodal

Host: Gerth Stølting Brodal SK: 5211