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

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

1 引言

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

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

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

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

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

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

（2）基于位置及好友關(guān)系的推薦需求

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 位置搜索技術(shù)現(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)品的位置搜索技術(shù)進行分析。

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

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

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

4 位置搜索關(guān)鍵技術(shù)及實現(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)性能有著非常高的需求。眾所周知，常用的樹結(jié)構(gòu)索引并不適合頻繁更新的場景。要實現(xiàn)海量用戶的SoLoMo應用，還需要對現(xiàn)有的位置搜索技術(shù)進行改進。

4.1 技術(shù)框架

根據(jù)上述對位置搜索需求及特性的分析，提供位置搜索的能力引擎主要提供兩種能力：一種是位置信息搜索能力，另一種是位置信息推薦能力，這兩種能力均需要龐大的數(shù)據(jù)源做支撐。其中最重要的數(shù)據(jù)是POI數(shù)據(jù)，主要來源于POI引擎，其次是用戶數(shù)據(jù)，來源于包括公眾應用、政企/行業(yè)應用以及互聯(lián)網(wǎng)合作應用在內(nèi)的各類應用系統(tǒng)。位置搜索技術(shù)實現(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ù)包括用戶基本信息、好友關(guān)系、狀態(tài)數(shù)據(jù)、行為數(shù)據(jù)等。采集的POI數(shù)據(jù)存儲在本地POI庫中，而用戶數(shù)據(jù)則存儲在用戶數(shù)據(jù)庫中。

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

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

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

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

4.2.2 統(tǒng)計分析

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

4.2.3 維護管理

提供對位置搜索引擎的管理功能，以保證引擎的正常運行。主要功能包括：對用戶賬號的管理維護；對分詞、同義詞、敏感詞、關(guān)鍵詞等各類詞庫的統(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ù)用戶所處的位置等信息進行合理的信息推薦。因此，在以上功能模塊的基礎(chǔ)上，位置搜索還需滿足以下策略要求。

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

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

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

（1）將空間范圍的匹配轉(zhuǎn)換為采用基于分詞的反向索引技術(shù)的全文搜索?；诜衷~的反向索引實現(xiàn)全文搜索的技術(shù)已經(jīng)比較成熟，如果能將空間范圍的匹配轉(zhuǎn)換為采用基于分詞的反向索引技術(shù)的全文搜索，則基于空間范圍的全文搜索策略即可輕松實現(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)格標識通過邏輯“或”的關(guān)系組合起來作為查詢串，如C/D/E/H/I/J/M/N/O。

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

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

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)格的標識從散列索引中獲取符合條件的全部用戶信息作為候選結(jié)果。

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

5 結(jié)束語

隨著LBS業(yè)務的快速發(fā)展，位置搜索技術(shù)也正迎來快速成長期，而效率和準確性將是衡量位置搜索技術(shù)優(yōu)劣的核心指標，所以LBS技術(shù)和服務提供商應主要從性能提升方面進行位置搜索技術(shù)的研究。在保證搜索性能的前提下，結(jié)合用戶當前屬性和行為數(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