Dynamic Range Reporting in External Memory

2010/06/21 by Yakov Nekrich, Nekrich, Yakov
Computer Science · #Algorithms and Data Compression #Advanced Data Storage Technologies #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.1006.4093

Abstract

In this paper we describe a dynamic external memory data structure that supports range reporting queries in three dimensions in O(log_B² N + (k)/(B)) I/O operations, where k is the number of points in the answer and B is the block size. This is the first dynamic data structure that answers three-dimensional range reporting queries in log_B^O(1) N + O((k)/(B)) I/Os.

Related

• External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates
• A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting
• External Memory Orthogonal Range Reporting with Fast Updates
• Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic Time
• Dynamic Planar Point Location in External Memory