• norsk
    • English
  • norsk 
    • norsk
    • English
  • Logg inn
Vis innførsel 
  •   Hjem
  • Øvrige samlinger
  • Publikasjoner fra CRIStin - NTNU
  • Vis innførsel
  •   Hjem
  • Øvrige samlinger
  • Publikasjoner fra CRIStin - NTNU
  • Vis innførsel
JavaScript is disabled for your browser. Some features of this site may not work without it.

Improving Spatial Data Processing by Clipping Minimum Bounding Boxes

Sidlauskas, Darius; Chester, Sean; Zacharatou, Eleni Tzirita; Ailamaki, Anastasia
Chapter
Submitted version
Thumbnail
Åpne
icde-sidlauskas-2018.pdf (774.7Kb)
Permanent lenke
http://hdl.handle.net/11250/2583073
Utgivelsesdato
2018
Metadata
Vis full innførsel
Samlinger
  • Institutt for datateknologi og informatikk [4881]
  • Publikasjoner fra CRIStin - NTNU [26591]
Originalversjon
10.1109/ICDE.2018.00046
Sammendrag
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.
Utgiver
Institute of Electrical and Electronics Engineers (IEEE)

Kontakt oss | Gi tilbakemelding

Personvernerklæring
DSpace software copyright © 2002-2019  DuraSpace

Levert av  Unit
 

 

Bla i

Hele arkivetDelarkiv og samlingerUtgivelsesdatoForfattereTitlerEmneordDokumenttyperTidsskrifterDenne samlingenUtgivelsesdatoForfattereTitlerEmneordDokumenttyperTidsskrifter

Min side

Logg inn

Statistikk

Besøksstatistikk

Kontakt oss | Gi tilbakemelding

Personvernerklæring
DSpace software copyright © 2002-2019  DuraSpace

Levert av  Unit