Kejlberg-Rasmussen, Casper, Tsakalidis, Konstantinos 
ORCID: 0000-0001-6470-9332 and Tsichlas, Kostas
(2012)
I/O-Efficient Dynamic Planar Range Skyline Queries.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
1207.2341v1.pdf - Submitted version Download (446kB) |
Abstract
We present the first fully dynamic worst case I/O-efficient data structures that support planar orthogonal \textit{3-sided range skyline reporting queries} in $\bigO (\log_{2B^\epsilon} n + \frac{t}{B^{1-\epsilon}})$ I/Os and updates in $\bigO (\log_{2B^\epsilon} n)$ I/Os, using $\bigO (\frac{n}{B^{1-\epsilon}})$ blocks of space, for $n$ input planar points, $t$ reported points, and parameter $0 \leq \epsilon \leq 1$. We obtain the result by extending Sundar's priority queues with attrition to support the operations \textsc{DeleteMin} and \textsc{CatenateAndAttrite} in $\bigO (1)$ worst case I/Os, and in $\bigO(1/B)$ amortized I/Os given that a constant number of blocks is already loaded in main memory. Finally, we show that any pointer-based static data structure that supports \textit{dominated maxima reporting queries}, namely the difficult special case of 4-sided skyline queries, in $\bigO(\log^{\bigO(1)}n +t)$ worst case time must occupy $\Omega(n \frac{\log n}{\log \log n})$ space, by adapting a similar lower bounding argument for planar 4-sided range reporting queries.
| Item Type: | Article |
|---|---|
| Additional Information: | Submitted to SODA 2013 |
| Uncontrolled Keywords: | cs.DS, cs.DS, E.1; F.2.2 |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 05 Feb 2019 09:53 |
| Last Modified: | 19 Jan 2023 01:08 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3030693 |
Share
Share
