Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/9648C742-BA07-43D3-8EFD-AB2B212C0CB0 | - |
| Identifier | https://www.cse.ust.hk/~yike/enclosure/esa04.pdf | - |
| Language | en | - |
| Extent | 12 pages | en |
| Title | Optimal external memory planar point enclosure | en |
| Creator | Samoladas Vasilis | en |
| Creator | Σαμολαδας Βασιλης | el |
| Creator | Lars Arge | en |
| Creator | Ke Yi | en |
| Content Summary | In this paper we study the external memory planar point en- closure problem: Given N axis-parallel rectangles in the plane, construct a data structure on disk (an index) such that all K rectangles containing a query point can be reported I/O-efficiently. This problem has important applications in e.g. spatial and temporal databases, and is dual to the important and well-studied orthogonal range searching problem. Surpris- ingly, we show that one cannot construct a linear sized external memory point enclosure data structure that can be used to answer a query in O(logB N + K/B) I/Os, where B is the disk block size. To obtain this bound, Ω(N/B1−ε) disk blocks are needed for some constant ε > 0. With linear space, the best obtainable query bound is O(log2 N + K/B). To show this we prove a general lower bound on the tradeoff between the size of the data structure and its query cost. We also develop a family of structures with matching space and query bounds. | el |
| Type of Item | Πλήρης Δημοσίευση σε Συνέδριο | el |
| Type of Item | Conference Full Paper | en |
| License | http://creativecommons.org/licenses/by/4.0/ | en |
| Date of Item | 2015-10-17 | - |
| Date of Publication | 2004 | - |
| Bibliographic Citation | L. Arge, V. Samoladas, K. Yi .(2004).Optimal external memory planar point enclosure.Presented at 12th Annual European Symposium.[online].Available: https://www.cse.ust.hk/~yike/enclosure/esa04.pdf | en |
Copyright © DIAS 2013
