Journal article
Adaptive row major order: a new space filling curve for efficient spatial join processing in the transform space
The Journal of systems and software, Vol.78(3), pp.257-269
2005
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
A transform-space index indexes spatial objects represented as points in the transform space. An advantage of a transform-space index is that optimization of spatial join algorithms using these indexes can be more formal. The authors earlier proposed the
Transform-Based Spatial Join algorithm that joins two transform-space indexes. It renders global optimization easy with little overhead by utilizing the characteristics of the transform space. In particular, it allows us to globally determine the order of accessing disk pages, which makes a significant impact on the performance of joins. For this purpose, we use various space filling curves. In this paper, we propose a new space filling curve called the
adaptive row major order (
ARM order). The ARM order adaptively controls the order of accessing pages and significantly reduces the
one-pass buffer size (the minimum buffer size required for guaranteeing one disk access per page) and the number of disk accesses for a given buffer size. Through analysis and experiments, we verify excellence of the ARM order when used with the Transform-Based Spatial Join. The Transform-Based Spatial Join with the ARM order always outperforms those with other conventional space filling curves in terms of both measures used: the one-pass buffer size and the number of disk accesses. Specifically, it reduces the one-pass buffer size by up to 25.9 times and the number of disk accesses by up to 2.11 times. We conclude that we achieve these results mainly due to global optimization of the order of accessing disk pages using an adaptive space filling curve.
Metrics
3 Record Views
Details
- Title
- Adaptive row major order: a new space filling curve for efficient spatial join processing in the transform space
- Creators
- Min-Jae Lee - Department of Computer Science and Advanced Information Technology Research Center (AITrc), Korea Advanced Institute of Science and Technology (KAIST), 373-1, Koo-Sung Dong, Yoo-Sung Ku, Daejeon 305-701, Republic of KoreaKyu-Young Whang - Department of Computer Science and Advanced Information Technology Research Center (AITrc), Korea Advanced Institute of Science and Technology (KAIST), 373-1, Koo-Sung Dong, Yoo-Sung Ku, Daejeon 305-701, Republic of KoreaWook-Shin Han - Department of Computer Engineering, Kyungpook National University, Sankyuk-Dong, Buk-Gu, Daegu 702-701, Republic of KoreaIl-Yeol Song - College of Information Science and Technology, Drexel University, Philadelphia, PA, USA
- Publication Details
- The Journal of systems and software, Vol.78(3), pp.257-269
- Publisher
- Elsevier
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Information Science (Informatics)
- Identifiers
- 991014878292904721
UN Sustainable Development Goals (SDGs)
This output has contributed to the advancement of the following goals:
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Software Engineering
- Computer Science, Theory & Methods