簡易檢索 / 詳目顯示

回結果列表
研究生： 廖世傑
Liao, Shi-Jei
論文名稱： 連續對移動速度與方向不確定之物體作 K 個最近鄰居搜尋
Continuous K-Nearest Neighbor Query for Moving Objects with Uncertain Speed and Uncertain Direction
指導教授： 李強
Lee, Chiang
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2007
畢業學年度： 95
語文別： 中文
論文頁數： 62
中文關鍵詞： 時間-空間資料庫 、查詢者的 K 個最近鄰居
外文關鍵詞： K-Nearest Neighbor, moving query object, spatio-temporal databases, moving objects, continuous K-Nearest Neighbor query
相關次數： 點閱：92  下載：2 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 在時間-空間資料庫系統所提供的查詢服務裡, 其中有一項重要的查詢稱之為 continuous K-Nearest Neighbor (CKNN) query.
    CKNN query 會判斷出在未來一段時間 ts 到 te 之內的每個時間點, 查詢者的 K 個最近物體, 而這些物體稱之為查詢者的 K 個最近鄰居 (簡稱為 KNN).
    在本篇論文中, 我們研究如何去有效地處理 CKNN query.
    不同以往的相關研究, 我們放寬過去物體為等速度且固定方向的假設, 允許物體的速度和方向各自介於一個範圍內移動.
    允許物體的速度與方向不固定讓我們的研究更符合現實生活的應用.
    由於物體的速度與方向的不確定, 使得處理 CKNN query 變的更加複雜.
    我們提出一個可以避免掉過去方法所面臨的缺點的方法來有效的處理 CKNN query.
    另外, 我們也發展一個有效的刪除策略並結合一個索引來減少 I/O 和 CPU 成本.
    根據實驗結果, 我們方法具有的良好的效能.

    One of the most important queries in spatio-temporal databases that aims at managing moving objects efficiently is the continuous K-Nearest Neighbor (CKNN) query.
    Given a future time interval [ts, te] and a moving query object q, a CKNN query is to retrieve the K-Nearest Neighbor (KNN) of q from ts to te.
    In this paper, we investigate how to process a CKNN query efficiently.
    Different from the previous related works, our work relieves the past assumption, that an object moves with a fixed speed and a fixed direction, by allowing that the speed and direction of the object can vary within a known range.
    Allowing objects move with uncertain speed and direction makes our work more suitable for the real-life applications.
    Due to the introduction of this uncertainty on the speed and direction of each object, processing a CKNN becomes much more complicated.
    We propose an approach to remedy the shortcomings of the previous work so as to efficiently process CKNN query.
    In addition, we also develop an efficient pruning strategy operated by the support of a data-partition index to achieve low I/O and CPU costs.
    Comprehensive experiments demonstrate the efficiency and effectiveness of our proposed approach.

    Abstract i Acknowledgements iii Table of Contents iv Table of Figures vii Table of Tables ix Table of Algorithms x 1 Introduction 1 2 Related Work 6 2.1 Index Structures . . . . . . . . . . . . . . . . . 6 2.1 Index Structures . . . . . . . . . . . . . . . . . 6 2.1.1 R-Tree . . . . . . . . . . . . . . . . . . . . . 6 2.1.2 TPR-Tree . . . . . . . . . . . . . . . . . . . . 7 2.2 CKNN Queries . . . . . . . . . . . . . . . . . . . 8 2.2.1 Moving objects with fixed velocity . . . . . . . 8 2.2.2 Moving objects with unknown velocity . . . . . . 11 2.2.3 Moving object with velocity within a range . . . 15 3 Uncertain Distance Model 18 3.1 The Minimal Distance Function do,q(t) . . . . . . . 19 3.1.1 The minimal distance between o and q at time t . 19 3.1.2 Computing the valid time interval . . . . . . . . 24 3.1.3 Determining the minimal distance function do,q(t) 30 3.2 The Maximal Distance Function Do,q(t) . . . . . . . 30 4 Pruning by the Support of a Data-Partitioning Index 32 4.1 Pruning Strategy . . . . . . . . . . . . . . . . . .32 4.2 TPRc-Tree Structure . . . . . . . . . . . . . . . . 33 4.3 Pruning Objects Using TPRc-Tree . . . . . . . . . . 36 4.3.1 Pruning Criteria . . . . . . . . . . . . . . . . .36 4.3.2 Branch-and-Bound Traversal on TPRc-Tree . . . . 38 5 Result Maintenance Mechanism 43 6 Experimental Evaluation 47 6.1 Experimental Settings . . . . . . . . . . . . . . . 48 6.2 Performance of the P2KNN algorithm . . . . . . . . .49 6.2.1 Effect of different query time nterval . . . . . .49 6.2.2 Effect of number of NNs (K) . . . . . . . . . . . 51 6.2.3 Effect of number of objects (N) . . . . . . . . . 52 6.3 The impact ofmoving speed and direction . . . . . . 53 6.3.1 Effect of uncertain speed . . . . . . . . . . . . 53 6.3.2 Effect of uncertain direction . . . . . . . . . . 54 6.4 Efficiency of the result maintenance mechanism . . .55 7 Conclusions 57 Bibliography 58 Biography 62

    [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.

    [CKP04] R. Cheng, D. V. Kalashnikov, and S. Prabhakar, “Querying Imprecise Data in Moving Object Environments,” IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 9, pp. 1112-1127, 2004.

    [Gut84] A. Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching,” in ACM SIGMOD Conf, 1984, pp 47-57.

    [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.58

    [ISS03] Glenn Iwerks, Hanan Samet, and Ken Smith, “Continuous KNearest Neighbor Queries for Continuously Moving Points with Updates,” in International Conference on Very Large Data Bases, Berlin, Germany, September 9-12 2003.

    [MHP05] KyriakosMouratidis, Marios Hadjieleftheriou, and Dimitris Papadias,“Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring,” in Proceedings of the ACM SIGMOD, 2005.

    [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.

    [RKV95] Nick Roussopoulos, Stephen Kelley, and Fr’ed’eric Vincent,“Nearest neighbor queries,”in Proceedings of ACM Sigmod, 1995, pp 71-79.

    [RPM03] K. Raptopoulou, A. N. Papadopoulos, and Y. Manolopoulos,“Fast Nearest-Neighbor Query Processing in Moving-Object Databases,” in Geoinformatica, vol. 7, pp.113-137, 2003.

    [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.

    [SR01] Zhexuan Song and Nick Roussopoulos, “K-Nearest Neighbor Search for Moving Query Point,” in Proceedings of 7th International Symposium on Advances in Spatial and Temporal Databases, LNCS2121, Redondo Beach, CA, USA, July 12-15 2001, pp 79-96.

    [TFWG00] G.B. Thomas, R.L. Finney, M.D. Weir, and F.R. Giordano,“Thomas’ Calculus,” 10th ed., Addison Wesley, 2000.

    [TP02] Yufei Tao and Dimitris Papadias, “Time Parameterized Queries in Spatio-Temporal Databases,” in Proceedings of the 2002 ACM SIGMOD international conference on Management of data, Madison, Wisconsin, 2002, pp. 334-345.

    [TWZC02] Goce Trajcevski, Ouri Wolfson, Fengli Zhang and Sam Chamberlain, “The Geometry of Uncertainty in Moving Objects Databases,” in Proceedings of the 8th International Conference on Extending Database Technology, 2002, pp. 233-250.

    [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.

    [WSCY99] A. P. Sistla, O. Wolfson, S. Chamberlain, and Y. Yesha, “Updating and querying databases that track mobile units,” Distributed and Parallel Databases, vol. 7, no. 3, pp. 257-387, 1999.

    [XMA05] Xiaopeng Xiong, Mohamed F. Mokbel, and Walid G. Aref, “SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-temporal Databases,” ICDE, 2005.

    [YPK05] Xiaohui Yu, Ken Q. Pu, and Nick Koudas, “Monitoring KNearest Neighbor Queries Over Moving Objects,” ICDE, 2005.

    下載圖示 校內：2008-08-27公開
    校外：2008-08-27公開
    QR CODE