位置搜索關鍵技術研究

楊德利，袁立宇，張 濤，徐 雄

（中國電信股份有限公司廣東研究院 廣州510630）

1 引言

近幾年來，位置服務（location based services，LBS）的快速發展引起了國家科技行政部門的高度重視。《國家中長期科學和技術發展規劃綱要 （2006-2020年）》、《國家“十二五”科學和技術發展規劃》都提出要積極發展導航與地理信息服務產業。在產業趨勢和國家政策支持下，近年來，國內、外互聯網公司和運營商都非常看好LBS的發展空間，紛紛推出了自己的LBS應用。但在這些應用中，用戶都要面對“超載”的海量信息。怎樣根據用戶的行為數據以及實時信息，準確判斷用戶的喜好，并在此基礎上向用戶提供最相關的產品、服務是解決所謂“信息超載”問題的有效手段，因此產生了對位置搜索的廣泛需求。

位置搜索[1，2]，即基于位置的搜索，是從各類信息源（如POI引擎、各類應用系統等）中采集位置相關信息，經分析、挖掘等工作后，向應用系統提供POI信息的能力和位置相關的信息搜索、推薦能力。位置搜索的目標是在一定地理區域內的對象或信息，被搜索的對象可以是一個點，如一個人或一個商店，在空間域就表示為一個以經緯度表示的點；但也可能是一個面，甚至是一個三維立體的對象。本文不對空間計算技術展開全面的探討，而是主要聚焦于點在平面上的搜索，這些點可以是移動的人或物體（查看周邊好友），也可以是固定的POI，如商店、景點等（本地商家搜索）。

2 位置搜索需求及特性分析

根據上面位置搜索的定義，位置搜索主要滿足以下兩種基本需求。

（1）基于位置的搜索需求

基于位置的搜索需求包括提供以位置屬性為條件的信息搜索、提供位置條件和其他條件（如POI名稱等）的組合搜索以及提供對移動實體的范圍搜索（如搜索周邊移動的人）需求。

（2）基于位置及好友關系的推薦需求

基于位置及好友關系的推薦需求主要包括以下幾點。

·信息整合需求。位置搜索需要整合多方具有共享價值的信息，要識別不同來源信息的關聯性，并把關聯信息整合成更加完整、更有共享價值的信息。

·位置搜索能利用位置數據，挖掘用戶的相關知識，并用于個性化信息的推薦。譬如，利用記錄的用戶出行軌跡，分析出用戶的居所和辦公場所以及經常光顧的商圈，并以此為依據向用戶推薦其可能感興趣的信息。

·用戶之間的關系，包括好友關系、關注關系、聯系人

關系，可以用于個性化信息推薦。譬如，用戶好友對信息的評價對用戶有更高的可信度，依據好友的評價進行信息的推薦可以提高推薦的精準度。

為實現以上需求，位置搜索必須具有以下特性。

（1）支持空間范圍查詢與全文搜索的有效結合

·在傳統對文本內容的全文搜索基礎上，位置搜索支持對信息的位置和空間有效范圍等LBS屬性的處理（如搜索包含關鍵字A，且有效范圍與目標區域B有交集的信息）。

·通過空間網格映射技術，支持把空間范圍的查詢轉換為文本查詢，實現與全文搜索的有效結合。

（2）支持移動物體的位置跟蹤和快速搜索

移動物體位置信息更換頻繁，對這些信息的跟蹤維護需要消耗大量的計算資源。位置搜索需支持快速散列算法，使得計算成本控制在O(1)范圍內。

（3）支持基于信息可信度的信息推薦

·基于用戶的位置軌跡以及好友關系估算推薦信息的可信度，并憑此推薦信息，幫助用戶獲取滿足自身個性化需求的資訊。

·在大數據量的情況下，有效地組合好友關系、地理位置、時間3個維度，為用戶提供實時的信息推薦。

3 位置搜索技術現狀

目前，一些成熟的商業數據庫都提供了空間數據庫引擎（包括位置搜索能力），如 Oracle和SQL Server。此外，一些非傳統的數據庫，如MongoDB，也提供空間索引，以實現空間搜索的能力。還有，原來主要提供全文索引和搜索的Lucene也在實現空間搜索模塊。這些產品，有些 （如Oracle Spatial）是提供完備的空間計算能力的，有些 （如Lucene Spatial）則僅僅提供某種空間索引以便實現針對點的位置搜索。下面對一些代表性產品的位置搜索技術進行分析。

·Oracle Spatial[3]是基于商業化的成熟的關系型數據庫的擴展，具有完備的空間計算能力，能更好地與關系數據庫結合使用，有配套成熟的管理和維護環境。但對全文索引的支持不如專門的全文搜索引擎，加上成本也高，少有用于支撐互聯網數據的搜索應用。

·Lucene[4]是開源的全文搜索引擎，空間擴展模塊（Lucene Spatial）在與全文搜索的結合上具有其他數據庫無法比擬的優勢。但目前Lucene Spatial并未成熟，有待優化和驗證。

·MongoDB[5]的核心競爭力是位置搜索，并且被全球最流行的LBS服務Foursquare采用。在對當前常見的LBS服務（如簽到、周邊商家的搜索）的支持方面有著內在的優勢。但MongoDB的局限性也很致命，其寫鎖為全局鎖，不適合位置變更頻繁的應用（如搜索周邊快速移動的人）。

4 位置搜索關鍵技術及實現

在面向個人的位置服務中，SoLoMo（social+local+mobile，即社交+本地化+移動）是公認的趨勢。SoLoMo對位置搜索有著比傳統應用更高的需求，譬如“搜索周邊用戶”，因為好友是會移動的個體，要搜索周邊的用戶，就必須實時記錄海量用戶的移動軌跡。假設有個SoLoMo應用，在廣州有100萬活躍用戶，平均每人上班路程為5 km，上班時間分布在7-9時的2 h內，用戶位置每移動100 m系統就更新其位置，則系統在上班高峰期需要支撐約7 000次/s的位置更新請求。可見實時記錄用戶的位置對系統性能有著非常高的需求。眾所周知，常用的樹結構索引并不適合頻繁更新的場景。要實現海量用戶的SoLoMo應用，還需要對現有的位置搜索技術進行改進。

4.1 技術框架

根據上述對位置搜索需求及特性的分析，提供位置搜索的能力引擎主要提供兩種能力：一種是位置信息搜索能力，另一種是位置信息推薦能力，這兩種能力均需要龐大的數據源做支撐。其中最重要的數據是POI數據，主要來源于POI引擎，其次是用戶數據，來源于包括公眾應用、政企/行業應用以及互聯網合作應用在內的各類應用系統。位置搜索技術實現框架如圖1所示。

從圖1中可以看出，位置搜索引擎從POI引擎和各類應用系統中獲取位置及用戶行為等數據，經加工處理后，向應用系統提供位置信息的搜索和推薦能力。另外，位置搜索引擎還包括了對用戶搜索行為的統計分析功能和用戶管理、監控服務等維護管理功能。下面對位置搜索引擎的主要功能進行闡述。

4.2 主要功能

從圖1中可以看出，位置搜索包括4大部分：搜索應用、統計分析、維護管理和數據存儲。

4.2.1 搜索應用

搜索應用包括POI采集、用戶行為采集等信息采集功能以及分析挖掘、位置索引創建、檢索、推薦等信息應用功能。

·采集。位置搜索引擎主要采集兩大類數據：POI數據和用戶數據。其中，POI數據包括POI基本數據、擴展數據和位置數據；用戶數據包括用戶基本信息、好友關系、狀態數據、行為數據等。采集的POI數據存儲在本地POI庫中，而用戶數據則存儲在用戶數據庫中。

·分析挖掘。引擎對收集到的用戶和POI數據進行分析挖掘，得出對信息采集和信息應用有價值的信息。引擎需要維護用戶、POI兩個視圖的信息。這些信息有些可以直接采集，有些需要根據其他信息推測或者根據實體行為挖掘。系統要具備挖掘這些信息的能力，并且及時更新這些信息。這些信息要能（自動或人為地）被應用到信息推薦和檢索結果排序上。

·位置索引創建。位置搜索引擎需創建3種位置索引：基礎POI、資訊和移動物體的位置索引。其中，基礎POI索引是支持位置的全文索引，資訊索引是支持位置和資訊范圍的全文索引，而移動物體的位置索引不支持全文索引，但支持地理位置信息的頻繁切換。

·檢索。應用系統對引擎POI數據和用戶數據的檢索支持范圍檢索、屬性過濾、全文檢索的組合快速檢索。

·推薦。引擎提供不同策略的推薦能力，以便主動向用戶推薦資源或者把推薦策略應用到用戶主動檢索的結果排序上。

4.2.2 統計分析

支持對用戶的查詢行為進行統計和分析，主要功能包括：高頻詞及組合統計、查無統計、關鍵字發現、關鍵字活躍度分析、用戶行為分析等。

