A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting

2012/08/22 by Yufei Tao, Tao, Yufei
Computer Science · #Advanced Database Systems and Queries #Algorithms and Data Compression #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1208.4516

In PODS'14

openalex publication_date 2012/08/22 · arxiv created 2014/03/26 · arxiv updated 2014/03/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a structure in external memory for "top-k range reporting", which uses linear space, answers a query in O(lg_B n + k/B) I/Os, and supports an update in O(lg_B n) amortized I/Os, where n is the input size, and B is the block size. This improves the state of the art which incurs O(lg²_B n) amortized I/Os per update.

Related

• Dynamic Range Reporting in External Memory
• External Memory Orthogonal Range Reporting with Fast Updates
• External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates
• I/O-Efficient Data Structures for Colored Range and Prefix Reporting
• On Dynamic Range Reporting in One Dimension