位置搜索关键技术研究

杨德利，袁立宇，张 涛，徐 雄

（中国电信股份有限公司广东研究院 广州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属性的处理。基于空间范围的全文搜索策略如图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