4.2.3 維護管理

提供對位置搜索引擎的管理功能，以保證引擎的正常運行。主要功能包括：對用戶賬號的管理維護；對分詞、同義詞、敏感詞、關鍵詞等各類詞庫的統一管理和批量導入、導出；對系統各主機設備的監控和管理功能等。

4.2.4 數據存儲

提供位置搜索引擎各類數據的存儲功能。存儲的內容包括：本地POI數據，用戶數據，分析挖掘后得到的知識、索引以及系統數據等。

4.3 主要策略實現

同普通的全文搜索不同，位置搜索處理的信息均帶有明顯的位置特性，且需要根據用戶所處的位置等信息進行合理的信息推薦。因此，在以上功能模塊的基礎上，位置搜索還需滿足以下策略要求。

4.3.1 基于空間范圍的全文搜索策略

位置搜索需要在傳統對文本內容的全文搜索基礎上，加入對信息的位置和空間有效范圍等LBS屬性的處理?；诳臻g范圍的全文搜索策略如圖2所示。

基于空間范圍的全文搜索策略實現步驟如下。

（1）將空間范圍的匹配轉換為采用基于分詞的反向索引技術的全文搜索。基于分詞的反向索引實現全文搜索的技術已經比較成熟，如果能將空間范圍的匹配轉換為采用基于分詞的反向索引技術的全文搜索，則基于空間范圍的全文搜索策略即可輕松實現。

·將地理位置映射到網格，每個網格用其左上角經緯度值作為唯一的標識，如21.324562-113.234321。

·將被資訊范圍覆蓋的網格標識連起來作為資訊的范圍字段，且每個標識作為一個獨立的分詞，如 A/B/C/F/G/H/K/L/M，建立反向索引。

·將被搜索范圍覆蓋的網格標識通過邏輯“或”的關系組合起來作為查詢串，如C/D/E/H/I/J/M/N/O。

·執行普通的全文搜索，只要資訊的范圍字段和查詢串的分詞有交集，就會被選中。引擎還要對選中的結果進行空間距離計算，最終篩選出滿足條件的結果。

（2）將對空間范圍字段的搜索和對資訊內容的全文搜索進行邏輯“與”的組合，即可得到基于空間范圍的全文搜索結果。

4.3.2 移動實體的快速匹配策略

移動實體的快速匹配策略示意如圖3所示。在LBS應用中，移動物體位置信息更換頻繁，對這些信息的跟蹤維護需要消耗大量的計算資源，位置搜索必須采取有效的處理措施。在處理的過程中，要考慮到移動物體的位置變更次數遠多于被搜索的次數，所以變更的運算成本要控制到最低。

此策略的實現原理是通過網格映射實現位置散列算法，步驟如下。

（1）將地理位置映射到網格，每個網格用其左上角經緯度值作為唯一的標識，如21.324562-113.234321。

（2）每次更新，根據用戶的位置計算其所在網格，用該網格標識作為鍵值，為用戶信息建立散列索引。

（3）計算搜索范圍所覆蓋的網格，根據這些網格的標識從散列索引中獲取符合條件的全部用戶信息作為候選結果。

（4）對候選結果再做精確的過濾計算。精確過濾的時候可以基于對各條件篩選率的統計，先執行選中率低的計算，從而進一步減少運算量，比如先做年齡比較，再做性別比較。

5 結束語

隨著LBS業務的快速發展，位置搜索技術也正迎來快速成長期，而效率和準確性將是衡量位置搜索技術優劣的核心指標，所以LBS技術和服務提供商應主要從性能提升方面進行位置搜索技術的研究。在保證搜索性能的前提下，結合用戶當前屬性和行為數據，就能真正做到個性化的信息推薦。

1 Seiji Yokoji,Katsumi Takahashi,Nobuyuki Miura.Kokono search:a location based search engine.http://www10.org/cdrom/posters/1146.pdf

2 Chengyi Liu,Pei-Luen Patrick Rau,Fei Gao.Mobile information search for location-based information.Computers in Industry,2010,61(4):364～371

3 何原榮,李全杰,傅文杰.Oracle Spatial空間數據庫開發應用指南.北京：測繪出版社,2008

4 Grant Ingersoll.使用 Apache Lucene和Solr進行位置感知搜索.https://www.ibm.com/developerworks/cn/java/j-spatial/,2010

5 圖解 MongoDB地理位置索引的實現原理.http://blog.nosqlfan.com/html/1811.html