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

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

1 引言

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

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

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

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

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

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

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

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

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

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

·用戶之間的關系，包括好友關系、關注關系、聯(lián)系人

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

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

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

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

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

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

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

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

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

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

3 位置搜索技術現(xiàn)狀

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

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

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

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

4 位置搜索關鍵技術及實現(xiàn)

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

4.1 技術框架

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

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

4.2 主要功能

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

4.2.1 搜索應用

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

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

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

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

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

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

4.2.2 統(tǒng)計分析

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

4.2.3 維護管理

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

4.2.4 數(shù)據(jù)存儲

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

4.3 主要策略實現(xiàn)

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

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

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

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

（1）將空間范圍的匹配轉(zhuǎn)換為采用基于分詞的反向索引技術的全文搜索?；诜衷~的反向索引實現(xiàn)全文搜索的技術已經(jīng)比較成熟，如果能將空間范圍的匹配轉(zhuǎn)換為采用基于分詞的反向索引技術的全文搜索，則基于空間范圍的全文搜索策略即可輕松實現(xiàn)。

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

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

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

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

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

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

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

此策略的實現(xiàn)原理是通過網(wǎng)格映射實現(xiàn)位置散列算法，步驟如下。

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

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

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

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

5 結束語

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

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空間數(shù)據(jù)庫開發(fā)應用指南.北京：測繪出版社,2008

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

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