(18.210.12.229) 您好!臺灣時間:2021/02/26 09:30
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:張健鴻
研究生(外文):Chang Chien-Hung
論文名稱:連續移動物件之有效索引方法
論文名稱(外文):Efficient indexing methods for continuously moving objects
指導教授:李瑞庭李瑞庭引用關係
指導教授(外文):Anthony J.T. Lee
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊管理研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:60
中文關鍵詞:移動物件索引方法
外文關鍵詞:moving objectindexing method
相關次數:
  • 被引用被引用:0
  • 點閱點閱:78
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:5
  • 收藏至我的研究室書目清單書目收藏:0
近幾年來,使用無線通訊設備的人口成長非常快。為了提供使用者更好的服務,無線設備在很多領域中被廣泛地應用。對於資料庫來說,要持續且精確地追蹤移動物件的位置是很難的。在傳統資料庫中所提出的索引方法是針對靜態物件設計的,不適合用來索引移動物件。
物件的位置隨著時間而變動,要隨時更新資料庫中物件的位置需要很高的更新成本。所以本研究將物件移動的軌跡用線性方程式描述,在資料庫中只記錄線性方程式的參數而不是物件的位置。當線性方程式的參數改變時才更新資料庫以節省更新成本。
在本論文中提出了三種索引方法。首先本研究提出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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
1. 64. 黃國隆(民75):「中學教師的組織承諾與專業承諾」,國立政治大學學報,第53期,頁55-84。
2. 60. 盛立軍(民88):「整合力量,創造新價值」,管理雜誌,第296期,頁40-42。
3. 59. 曾銘宗(民89.06):「農會信用部改制之探討」,今日合庫,第308期,頁9-18。
4. 54. 陳金貴(民82):「美國非營利組織的分析」,行政學報25,頁27-46。
5. 71. 廖朝賢(民90) :「89年台灣地區各級農會營運分析」,農訓雜誌18卷11期,頁4~7。
6. 36. 孫炳焱(民77):「強化組織活力,提昇農會功能─回歸國際合作原則的建議」,今日合庫,14卷6期,頁11-24。
7. 78. 蔣憲國(民89):「台灣廣域農會合併之探討─從日本廣域農協合併的經驗論起」,農業金融論叢,43期,頁43-73。
8. 26. 林維義(民88): 「農會信用部經營危機之改革方向探討」,金融財務,第3期,頁13∼14。
9. 76. 蔡勝佳(民88):「談台灣農會面臨的緊要課題與對策」,合作經濟,第62期,頁32-35。
10. 25. 林盟城(民86):「析論金融產業之購併活動」,產業金融季刊,頁38-48。
11. 82. 蕭崑杉(民74):「台灣基層農會組織內部關係之研究」,農業金融論叢,第14期,頁91-114。
12. 72. 劉光華(民83):「組織變革之理念與途徑」,人事月刊,第18卷4期,頁8-15。
13. 20. 余尚武、江玉柏(民87):「影響企業購併成敗因素與策略探討」,經濟情勢暨評論季刊,四卷二期,國際購併趨勢與台灣產業發展專輯,頁125-144。
14. 5. 江明修(民83):「非營利組織領導行為之研究」,人事管理,33(10):頁4-13;33(12):頁22-41。
 
系統版面圖檔 系統版面圖檔