Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Improving Spatial Data Processing by Clipping Minimum Bounding Boxes
 
conference paper

Improving Spatial Data Processing by Clipping Minimum Bounding Boxes

Sidlauskas, Darius  
•
Chester, Sean
•
Tzirita Zacharatou, Eleni  
Show more
2018
2018 IEEE 34th International Conference on Data Engineering (Icde)
34th IEEE International Conference on Data Engineering Workshops (ICDEW)

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.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1109/ICDE.2018.00046
Web of Science ID

WOS:000492836500038

Author(s)
Sidlauskas, Darius  
Chester, Sean
Tzirita Zacharatou, Eleni  
Ailamaki, Anastasia  
Date Issued

2018

Publisher

IEEE

Publisher place

New York

Published in
2018 IEEE 34th International Conference on Data Engineering (Icde)
Start page

425

End page

436

Subjects

Computer Science, Information Systems

•

Computer Science, Theory & Methods

•

Computer Science

•

tree

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DIAS  
Event nameEvent placeEvent date
34th IEEE International Conference on Data Engineering Workshops (ICDEW)

Paris, France

April 16-19, 2018

Available on Infoscience
March 3, 2018
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/145152
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés