在以位置為基礎的服務下連續對移動物體作K個最近鄰居搜尋

在以位置為基礎的服務下連續對移動物體作K個最近鄰居搜尋  　

成功大學資訊工程學系碩士班  黃淵科

在無線網路的環境下, 對於移動中的物體都能利用 GPS 技術準確的將位置定位出來. 使用者可以在任何時間以及地點, 透過無線網路來查詢物體的位置. 提供與物體位置有關的查詢服務被稱為 Location Based Services (LBS).
在 LBS 所提供的查詢中, 舉一個例子來說, "告訴我在一段時間中, 那些離我最近的 K 間加油站". 這一類的查詢稱之為 continuous K-Nearset Nieghbor (CKNN) search.
由於查詢者與物體的位置都是隨著時間在變化, 造成 CKNN search 的結果也會隨著時間變化而不同. 過去有關解決 CKNN search 的研究, 不是以重複執行其方法才能找出結果, 便是為 CKNN search 作一些限制 (例如: 物體是靜止的, 只能找 C1NN) 以簡化問題. 在本篇論文中, 我們發展一個有效的演算法來解決 CKNN search. 另外, 我們也結合 index 來加速處理 CKNN search. 根據實驗的結果顯示, 我們方法的效能的確是優於其他的方法.