Name
Abstract | ||
|---|---|---|
A spatial join is a query that searches for a set of object pairs satisfying a given spatial relationship from a database. It is one of the most costly queries, and thus requires an efficient processing algorithm that fully exploits the features of the underlying spatial indexes. In our earlier work, we devised a fairly effective algorithm for processing spatial joins with double transformation (DOT) indexing, which is one of several spatial indexing schemes. However, the algorithm is restricted to only the one-dimensional cases. In this paper, we extend the algorithm for the two-dimensional cases, which are general in Geographic Information Systems (GIS) applications. We first extend DOT to two-dimensional original space. Next, we propose an efficient algorithm for processing range queries using extended DOT. This algorithm employs the quarter division technique and the tri-quarter division technique devised by analyzing the regularity of the space-filling curve used in DOT. This greatly reduces the number of space transformation operations. We then propose a novel spatial join algorithm based on this range query processing algorithm. In processing a spatial join, we determine the access order of disk pages so that we can minimize the number of disk accesses. We show the superiority of the proposed method by extensive experiments using data sets of various distributions and sizes. The experimental results reveal that the proposed method improves the performance of spatial join processing up to three times in comparison with the widely-used R-tree-based spatial join method. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.ins.2009.11.029 | Inf. Sci. |
Keywords | Field | DocType |
dot-based indexing,efficient processing algorithm,processing spatial,spatial relationship,spatial indexing scheme,efficient algorithm,widely-used r-tree-based spatial,underlying spatial index,range query processing algorithm,effective algorithm,spatial relationships,range query,spatial database,spatial index,geographic information system,indexation,satisfiability | Geographic information system,Data mining,Data set,Joins,Computer science,Range query (data structures),Search engine indexing,Spatial query,Space-filling curve,Spatial database | Journal |
Volume | Issue | ISSN |
180 | 8 | 0020-0255 |
Citations | PageRank | References |
1 | 0.35 | 25 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hyun Back | 1 | 1 | 0.69 |
| Jung-Im Won | 2 | 86 | 10.56 |
| Jee-Hee Yoon | 3 | 49 | 8.70 |
| Sanghyun Park | 4 | 729 | 80.64 |
| Sang-Wook Kim | 5 | 792 | 152.77 |