近幾年來，使用無線通訊設備的人口成長非常快。為了提供使用者更好的服務，無線設備在很多領域中被廣泛地應用。對於資料庫來說，要持續且精確地追蹤移動物件的位置是很難的。在傳統資料庫中所提出的索引方法是針對靜態物件設計的，不適合用來索引移動物件。
物件的位置隨著時間而變動，要隨時更新資料庫中物件的位置需要很高的更新成本。所以本研究將物件移動的軌跡用線性方程式描述，在資料庫中只記錄線性方程式的參數而不是物件的位置。當線性方程式的參數改變時才更新資料庫以節省更新成本。
在本論文中提出了三種索引方法。首先本研究提出MBR-tree。MBR-tree借由計算出樹中包圍矩形的最小擴張速度以包含下層所有子樹中的矩形及移動物件。這樣一來可以減少許多不必要的重疊區域，增進搜尋的效率。
接下來提出MBS-tree，MBS-tree將MBR-tree中的包圍矩形換成球形，也就是利用球來包圍下層所有的移動物件。本研究也提出計算包圍球形的最小擴張速度以包含下層所有子樹中的球形及移動物件。
MBR-tree和MBS-tree都會產生許多互相重疊的區域，而這些重疊區域會影響搜尋的效率。所以本研究提出MQ-tree。MQ-tree將要搜尋的空間作等分切割成四塊，然後將移動物件在這四個區塊的移動情形分成24個情況，根據物件移動的情形來建構MQ-tree。

In the coming years, the population using wireless devices will grow rapidly. With providing special services for each individual customer, the wireless devices are becoming more and more popular. Tracking the positions of moving objects is hard for the indexing methods of the current database systems. The reason is that most of proposed indexing methods are suitable for still(not-moving) objects, not for moving objects. Since the positions of moving objects are changed over time, it’s impossible for the indices in the database to keep the correct positions of moving objects. If we try to update the positions of moving objects immediately when they move, the cost is really high.
In this thesis, we first propose the MBR-tree with the minimum boundary velocity for each bounding rectangle. This makes the bounding rectangles not grow so rapid and the overlapping areas are reduced effectively. The MBR-tree uses a bounding rectangle to cover all the objects or rectangles within the bounding rectangle. This motivates us to use a different shape to enclose moving objects. So, we propose the MBS-tree that uses a bounding sphere to enclose moving objects. We also propose an algorithm to compute the minimum boundary velocity for a bounding sphere. The MBR-tree and the MBS-tree use a rectangle or sphere to enclose all moving objects. These methods will generate a lot of overlapping areas and such overlapping areas will reduce the performance of the MBR-tree and the MBS-tree. Therefore, we propose the MQ-tree in which the whole data space is partitioned into no overlapping regions. Next we classify all the moving objects into three types and 24 cases of movements. Then we recursively construct the MQ-tree according to the cases of movements.

Chapter 1 Introduction 1
Chapter 2 Background and Literature Survey 3
2.1 Problem statement 3
2.2 Techniques of indexing the still objects in the d-dimensional space 4
2.2.1 R-tree 4
2.2.2 R*-tree 8
2.2.3 SS-tree 8
2.3 Techniques of indexing moving objects in the d-dimensional space 10
2.3.1 TPR-tree 10
2.3.2 LUR-tree 13
2.4 Discussion 16
Chapter 3 Proposed Index Structures 17
3.1 MBR-tree 17
3.2 MBS-tree 19
3.2.1 The minimum bounding sphere of points 19
3.2.2 The minimum bounding sphere of spheres 25
3.3 MQ-tree 29
Chapter 4 Experimental Results 38
4.1 Experiment setup 38
4.2 Compare each index structure 40
4.3 Simulation model 44
Chapter 5 Conclusions and Future Work 50
References 52

[1] N. Beckmann, H. Kriegel, R. Schneider, and B. Seeger, “The R* tree: An efficient and robust access method for points and rectangles,” Proc. of the ACM SIGMOD Intl. Conf. on Management of Data, June 1990.
[2] D.J. Elzinga and D.W. Hearn, “The Minimum Covering Sphere Problem.” Management Science 19(1) , pp. 96-104, 1972.
[3] Kaspar Fischer, “The Smallest Enclosing Ball of Balls,” Technical Report, Institute for Theoretical Computer Science, April 3, 2001.
[4] A. Guttman, ”R-Trees: A Dynamic Index Structure for Spatial Searching,” In Proc. Of the ACM SIGMOD Conference, Boston, USA, pp.47-57, 1984.
[5] Hopp, T.H. and Reeve C.P., “An Algorithm for Computing the Minimum Covering Sphere in Any Dimension,” SIAM J. of Computing, 1996.
[6] H.P. Kriegel, M. Schiwietz, R.Schneider, and B. Seeger. Performance Comparison of Point and Spatial Access Method. In First Symposium SSD：Design and Implementation of Large Spatial Databases, page 89-114,1989.
[7] Dongseop Kwon, Sangjun Lee, Sukho Lee, “Indexing the Current Positions of Moving Objects Using the Lazy Update R-tree,” Proceedings of the third IEEE International Conference on Mobile Data Management, 2002.
[8] J. Moreira, C. Ribeiro, and J. Saglio, “Representation and Manipulation of Moving Points: An Extended Data Model for Location Estimation,” Cartography and Geographical Information Systems, 1999.
[9] D. Pfoser and C. S. Jensen, “Capturing the Uncertainty of Moving-Object Representations,” Proc. of the SSDBM Conf., pp. 111—132 , 1999.
[10] Simonas Saltenis, Christian S. Jensen, Scott T. Leutenegger, Mario A. Lopez, “Indexing the Positions of Continuously Moving Objects,“ Technical Report, Department of Computer Science, Aalborg University, Denmark, Department of Mathematics and Computer Science, University of Denver, Colorado, USA, 2000.
[11] Z. Song and N. Roussopoulos, “Hashing moving objects,” Proc. Of the 2nd Int’l. Conf. On Mobile Data Management, 2001.
[12] D. A.White, Jain R., ”Similarity Indexing with the SS-tree,” Proc. Of the 12th Int. Conf. On Data Engineering, 1996.
[13] O. Wolfson, A. P. Sistla, S. Chamberlain, and Y. Yesha, “Updating and Querying Databases that Track Mobile Units,” Distributed and Parallel Databases 7(3) , 257 — 387 , 1999.