One-dimensional spatial join processing using a DOT-based index structure

Jung Lm Won, Hyun Back, Jee Hee Yoon, Sanghyun Park, Sang Wook Kim

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


Spatial join is an operation that finds a set of object pairs with a given spatial relationship from a spatial database. It is very costly, and thus requires an efficient algorithm for its execution that fully exploits the features of underlying spatial indexes. In this paper, we propose a novel one-dimensonal spatial join algorithm based on DOT indexing. The proposed algorithm reduces the cost of disk accesses by deciding the access order of pages containing spatial objects to minimize the number of buffer replacements. It also minimizes the CPU cost by using a quarter division technique, which divides a query region into a set of subregions that contain consecutive space-filling curves as long as possible. Our algorithm is very easy to integrate with an existing DBMS because it uses B+-trees as a base structure for DOT indexing. We verify the effectiveness of the proposed algorithm via extensive experiments using data sets with various sizes and distributions. The results show that the proposed join algorithm performs up to 3 times better than the previous R -tree-based join algorithm.

Original languageEnglish
Pages (from-to)101-115
Number of pages15
JournalComputer Systems Science and Engineering
Issue number2
Publication statusPublished - 2013 Mar

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'One-dimensional spatial join processing using a DOT-based index structure'. Together they form a unique fingerprint.

Cite this