Aarhus University Seal / Aarhus Universitets segl

MADALGO Theory Seminar

MADALGO Seminar: Gerth S. Brodal (AU): "External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates"

2016.02.03 | Katrine Østerlund Rasmussen

Date Wed 10 Feb
Time 14:15 15:00
Location Nygaard 395

Title: 
External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates

Abstract:
An external memory data structure is presented for maintaining a dynamic set of N two-dimensional points under the insertion and deletion of points, and supporting 3-sided range reporting queries and top-k queries, where top-k queries report the k points with highest y-value within a given x-range. For any constant 0 < ε ≤ 1/2, a data structure is constructed that supports updates in amortized O(1/(εB1ε) ∙logB N) IOs and queries in amortized O(1/ε∙logBN+K/B) IOs, where B is the external memory block size, and K is the size of the output to the query (for top-k queries K is the minimum of k and the number of points in the query interval). The data structure uses linear space. The update bound is a significant factor B1ε improvement over the previous best update bounds for the two query problems, while staying within the same query and space bounds.

Talk to be presented at STACS’16.

arxiv.org/abs/1509.08240

 

Lecture / talk