跳到主要內容

臺灣博碩士論文加值系統

(3.231.230.177) 您好!臺灣時間:2021/07/28 18:33
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:王炳竣
研究生(外文):Ping-Chun Wang
論文名稱:針對有不確定性之移動物體設計一個有效索引來處理時間-空間查詢
論文名稱(外文):An Efficient Index for Processing Spatio-Temporal Queries over Moving Objects with Uncertainty
指導教授:李強李強引用關係
指導教授(外文):Chiang Lee
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:中文
論文頁數:73
中文關鍵詞:不確定性索引移動物體時間-空間查詢
外文關鍵詞:range queryuncertaintyK-nearest neighbor queryspatial join queryspatio-temporal queriesmoving objects
相關次數:
  • 被引用被引用:0
  • 點閱點閱:158
  • 評分評分:
  • 下載下載:17
  • 收藏至我的研究室書目清單書目收藏:0
近幾年來,由於在高度動態的環境下對於即時訊息的需求,管理空間中位置不確定的移動物體並有效率的處理時間-空間查詢是日益重要的課題。在本篇論文中,我們討論如何處理三種重要的時間-空間查詢: range query, $K$-nearest neighbor query 以及 spatial join query。處理時間-空間查詢的相關研究中,都採用設計索引架構來管理移動物體,並利用索引增進處理查詢時的效能。但現今管理位置不確定的移動物體之索引都存在一些缺點: 更新時效能較差或是處理查詢時過濾物體的效能較差。有鑑於此,我們設計了一個有效率的索引,稱為possible region index (簡稱為 PRI),來專門管理位置不確定的移動物體。我們並設計了一個有效率的位置更新機制,可以有效減少物體更新的次數。最後我們設計了總合性的實驗來証實 PRI 在更新以及處理查詢時都有好的效能。
Efficient processing the spatio-temporal queries over moving objects with uncertain location has become imperative in recent years due to the increasing need for real-time information in highly dynamic environments. In this thesis, we investigate how to process three important types of spatio-temporal queries. They are range query, K-nearest neighbor query, and spatial join query. Most of the existing approaches focus on designing an index structure for managing moving objects with uncertainty, and then utilize it to improve the query performance. All the proposed indexes, however, have some serious shortcomings (such as the high index update cost or the low pruning ability) which limit their improvement in processing the spatio-temporal queries. Therefore, we devote to developing a novel and efficient index, named possible region index (PRI), to index moving objects with uncertainty. By exploiting a well-designed location update strategy,
the PRI needs not be updated frequently. Moreover, it can achieve better query performance than the existing indexes.
Comprehensive experiments demonstrate the efficiency of the PRI in terms of the update cost and the query performance.
目錄
Abstract i
Table of Contents iii
Table of Figures vi
Table of Tables ix
1 Introduction . . . . . . . . . . . . . . . . .1
2 Related Work . . . . . . . . . . . . . . . . .7
2.1 U-Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Index Using Dual Transformation . . . . . . . . . . . . . . 10
2.3 Velocity Constrained Index . . . . . . . . . . . . . . . . . . 11
2.4 TPR(s,d)-tree . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Uncertainty Model and Index Structure . . . . . . . . . . . . . . . . .17
3.1 UncertaintyModel . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Possible Region Index . . . . . . . . . . . . . . . . . . . . 18
3.2.1 Location Transformation . . . . . . . . . . . . . . . 19
3.2.2 Speed Transformation . . . . . . . . . . . . . . . . 20
3.2.3 Angle Transformation . . . . . . . . . . . . . . . . 21
3.2.4 Index Structure . . . . . . . . . . . . . . . . . . . . 22
3.3 PRI Update Operation . . . . . . . . . . . . . . . . . . . . 23
3.3.1 When to Update PRI . . . . . . . . . . . . . . . . . 23
3.3.2 How to Update PRI . . . . . . . . . . . . . . . . . 27
4 Query processing . . . . . . . . . . . . . . . . .28
4.1 Flow Chart of Query Processing . . . . . . . . . . . . . . . 28
4.1.1 Sampling-based Probability Model . . . . . . . . . 29
4.2 Range query . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.2.1 Filtering Phase for Range Query . . . . . . . . . . 30
4.2.2 Refinement Phase for Range Query . . . . . . . . . 37
4.2.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 KNN query . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3.1 Pruning Distance . . . . . . . . . . . . . . . . . . . 39
4.3.2 Node ExtendMethod . . . . . . . . . . . . . . . . . 40
4.3.3 Filtering Phase for KNN Query . . . . . . . . . . . 42
4.3.4 Refinement Phase for KNN Query . . . . . . . . . 43
4.4 Spatial Join Query . . . . . . . . . . . . . . . . . . . . . . 45
4.4.1 Filtering Phase for Spatial Join Query . . . . . . . 45
4.4.2 Refinement Phase for Spatial Join Query . . . . . . 49
5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . 51
5.1 Experimental Settings . . . . . . . . . . . . . . . . . . . . 51
5.1.1 Performance Metrics . . . . . . . . . . . . . . . . . 53
5.1.2 Compared Index . . . . . . . . . . . . . . . . . . . 53
5.2 Performance of the query processing . . . . . . . . . . . . 54
5.2.1 Range query . . . . . . . . . . . . . . . . . . . . . . 54
5.2.2 KNN query . . . . . . . . . . . . . . . . . . . . . . 58
5.2.3 Spatial join query . . . . . . . . . . . . . . . . . . . 60
5.3 Index update cost . . . . . . . . . . . . . . . . . . . . . . . 62
5.3.1 The impact of update radio . . . . . . . . . . . . . . 62
5.3.2 The impact of Areamax . . . . . . . . . . . . . . . . 62
5.3.3 The impact of data − size on update cost . . . . . 63
5.4 Accuracy of Query Result . . . . . . . . . . . . . . . . . . 63
5.4.1 The impact of sampling numbers . . . . . . . . . . 64
5.4.2 The impact of Max update time . . . . . . . . . . . 65
6 Conclusions and Future Work . . . . . . . . . . . . . . . . . . 67
[B71] A. R. Butz, “Alternative Algorithm for Hilbert’s Space-Filling Curve,” In IEEE Trans. Comput., 1971, 20(4), 424-426.
[BJKS02] Rimantas Benetis, Christian S. Jensen, Gytis Karciauskas, and Simonas Saltenis, “Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects,” in International Database Engineering and Applications Symposium, Canada, July 17-19 2002.
[BJKS06] Rimantas Benetis, Christian S. Jensen, Gytis Karciauskas, and Simonas Saltenis, “Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects,” in VLDB Journal, vol.15, no. 3, pp. 229-249, September 2006.
[BKS93] T. Brinkhoff, H-P Kriegel and B. Seeger,“Efficient Processing of Spatial Joins using R-trees,” In SIGMOD Conference, 1993, pp.237 - 246.
[BKSS90] Norbert. Beckmann, Hans.Peter. Kriegel, Ralf. Schneider, Bernhard. Seeger, “The R∗-Tree: An Efficient and Robust Access Method for Points and Rectangles,” in ACM SIGMOD Conf, 1990, pp. 322-331.
[BSI08] George Beskales, Mohamed A. Soliman, Ihab F. IIyas, “Efficient search for the top-k probable nearest neighbors in uncertain databases,” In VLDB Conference, 2008 pp. 326 - 339.
[CKP04] Reynold Cheng, Sunil Prabhakar, Dmitri V. Kalashnikov, “Querying Imprecise Data in Moving Object Environments,” In IEEE Transactions on Knowledge and Data Engineering, 2004, 16(9), pp. 1112-1127.
[CLC09] Bruce S. E. Chung, Wang-Chien Lee, Arbee L. P. Chen, “Processing probabilistic spatio-temporal range queries over moving objects with uncertainty,” In EDBT Conference, 2009, pp. 60-71.
[CLH03] S. Y. Lin, C. S. Chen, L. Liu, and C. H. Huang, “Tensor Product Formulation for Hilbert Space-Filling Curves,” In Proceedings of the 2003 International Conference on Parallel Processing, 2003, pp. 99-
106.
[CLH04] C. S. Chen, S. Y. Lin, and C. H. Huang, “Algebraic Formulation and Program Generation of Three-Dimensional Hilbert Space-Filling Curves,” In Proceedings of the 2004 International Conference on Imaging Science, Systems, and Technology, 2004, pp. 254-260.
[CP07] Yun Chen, Jignesh M. Patel, “Efficient Evaluation of All-Nearest-Neighbor Queries,” In ICDE Conference, 2007, pp. 1056 - 1065.
[CXPS+04] Reynold Cheng, Yuni Xia, Sunil Prabhakar, Rahul Shah, Jeffrey Scott Vitter, “Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data,” In VLDB Journal, 2004, pp. 876-887.
[Gut84] A. Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching,” in ACM SIGMOD Conf, 1984, pp. 47-57.
[HCL09] Yuan-Ko Huang, Chao-Chun Chen, Chiang Lee, “Continuous K-Nearest Neighbor Query for Moving Objects with Uncertain Velocity,”In GeoInformatica, 2009, 13(1), pp. 1-25.
[HCL06] Yuan-Ko Huang, Chao-Chun Chen, and Chiang Lee, “Continuous K-Nearest Neighbor Query for Moving Objects with Uncertain Velocity,” Department of Computer Science and Information Engineering, National Cheng Kung University, 2006,
http://dblab.csie.ncku.edu.tw/∼wbsyok/tech cknn queries.ps.
[HJR97] Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner “Spatial Joins Using R-Trees: Breadth-First Traversal with Global Optimizations,”In VLDB Conference, 1997, pp. 396 - 405.
[HKLT+09] Wook-Shin Han, Jaehwa Kim, Byung Suk Lee, Yufei Tao, Ralf Rantzau, Volker Markl, “Cost-Based Predictive Spatiotemporal Join,” In IEEE TKDE, 2009, pp. 220 - 233.
[HLL09] Yuan-Ko Huang, Shi-Jei Liao, Chiang Lee, Evaluating continuous K-nearest neighbor query on moving objects with uncertainty,”In Proceedings of the Information Systems, 2009 to appear.
[JLO04] C. S. Jensen, D. Lin, B.C. Ooi, “Query and Update Efficient B+-Tree Based Indexing of Moving Objects,” In VLDB Conference, 2004, pp. 768-779.
[JTT06] C. S. Jensen, D. Tiesyte, and N. Tradisauskas, “Robust B+-Tree-Based Indexing of Moving Objects,” In Proc. MDM, 2006, pp.12.
[KKM07] H.P. Kriegel, P. Kunath, M. Renz, “Probabilistic nearestneighbor query on uncertain objects,” InProceedings of the 12th International Conference on Database Systems for Advanced Applications, Volume 4443 of lecture Notes in Computer Science, Springer (2007) 337 - 348.
[KPGT05] George Kollios, Dimitris Papadopoulos, Dimitrios Gunopulos, Vassilis J Tsotras, “Indexing Mobile Objects Using Dual Transformations,”In VLDB Journal, 2005, 14 pp. 238-256.
[LWHS06] Min-Jae Lee, Kyu-Young Whang, Wook-Shin Han, I.-Y. Song,“Transform-Space View: Performing Spatial Join in the Transform Space Using Original-Space Indexes,” In IEEE TKDE, 2006, pp. 245 - 260.
[MJFS01] B. Moon, H.V. Jagadish, C. Faloutsos, and J. H. Saltz. “Analysis of the Clustering Properties of the Hilbert Space-Filling Curve,”In IEEE TKDE, 13(1): 124-141, 2001.
[PJ99] Dieter Pfoser, Christian Jensen, “Capturing the Uncertainty of Moving-Object Representations,” In Advances in Spatial Databases, 1999, pp. 111–131.
[PSTM04] Dimitris Papadias and Qiongmao Shen and Yufei Tao and KyriakosMouratidis, “Group Nearest Neighbor Queries,” in Proceedings the 20th International Conference on Data Engineering, 2004.
[PXKA+02] S. Prabhakar, Y. Xia, D. V. Kalashnikov, W. G. Aref, and S. E. Hambrusch, “Query Indexing and Velocity Constrained Indexing:Scalable Techniques for Continuous Queries on Moving Objects,” In IEEE Transactions on Computers, 51(10):1124-1140, 2002.
[Sam90a] Hanan Samet, “The Design and Analysis of Spatial Data Structures,”Addison-Wesley, ISBN 0-201-50255-0, 1990.
[Sam90b] Hanan Samet, “Application of Spatial Data Structure,”Addison-Wesley, ISBN 0-201-50300-X, 1990.
[Sequoia] http://www.rtreeportal.org/datasets/spatial/US/Sequoia.zip
[SJLL00] Simonas Saltenis, Christian S. Jensen, Scott T. Leutenegger, and Mario A. Lopez, “Indexing the Positions of ContinuouslyMoving Objects,” in SIGMOD Conference, 2000, pp. 331-342.
[STPK06] J. Sun, Y. Tao, D. Papadias, and G. Kollios, “Spatio-Temporal Join Selectivity,” In Information Systems, vol. 31, no. 8, pp. 793 - 813, 2006.
[TCXN+05] Yufei Tao, Reynold Cheng, Xiaokui Xiao, Wang Kay Ngai, Ben Kao, Sunil Prabhakar, “Indexing multi-dimensional uncertain data with arbitrary probability density functions,” In VLDB Conference, 2005, pp. 922-933.
[TPS03] Y, Tao., D. Papadias, J. Sun, “The TPR∗-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries,” In VLDB Conference, 2003, pp. 790-801.
[TTDS+09] Goce Trajcevski, Roberto Tamassia, Hui Ding, Peter
Scheuermann, Isabel F. Cruz, “Continuous probabilistic nearestneighbor queries for uncertain trajectories,” In EDBT Conference, 2009, pp. 874-885.
[TWHC04] Goce Trajcevski, Ouri Wolfson, Klaus Hinrichs and
Sam Chamberlain, “Managing Uncertainty in Moving Objects
Databases,” in ACM Transactions on Database Systems, vol. 29, no.3, September 2004, pp. 463-507.
[TXC07] Y. Tao, X. Xiao, and R. Cheng, “Range search on multidimensional uncertain data,” In ACM Transactions on Database Systems, 2007, 32(3).
[YTM08] Man. Lung. Yiu, Yufei. Tao, Nikos. Mamoulis, “The Bdual-Tree: Indexing Moving Objects by Space Filling Curves in the Dual Space,”In VLDB Journal, 2008, 17(3) pp. 379-400.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top