With the large number of spatial queries for spatial data objects changing with time in many applications, e.g., the location based services and geographic information systems, spatio-temporal databases have been developed to manipulate them in spatial or temporal databases. We focus on queries for stationary and moving objects in the spatial database in the present. However, there is no total ordering for the large volume and complicated objects which may change their geometries with time. A spatial access method based on the spatial index structure attempts to preserve the spatial proximity as much as possible. Then, the number of disk access which takes the response time is reduced during the query processing. Therefore, in this dissertation, based on the NA-tree, first, we propose the NA-tree join method over the stationary objects. Our NA-tree join simply uses the correlation table to directly obtain candidate leaf nodes based on two NA-trees which have non-empty overlaps. Moreover, our NA-tree join accesses objects once from those candidate leaf nodes and returns pairs of objects which have non-empty overlaps. Second, we propose the NABP method for the continuous range queries over the moving objects. Our NABP method uses the bit-patterns of regions in the NA-tree to check the relation between the range queries and moving objects. Our NABP method searches only one path in the NA-tree for the range query, instead of more than one path in the R*-tree-based method which has the overlapping problem. When the number of range queries increases with time, our NABP method incrementally updates the affected range queries by bit-patterns checking, instead of rebuilding the index like the cell-based method. From the experimental results, we have shown that our NABP method needs less time than the cell-based method for range queries update and less time than the R*-tree-based method for moving objects update. Based on the Hilbert curve with the good clustering property, we propose the ANHC method to answer the all-nearest-neighbors query by our ONHC method. Our ONHC method is used to answer the one-nearest-neighbor query over the stationary objects. We generate direction sequences to store the orientations of the query block in the Hilbert curve of different orders. By using quaternary numbers and direction sequences of the query block, we obtain the relative locations of the neighboring blocks and compute their quaternary numbers. Then, we directly access the neighboring blocks by their sequence numbers which is the transformation of the quaternary numbers from base four to ten. The nearest neighbor can be obtained by distance comparisons in these blocks. From the experimental results, we have shown that our ONHC and ANHC methods need less time than CCSF method for the one-nearest-neighbor query and the method based on R*-trees for the all-nearest-neighbors query, respectively.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0520111-020501 |
| Date | 20 May 2011 |
| Creators | Chen, Hue-Ling |
| Contributors | Suh-Yin Lee, Chiang Lee, Chung-Nan Lee, Wei-Pang Yang, Ye-In Chang, Vincent S. Tseng, S.-Y. Hwang |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0520111-020501 |
| Rights | withheld, Copyright information available at source archive |
Page generated in 0.0028 seconds