With the proliferation of wireless communications and rapid advances in technologies, algorithms for efficiently answering queries about large number of spatial data are needed. Spatial data consists of spatial objects including data of higher dimension. Neighbor finding is one of the most important spatial operations in the field of spatial data structures. In recent years, many researchers have focused on finding efficient solutions to the nearest neighbor problem (NN) which involves determining the point in a data set that is the nearest to a given query point. It is frequently used in Geographical Information Systems (GIS). A block B is said to be the neighbor of another block A, if block B has the same property as block A has and covers an equal-sized neighbor of block A. Jozef Voros has proposed a neighbor finding strategy on images represented by quadtrees, in which the four equal-sized neighbors (the east, west, north, and south directions) of block A can be found. However, based on Voros's strategy, the case that the nearest neighbor occurs in the diagonal directions (the northeast, northwest, southeast, and southwest directions) will be ignored. Moreover, there is no total ordering that preserve proximity when mapping a spatial data from a higher dimensional space to a 1D-space. One way of effecting such a mapping is to utilize space-filling curves. Space-filling curves pass through every point in a space and give a one-one correspondence between the coordinate and the 1D-sequence number of the point. The Peano curve, proposed by Orenstein, which maps the 1D-coordinate of a point by simply interleaving the bits of the X and Y coordinates in the 2D-space, can be easily used in neighbor finding. But with the data ordered by the RBG curve or the Hilbert curve, the neighbor finding would be complex. The RBG curve achieves savings in random accesses on the disk for range queries and the Hilbert curve achieves the best clustering for range queries. Therefore, in this thesis, we first show the missing case in the Voros's strategy and show the ways to find it. Next, we show that the Peano curve is the best mapping function used in the nearest neighbor finding. We also show the transformation rules between the Peano curve and the other curves such that we can efficiently find the nearest neighbor, when the data is linearly ordered by the other curves. From our simulation, we show that our proposed two strategies can work correctly and faster than the conventional strategies in nearest neighbor finding. Finally, we present a revised version of NA-Trees, which can work for exact match queries and range queries from a large, dynamic index, where an exact match query means finding the specific data object in a spatial database and a range query means reporting all data objects which are located in a specific range. By large, we mean that most of the index must be stored in secondary memory. By dynamic, we mean that insertions and deletions are intermixed with queries, so that the index cannot be built beforehand.

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.