《時間依賴路網中連續k近鄰查詢處理技術研究》是依託瀋陽航空航天大學，由李佳佳擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：時間依賴路網中連續k近鄰查詢處理技術研究
- 項目類別：青年科學基金項目
- 項目負責人：李佳佳
- 依託單位：瀋陽航空航天大學
項目摘要,結題摘要,
項目摘要
儘管基於路網環境的連續k近鄰查詢處理技術已經取得了豐富的研究成果，但這些成果主要針對權值是常量的靜態路網套用環境，無法直接套用到權值是動態變化的時間依賴路網中。在時間依賴路網中，由於受到路況條件或交通事故的影響，路網中邊的權值隨著時間變化而改變。時間依賴路網下連續k近鄰查詢在智慧型導航、位置廣告、緊急救援等領域展現了廣闊的套用前景。查詢結果不僅與查詢點的位置有關，還與發出查詢的時間有關，道路網中出行路徑的選擇以及連續k近鄰的計算過程變得更加複雜。這對路網的索引技術、連續k近鄰查詢處理技術以及連續查詢服務質量控制技術提出了新的挑戰。目前，針對時間依賴路網下連續k近鄰查詢的研究較少，本申請針對時間依賴網路以及連續k近鄰查詢的特點，深入地研究相關的路網索引模型與索引更新策略、k近鄰查詢的多種剪枝策略、連續查詢的結果維護策略，以及服務質量的評價模型與卸載策略等問題。
結題摘要
近鄰及近鄰相關查詢做為時空資料庫中重要的查詢類型，在歐氏空間和路網空間中被廣泛研究。但在邊權值是動態變化的時間依賴路網環境中，研究成果較少。由於邊權值隨著時間的改變而變化，路網中兩點間的代價計算變得複雜，已有技術不能直接套用在時間依賴路網中的近鄰查詢問題中。本項目針對時間依賴路網中連續k近鄰查詢的特點，深入地研究了：（1）時間依賴路網索引模型與索引更新策略；（2）時間依賴路網k近鄰以及相關查詢的多種剪枝策略、連續查詢的結果維護策略；（3）查詢服務質量最佳化；（4）數據產生及結果展示原型系統。主要成果如下： （1）索引結構：利用格線，提出了基於興趣點分布的合併策略，設計了時間依賴路網索引結構，使範圍查詢、近鄰查詢和最快路徑查詢，回響時間減少了34%到60%。 （2）k近鄰及相關查詢：（a）提出了基於動態選擇啟發值的k近鄰改進算法，使查詢回響時間減少了47%；（b）基於預計算和線上擴展結合的方式，提出了k近鄰查詢最佳化方法，回響時間減少了40%；（c）提出了基於子網劃分的反向k近鄰查詢算法，解決了已有算法在興趣點分布稀疏時，查詢效率低的問題，比已有算法遍歷結點數少50%；（d）針對機率剪枝階段子區域劃分粒度無法動態調整的問題，提出了基於分類的機率組近鄰查詢最佳化算法，回響時間減少了2-3倍；（e）針對單次快速k近鄰查詢無法有效解決連續k近鄰查詢的問題，提出了基於分割點的連續查詢結果計算和維護算法，回響時間上減少了近一個數量級。 （3）查詢服務質量最佳化：基於計程車軌跡數據，考慮時間、是否工作日、天氣、交通異常數據、相鄰路段之間相互影響的因素，對行駛時間函式進行了預測，提高了傳統方法的預測精度，進而提高了服務質量。 （4）原型系統：利用JAVA技術，開發了時間依賴路網仿真系統，系統可根據不同的工作日、時間、天氣、興趣點類型等參數，為科研人員生成多種時間依賴網路數據集。還能夠通過預留的算法接口，在地圖上顯示出不同查詢的結果。
