dc.contributor.author | Sidlauskas, Darius | |
dc.contributor.author | Chester, Sean | |
dc.contributor.author | Zacharatou, Eleni Tzirita | |
dc.contributor.author | Ailamaki, Anastasia | |
dc.date.accessioned | 2019-01-30T11:48:14Z | |
dc.date.available | 2019-01-30T11:48:14Z | |
dc.date.created | 2018-11-01T16:49:04Z | |
dc.date.issued | 2018 | |
dc.identifier.isbn | 978-1-5386-5520-7 | |
dc.identifier.uri | http://hdl.handle.net/11250/2583073 | |
dc.description.abstract | The majority of spatial processing techniques rely heavily on the idea of approximating each group of spatial objects by their minimum bounding box (MBB). As each MBB is compact to store (requiring only two multi-dimensional points) and intersection tests between MBBs are cheap to execute, these approximations are used predominantly to perform the (initial) filtering step of spatial data processing. However, fitting (groups of) spatial objects into a rough box often results in a very poor approximation of the underlying data. The resulting MBBs contain a lot of "dead space"—fragments of bounded area that contain no actual objects—that can significantly reduce the filtering efficacy. This paper introduces the general concept of a clipped bounding box (CBB) that addresses the principal disadvantage of MBBs, i.e., their poor approximation of spatial objects. Essentially, a CBB "clips away" dead space from the corners of an MBB by storing only a few auxiliary points. Turning to four popular R-tree implementations (a ubiquitous application of MBBs), we demonstrate how minor modifications to the query algorithm can exploit our CBB auxiliary points to avoid many unnecessary recursions into dead space. Extensive experiments show that clipped R-tree variants substantially reduce I/Os: e.g., by clipping the state-of-the-art revised R*-tree we can eliminate on average 19% of I/Os. | nb_NO |
dc.language.iso | eng | nb_NO |
dc.publisher | Institute of Electrical and Electronics Engineers (IEEE) | nb_NO |
dc.relation.ispartof | 2018 IEEE 34th International Conference on Data Engineering (ICDE) | |
dc.title | Improving Spatial Data Processing by Clipping Minimum Bounding Boxes | nb_NO |
dc.title.alternative | Improving Spatial Data Processing by Clipping Minimum Bounding Boxes | nb_NO |
dc.type | Chapter | nb_NO |
dc.description.version | submittedVersion | nb_NO |
dc.source.pagenumber | 425-436 | nb_NO |
dc.identifier.doi | 10.1109/ICDE.2018.00046 | |
dc.identifier.cristin | 1626165 | |
dc.relation.project | EC/H2020/753810 | nb_NO |
dc.description.localcode | © 2018 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | nb_NO |
cristin.unitcode | 194,63,10,0 | |
cristin.unitname | Institutt for datateknologi og informatikk | |
cristin.ispublished | true | |
cristin.fulltext | preprint | |
cristin.qualitycode | 1 | |