[發明專利]一種路網移動環境下的KNN查詢方法及系統

有效

• 申請號: 201710690023.3
• 申請日: 2017-08-14
• 公開（公告）號: CN107291963B
• 公開（公告）日: 2020-11-24
• 發明（設計）人: 吳洪麗
• 申請（專利權）人: 海南師范大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/29;G06F16/9535;G06F16/9537
• 代理公司: 廣州三環專利商標代理有限公司 44202
• 代理人: 陳歡

本發明公開了一種路網移動環境下的KNN查詢方法，包括：獲取路網中移動對象和移動查詢點之間的距離范圍；根據距離范圍在給定時間段內持續獲取移動對象信息，得到第一候選集；將第一候選集中不可能成為移動查詢點的KNN查詢結果的移動對象信息過濾掉，得到第二候選集；根據第二候選集向第三方互聯網地圖服務商發送時空查詢請求，并接收第三方互聯網地圖服務商返回的距離度量；基于距離度量生成移動查詢點的KNN查詢結果。同時，本發明還公開了一種路網移動環境下的KNN查詢系統。本發明充分考慮了路網的高度動態性和不可預測性，能夠反映出真實的路況信息，提供更準確的查詢結果。

技術領域

本發明涉及基于位置服務的信息查詢技術領域，具體涉及一種路網移動環境下的KNN查詢方法及系統。

背景技術

“車－路”信息系統一直是智能交通發展的重點領域。車聯網是指利用先進傳感技術、網絡技術、計算技術、控制技術、智能技術，對道路和交通進行全面感知，實現多個系統間大范圍、大容量數據的交互，對每一輛汽車進行交通全程控制，對每一條道路進行交通全時空控制，以提供交通效率和交通安全為主的網絡與應用。可以說，車聯網將是繼互聯網、物聯網之后，成為未來智能城市的另一個標志。

在車聯網這樣一個移動環境中，(司機)用戶常常需要訪問跟他們所在的地理位置相關的數據和信息。比如通過互聯網和無線接入技術(如藍牙、WiFi、GPRS、3G、衛星技術等)，用戶希望能隨時隨地獲得如交通運輸信息、商貿信息、天氣信息、公共設施的位置等信息。對這些位置相關信息的需求也促進了許多與位置相關的服務(Location BasedServices，LBS)的產生和發展，其中LBS的查詢，也被稱為位置相關查詢(LocationDependent Queries，LDQ)就是位置相關服務的一個重要技術支持。位置相關查詢的應用主要包括了范圍查詢、最近鄰居查詢、反向最近鄰居查詢等。LDQ是基于時空數據庫上抽象查詢的一種實際應用，比較典型的有范圍查詢(例如，查找給定區域里有多少輛車子)和k最近鄰點查詢(k-nearest-neighbor query)(例如，查找離我最近的加油站和5家飯店)。

傳統時空查詢的距離度量大部分都是基于兩點之間的物理距離，即歐氏距離或者網絡距離，但這種距離度量不會考慮到實際路況(比如交通擁塞和事故、道路施工等)，因此離用戶最近的不一定就是行駛時間最短的。圖1是基于物理距離與基于行駛時間的查詢結果對比圖，如圖1所示，在該示例中某一急診病人需要查找離他最近的醫院，傳統的基于物理距離的最近鄰查找算法會返回X醫院。然而，基于行駛時間的最近鄰查找算法會返回Y醫院，因為開車到Y的時間遠遠低于開車到X的時間。所以說，行駛時間相比于傳統的距離度量方式更可靠更切實際，基于行駛時間的時空查詢也變得更有意義。

然而，相對于歐氏距離或者網絡距離，行駛時間具有高度動態性，兩點之間的行駛時間很難被實時而又準確預測到。例如，洛杉磯I-10上一段高速公路在上午8點半需要30分鐘行駛時間而在上午9點半卻只需要行駛18分鐘，行駛時間減少了將近40％。提供行駛時間最佳的方式是實時監控道路的交通狀況，如部署攝像頭、傳感器以及收集車輛GPS信息等。然而，并不是每一個LBS提供方都能夠完成這種部署，因為這種部署不僅代價昂貴而且也容易涉及到用戶隱私問題。

近年來，研究者們對位置相關查詢(時空查詢)，特別是最近鄰查詢和反向最近鄰查詢進行了深入的研究，提出了許多的查詢處理技術來有效地支持各種空間與時空對象的查詢問題。但是，在最近鄰查詢方面，目前尚無人提出路網中可變速移動對象的連續最近鄰查詢算法。

歐氏空間下，對象與對象之間的距離只取決于對象的坐標值。而現實生活中，移動對象大多情況下是活動在網路環境下，如公路網、鐵路網等，對象之間的距離由路網的連通性來決定。歐氏空間環境下的相關算法是不能通過簡單的修改而應用到路網環境下的。

最近鄰查詢作為時空查詢處理技術中最重要的類型之一，已經成為空間與時空數據庫領域的一個研究重點與熱點。研究者們對最近鄰查詢進行了廣泛、深入地研究，許多最近鄰查詢算法已經被提出。