



























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<\varepsilon\leq \frac{1}{2}$, a data structure is constructed that supports updates in amortized $O(\frac{1}{\varepsilon B^{1-\varepsilon}}\log_B N)$ IOs and queries in amortized $O(\frac{1}{\varepsilon}\log_B N+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 $B^{1-\varepsilon}$ improvement over the previous best update bounds for the two query problems, while staying within the same query and space bounds.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。