A dynamic I/O-efficient structure for one-dimensional top-k range reporting
Yufei Tao · 2014
We present a structure in external memory for top-k range reporting, which uses linear space, answers a query in O(lgB n + k/B) I/Os, and supports an update in O(lgB 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(lg2B n) amortized I/Os per update.