簡易檢索 / 詳目顯示

回結果列表
研究生： 王炳竣
Wang, Ping-Chun
論文名稱： 針對有不確定性之移動物體設計一個有效索引來處理時間-空間查詢
An Efficient Index for Processing Spatio-Temporal Queries over Moving Objects with Uncertainty
指導教授： 李強
Lee, Chiang
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2009
畢業學年度： 97
語文別： 中文
論文頁數： 73
中文關鍵詞： 不確定性 、索引 、移動物體 、時間-空間查詢
外文關鍵詞： range query, uncertainty, K-nearest neighbor query, spatial join query, spatio-temporal queries, moving objects
相關次數： 點閱：78  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 近幾年來，由於在高度動態的環境下對於即時訊息的需求，管理空間中位置不確定的移動物體並有效率的處理時間-空間查詢是日益重要的課題。在本篇論文中，我們討論如何處理三種重要的時間-空間查詢: 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.

    下載圖示 校內：2011-08-26公開
    校外：2011-08-26公開
    QR CODE