Loading...
Please wait, while we are loading the content...
Similar Documents
Quad-splitting algorithm for a window query on a hilbert curve.
| Content Provider | CiteSeerX |
|---|---|
| Author | Wu, Chen-Chang Chang, Ye-In |
| Abstract | Space-filling curves, particularly, Hilbert curves, have been extensively used to maintain spatial locality of multi-dimensional data in a wide variety of applications. A window query is an important query operation in spatial (image) databases. Given a Hilbert curve, a window query reports its corresponding orders without the need to decode all the points inside this window into the corresponding Hilbert orders. Given a query window of size p × q on a Hilbert curve of size T × T, Chung et al. have proposed an algorithm for decomposing a window into the corresponding Hilbert orders, which needs O(n log T) time, where n = max(p, q). By employing the properties of Hilbert curves, we present an efficient algorithm, named as Quad-Splitting, for decomposing a window into the corresponding Hilbert orders on a Hilbert curve without individual sorting and merging steps. Although the proposed algorithm also takes O(n log T) time, it does not perform individual sorting and merging steps which are needed in Chung et al.’s algorithm. Therefore, experimental results show that the Quad-Splitting algorithm outperforms Chung et al.’s algorithm. 1 |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Hilbert Curve Window Query Quad-splitting Algorithm Corresponding Hilbert Order Merging Step Individual Sorting Quad-splitting Algorithm Outperforms Chung Important Query Operation Multi-dimensional Data Efficient Algorithm Corresponding Order Query Window Spatial Locality Wide Variety Space-filling Curve Experimental Result |
| Content Type | Text |
