移动云计算环境下的基于双色反近邻查询的商店定址系统

摘要

一种移动云计算环境下的基于双色反近邻查询的商店定址系统,属于基于大规模时空数据处理与移动技术应用领域。用于解决现有商店定址系统对用户与顾客、商店之间的空间位置不明确的问题，技术要点是：该系统智能终端包括智能移动客户端、云中心服务系统等，采用了大规模分布式BRNN等基于位置的服务的分析算法，通过各个查询顾客集位置与商店集位置，将大数据处理的模式整合到该商店定址系统的查询阶段，在海量数据中搜索出最符合商店定址条件的位置区域，并将该位置区域反馈至智能移动客户端，最终完成商店定址问题。效果是：通过查询现有顾客集的位置以及现有商店集的位置，据此为用户找到最佳商店定址位置区域，使得新建的商店能够吸引最多的顾客。

说明书

技术领域

本发明属于基于位置的服务的移动通讯领域，是一种移动云计算环境下的 基于双色反近邻查询的商店定址系统，涉及到大规模时空数据分析、云计算环 境下的分布式海量数据处理，尤其涉及到智能移动数据处理与移动应用开发。

背景技术

互联网改变了人们的生活方式，同时，随着3G技术的不断升级，移动定位 技术和地理信息系统(GeographicInformationSystem，GIS)的推广，以及内置 有GPS模块的智能手机，平板电脑的普及，移动互联网渐渐融入了人们的生活 中，人们可以随时随地通过手持设备终端中各种各样的基于位置的服务 (LocationBasedService，LBS)的应用程序使活动打破时空障碍，如移动定位 功能，移动网络社交等，它对人们的日常生活影响越来越重要，越来越满足服 务多元化需求。而随着中国城镇化的不断进行，建立或大或小的商店从而满足 人们的需求已经迫在眉睫。然而当前城市中的很多商店存在着这样一个问题： 不能吸引到尽可能多的客户。这个问题一方面使得商店老板不能获得更多的利 益，另一方面也使得客户购买物品更加麻烦。现有技术中，大多依托于笨重的 车载终端设备，这样就提高了定址的成本，并且不利于大规模的扩展与后期的 更新换代。即使现有的商店定址软件，也很难解决当前商店定址困难的问题。

结合近年来随着基于位置的服务和移动互联网的快速发展，地理空间数据 的数据量的迅猛增长。这些迅速增加的空间数据给传统的空间数据索引机制带 来了新的问题，而这些传统的索引方法往往是基于内存或者需要优化的磁盘访 问的先决条件。因此，如何实现高效的空间索引和查询处理大规模空间数据成 为商店定址软件新的需求和挑战。一种可扩展的、分布式的空间数据索引技术 不失为进行高效空间数据的查询和分析的最佳选择。现在已经有几种将空间分 布式索引和查询处理技术与MapReduce相结合的方法，例如R-树和基于泰森多 边形的空间索引。然而，R-树不适合进行平行化，基于泰森多边形索引的查询 需要额外的查询点定位和局部索引重建计算。这使得定址软件在定位与查询上 还存在一些技术问题。

因为云计算本身具有的虚拟化和并行化的特性，能高效的处理海量数据， 它与移动设备的便携性以及互联网结合起来，形成了移动云计算。移动云计算 集成了移动计算以及移动互联网和云计算的优点，这几年逐渐发展成为云计算 的一个重要分支。任何智能终端设备如智能手机和平板电脑都可以从无线网络 环境中随时按需获取服务，并且不受限于有限的硬件资源、计算能力和带宽等。 很显然，在移动云计算中，高效分析和处理海量时空数据，并且与商店定址应 用相结合，就是一个新兴的实用技术，移动云计算环境下有效的空间数据库索 引技术对提高空间数据库查找效率与应用用户体验至关重要，基于该出发点， 我们设计并实现了该发明。

发明内容

根据上述背景技术中存在的缺陷和不足，本发明提供了一种移动云计算环 境下的基于双色反近邻查询的商店定址系统，以解决现有商店定址系统对用户 与顾客、商店之间的空间位置不明确的问题。本发明也针对现有技术中存在的 在空间数据索引和查询方法中的不足进行了改进，用以提高定位与搜索查询的 速度、准确度和精确度。

为了实现上述目的，本发明所采用的技术方案是：一种移动云计算环境下 的基于双色反近邻查询的商店定址系统，包括云中心服务系统和智能移动客户 端系统，其中，云中心服务系统用于进行倒排网格索引的建立，以及执行分布 式空间双色反近邻查询算法，智能移动客户端用于收集与预处理定址用户位置、 该定址用户位置附近的商店以及顾客的位置信息，并通过无线网络将该信息发 送给云中心服务系统，且智能移动客户端还用于接收云中心服务系统返回的最 优位置区域。

作为技术方案的补充，该商店定址系统的执行方法是：当定址用户发出定 址请求后，由智能移动客户端的定位系统自动采集并提交定址用户位置附近的 商店和顾客的位置信息至云中心服务系统，云中心服务系统通过使用采集到的 定址用户位置附近的商店以及顾客的位置信息，建立商店位置信息的分布式倒 排网格索引，并对商店位置以及其附近顾客的位置进行分布式预处理，且按照 需要进行定期动态更新；

由云中心服务系统使用倒排网格索引进行分布式时空信息的双色反最近邻 查询，并返回最优位置给定址用户。

作为技术方案的进一步补充，倒排网格索引的处理步骤具体为：给定空间 数据集D，D是由欧几里德空间数据点组成的集合，且数据集D具有定址用户位 置附近的商店以及顾客的位置信息，对于D中的点p∈D在数据集D的位置用表达 式(p.x,p.y)表示，点p包含定址用户位置附近的商店以及顾客的位置信息；

首先将数据集文件存储到分布式文件系统HDFS上，HDFS会自动将其分割 成很多数据分块，每个Mapper读入一个输入数据分片，然后每个Mapper分析 数据分片中的空间数据点，并计算出空间数据点到网格单元格的映射，最后 Mapper把单元格c(i,j)在网格当中的位置作为key，把点p(x,y)的位置信息作为 value，并将该<key,vlaue>对应输出，Reducer则把Mapper读取的数据输出，并 收集相同单元格(key)中的点数据，然后输出单元格索引和包含在该单元格中 的点的集合。

作为技术方案的补充，双色反最近邻查询算法的定义为：给定欧氏距离空 间数据集P和O，其中P和O是不同类型的数据集，如果给定数据集P中的一 点p，双色反最近邻查询结果是返回所有点o∈O，其中o是p∈P的最近邻，即 不存在任意一点p’∈P满足dist(o,p')＜dist(o,p)。

作为技术方案的更进一步的补充，基于网格索引的双色反最近邻查询的方 法为：首先建立空间网格索引，并对网格空间进行整体扫描，从而建立了倒排 网格索引，在Map函数中对分片数据区域用PCT轮圈算法，以点c_i为圆心，半 径r＝|c_i,s_i|进行轮圈，并将圆区域内或与圆边界相交的网格Cell(i)的Counter(g_i) 值计为1，即Counter(g_i)＝1；

每个分片数据区域单独处理完后，最后在Reduce函数中合并，合并的过程 中，按照网格处理算法进行扫描，每次扫描的过程中，对重叠的网格Cell(i)的 Counter(g_i)值累加，最后输出整个空间区域权值W最大的Cell(j)。

有益效果：当用户发出定址请求时，数据中心会通过双色反最近邻查询算 法等基于位置服务的分析算法，搜索出适合用户进行商店定址的最优位置区域， 且本发明可以提高定位与搜索查询的速度、准确度和精确度。

附图说明

图1本发明的倒排网格索引的建立过程的示意图；

图2本发明的PCT查询算法过程的示意图；

图3本发明的Map过程的示意图；

图4本发明的Reduce过程的示意图；

图5本发明的基于倒排网格索引的双色反近邻查询的过程的示意图；

图6本发明的大规模商店定址系统架构的示意图；

图7本发明的功能模块图；

图8本发明商店定址流程图；

图9双色反最近邻查询算法的实际应用举例的示意图；

图10PCT轮圈算法的示意图。

具体实施方式

实施例1：一种移动云计算环境下的基于双色反近邻查询的商店定址系统， 包括云中心服务系统和智能移动客户端系统，其中，云中心服务系统用于进行 倒排网格索引(InvertedGridIndex，IGI)的建立，以及执行分布式空间双色反 近邻查询(BichromaticReverseNearestNeighbor，BRNN)算法，智能移动客户 端根据需要发出定址请求，用于收集定址用户位置、该定址用户位置附近的商 店以及顾客的位置信息，并通过无线网络将该信息发送给云中心服务系统，且 智能移动客户端还用于接收云中心服务系统返回的最优位置区域。

实施例2：具有与实施例1相同的技术方案，其中：该商店定址系统的执行 方法是：当定址用户发出定址相关请求后，由智能移动客户端的定位系统自动 采集并提交定址用户位置附近的商店和顾客的位置信息(经纬度坐标等表示地 理位置的信息)至云中心服务系统，云中心服务系统通过使用采集到的定址用 户位置附近的商店以及顾客的位置信息，建立商店位置信息的分布式倒排网格 索引，并对商店位置以及其附近顾客的位置进行分布式预处理，且按照需要进 行定期动态更新；由云中心服务系统使用倒排网格索引进行分布式时空信息的 双色反最近邻查询，并返回最优位置区域给定址用户。

实施例3：具有与实施例2相同的技术方案，其中：倒排网格索引的处理步 骤具体为：给定空间数据集D，D是由欧几里德空间数据点组成的集合，且数据 集D具有定址用户位置附近的商店以及顾客的位置信息，对于D中的点p∈D在数 据集D的位置用表达式(p.x,p.y)表示，点p包含定址用户位置附近的商店以及顾客 的位置信息；

首先将数据集文件存储到分布式文件系统HDFS上，HDFS会自动将其分割 成很多数据分块，每个Mapper读入一个输入数据分片(该分片就是数据集D的 一个子集)，然后每个Mapper分析数据分片中的空间数据点，并计算出空间数 据点到网格单元格的映射，例如空间点的位置信息p(x,y)将被映射到单元格 中，最后Mapper把单元格c(i,j)在网格当中的位置作为key， 把点p(x,y)的位置信息作为value，并将该<key,vlaue>对应输出，Reducer则把 Mapper读取的数据(商店和顾客的位置信息)输出，并收集相同单元格(key) 中的点数据，然后输出单元格索引和包含在该单元格中的点的集合。

实施例4：具有与实施例1或2或3相同的技术方案，其中：双色反最近邻 查询算法的定义为：给定欧氏距离空间数据集P和O，其中P和O是不同类型 的数据集，如果给定数据集P中的一点p，双色反最近邻查询结果是返回所有点 o∈O，其中o是p∈P的最近邻，即不存在任意一点p’∈P满足dist(o,p')＜dist(o,p)。

实施例5：具有与实施例1或2或3或4相同的技术方案，其中：基于网格 索引的双色反最近邻查询的方法为：首先建立空间网格，并对网格空间进行整 体扫描，建立倒排网格索引，在Map函数中对分片数据区域用PCT轮圈算法(已 将顾客和商店的位置信息等数据采集到云服务中心)以点c_i(某一顾客的位置信 息)为圆心，半径r＝|c_i,s_i|(s_i为某一商店的位置信息)进行轮圈，并将圆区域 内或与圆边界相交的网格Cell(i)的Counter(g_i)值计为1，即Counter(g_i)＝1；

每个分片数据区域单独处理完后，最后在Reduce函数中合并，合并的过程 中，按照网格处理算法进行扫描，每次扫描的过程中，用类似于WordCount算 法对重叠的网格Cell(i)的Counter(g_i)值累加，最后输出整个空间区域权值W最 大的Cell(j)。

本实施例采用了大规模分布式BRNN等基于位置的服务的分析算法，通过 各个查询顾客集位置与商店集位置，将大数据处理的模式整合到该商店定址系 统的查询阶段，在海量数据中搜索出最符合商店定址条件的位置区域，并将该 位置信息反馈至用户端，最终完成商店定址问题。效果是：通过查询现有顾客 集的位置以及现有商店集的位置，据此为用户提供新的商店定址区域，使得新 建的商店能够吸引最多的顾客。

本实施例中所述的商店定址系统具有下述结构和好处：

(1)采用单个终端的设计方式。用户端为安装在安卓智能手机上的软件， 供用户进行商店定址时使用。

用户通过手机内置的定位系统和手机运营商的基站，依托于2G/3G网络， wifi等获取自身的实时空间地理位置。获取位置信息后，我们可以离线建立倒排 网格索引，建立倒排网格索引的Map与Reduce过程。

(2)云计算是一种基于互联网的计算方式,通过这种方式，共享的软硬件资 源和信息可以按需提供给计算机和其他设备。我们发明中设计的大规模商店定 址系统所使用的云端服务器是由多个云数据中心的网络服务器或虚拟主机所构 成的，采用云计算这种并行化计算来处理大规模数据来应对线上或线下的商店 定址用户需求，在这种模式下，保证了高访问时的定址稳定性，也加快了用户 搜索时的反应速度，同时增强了可扩展性。

实施例6：本实施例给出了PCT轮圈算法的基本思路：

参考图2以及图10，PCT算法的基本思想是以查询点q为中心，一轮轮并 行地读取周围的单元格。图2算法的第2-14行为一路处理过程，每一路处理过 程包括一定数量并行的轮圈组操作(为了与轮一圈区分，把多个轮圈并行操作 称为一批轮圈组操作)，并行的数量由计算节点的多核或多线程机制来决定。因 为每一个计算节点包括一些独立的多核CPU，所以用u_c来代表每个计算节点可 以最多执行的线程数，例如一个支持四核双线程的CPU，则u_c的值为8。这里 为了简单起见，假定每个线程间是独立的，不考虑线程安全问题。

为了让多核CPU线程能够尽量充分得到激活，在算法的第3行中，首先初 始化u_c+1个CircleTrip并行运行线程(主要是因为在实验中使用的Hadoop运行 环境本身是基于java虚拟机的，但据我们所知，java6并不直接支持CPU线程 数量的自定义，所以我们通过额外加一个线程的方式来替代默认运行方式，在 实际的测试实验中，也证明了这个机制是有效的)。

在每一批轮圈组的每一个线程操作中，调用CircleTrip方法来画半径为 r_i＝r₀+i*δ，并收集相交的单元格中的点，每个轮圈C_i包含所有与以q为圆心及 以r_i＝r₀+i*δ半径的圆相交的单元格，即r₀是第一轮圈的半径，显然r₀的值最大可取maxdist(c_q,q)，否则单元格c_q将不会被 访问到。在每一轮遍历时，算法顺序地访问按mindist(c,q)升序排列的单元格，直 到mindist(c,q)≥q.dist_k时停止访问。其中CircularTrip是一种网格访问方法，该方法 返回一次轮圈所遍历的所有网格单元格。

本实施例还给出了BRNN查询算法的定义：

给定欧氏距离空间数据集P和O，其中P和O是不同类型的数据集，如果给定 数据集P中的一点p，双色反最近邻查询结果是返回所有点o∈O，其中o是p∈P 的最近邻，即不存在任意一点p’∈P满足dist(o,p')＜dist(o,p)，这些o点构成了p 的BRNN查询结果集合，用BRNN(p,p，)来表示。

基于网格索引的BRNN查询算法的基本思想如下：

首先建立空间网格索引，并对网格空间进行整体扫描，从而建立了倒排网 格索引，在Map函数中对分片数据区域用PCT轮圈算法(已将顾客和商店的位 置信息等数据采集到云服务中心)，以点c_i(某一顾客的位置信息)为圆心，半 径r＝|c_i,s_i|(s_i为某一商店的位置信息)进行轮圈，并对圆区域内或与圆边界相 交的网格Cell(i)的Counter(g_i)值计为1，即Counter(g_i)＝1。如图3.

每个数据分片区域单独处理完后，最后在Reduce函数中合并，合并的过程 中，按照网格处理算法进行扫描，每次扫描的过程中，对重叠的网格Cell(i)的 Counter(g_i)值累加，最后输出整个空间区域权值W最大的Cell(j)。如图4所示， 为两个NLC重叠的执行过程与结果，其中深色的阴影部分为两个NLC合并后 的输出结果。程序参见图5，需要说明的是，每个网格包含网格在网格空间的位 置信息以及顾客或商店的实际的位置信息。

实施例7：本实施例更进一步对实施例1～6进行阐述和说明，参见图1， 建立倒排网格索引的过程为，将预处理过程划分好的数据集(该数据集包含顾 客和商店的位置信息)上传到分布式文件系统上。首先每个Mapper任务读入数 据集P一个划分的子数据集作为输入，然后计算输入数据集中每个数据对象(即 每个顾客位置信息和每个商店位置信息)映射到网格空间中的网格编号，如对 象p(p.d₁,p.d₂,…,p.d_n,)(某一商店或顾客的位置信息)将被映射到C[p.d₁/δ, p.d₂/δ,…,p.d_n/δ]网格(某网格在网格空间中的位置)中。Map函数输出网格编号 和数据对象组成的键值对(包含网格位置以及某一商店或顾客的位置信息)，即 〈C[p.d₁/δ,p.d₂/δ,…,p.d_n/δ],p〉。Mapper的输出作为Reducer的输入，然后在 Reducer里将相同网格单元内的所有的数据对象聚合在一起。最后Reducer的输 出为网格编号及该网格内所包含的数据对象列表。Map和Reduce函数的输入和 输出都是键值对的形式。

分布式倒排网格索引的创建过程充分利用了MapReduce框架分散和聚合的 思想，分别对多个子数据集(前文已述)并行创建部分索引，最后将多个子索 引聚合为一个完整的索引。图1是分布式倒排网格索引在MapReduce模型下实 现的伪代码。从图中可以看出，Map函数中首先将输入的数据集中的每一行解 析为一个key/value对，然后计算每行中的数据对象点所映射的网格编号，Map 输出由网格编号和数据对象构成的键值对。网格编号相同的数据对象被传送到 同一个Reduce函数中，Reduce函数将这些对象聚集构成一个链表，同时按照一 定的规则对链表中的数据对象进行排序，最后输出由网格编号和链表构成的键 值对。

参见图1，首先建立空间网格索引，我们设定网格单元大小均为δ×δ，并对 网格空间进行整体扫描，建立倒排网格索引(已将顾客和商店的位置信息等数 据采集到云服务中心)，在Map函数中对分片数据区域用PCT轮圈算法，以点 c_i(某一个顾客的位置信息)为圆心，半径r＝|c_i,s_i|(s_i为某一商店的位置信息) 进行轮圈，并对圆区域内或与圆边界相交的网格Cell(i)的Counter(g_i)值计为1， 即Counter(g_i)＝1，每个数据分片区域单独处理完后，最后在Reduce函数中合并， 合并的过程中，按照网格处理算法进行扫描，每次扫描的过程中，对重叠的网 格Cell(i)的Counter(g_i)值累加，最后输出整个空间区域权值W最大的Cell(j)， 即为最优位置区域。同时我们利用了多核机制进行了并行化优化，以提高运行 速度。

参见图6，本发明考虑到移动终端便于携带的特性和它软硬件资源限制以及 云计算的优点，本大规模商店定址系统采用C/S架构的瘦用户端模式，云中心 服务器负责主要的数据(商店和顾客的位置信息)处理工作，移动智能客户端 只需要简单地发送定址请求，接收并显示结果。手持移动智能客户端通过基于 3G方式或是WIFI的无线网络，接入移动互联网与云中心服务系统建立联系。 移动智能客户端负责显示地图，并携带相关参数，如商店位置信息、客户位置 信息向云中心服务系统发送请求。空间地理信息(包括商店的位置信息以及顾 客信息)在此之前已经发送到云端服务器，空间地理信息在云端服务器采用我 们设计的空间海量数据分布式空间倒排索引技术，即倒排网格索引技术对顾客 和商店的位置信息建立分布式空间索引。用户需要定址的时候，云端服务器通 过采集到数据(商店和顾客的位置信息)，采用本文的并行化BRNN查询技术， 快速地从海量的商店及客户位置信息中查询到距离用户所需要的最优位置区 域。查询到的最优位置区域出现在用户端软件地图界面上，用户可根据自己的 要求进行商店定址。

参见图7，本发明是利用智能移动平台来进行商店定址的系统，其中包括一 组云中心服务系统和智能移动客户端，具体是安装在智能移动平台(如智能手 机或平板电脑)上的软件，给用户使用。智能移动客户端包括地图、定位等基 本功能。云中心服务系统负责整个定址流程的控制和相关数据(商店和顾客的 位置信息)处理(包括倒排网格索引的建立与分布式BRNN查询等)。

参见图8，通过本发明来实现定址所包括的步骤如下：商店定址用户登录到 智能移动客户端软件后，自动定位到当前的位置，使用人形图标标注。在定址 之前首先将其附近顾客位置、商店位置等信息采集到云中心服务系统，之后即 可开始搜索最优位置区域，云中心服务系统收到这次请求后根据定址用户的位 置使用空间索引算法对包含顾客位置、商店位置的数据进行处理，找出定址用 户附近的最优位置区域，并将最优位置区域返回给用户。

实施例8：:本实施例举例说明双色反最近邻查询算法与商店定址的对应关 系：

给定商店位置信息集合S和顾客位置信息集合C，我们假设数据集中有两个 商店S₁、S₂及五个顾客C₁、C₂、C₃、C₄和C₅的坐标位置(如经纬度等)，如图 9所示，我们知道，日常生活中，顾客总是会去距离其最近的商店购买商品，那 么顾客C₁、C₂、C₃总是会去商店S₁，顾客C₄和C₅总是去商店S₂，对于双色反 最近邻(BRNN)查询算法，有BRNN(S₁,S)＝{C₁,C₂,C₃}和BRNN(S₂,S)＝{C₄,C₅}， 那么如果我们想要找到一个最优位置区域，使得一个新的便利店S₃被安置在此 区域时能够吸引尽可能多的顾客，那么怎样才能找到满足这个条件的最优位置 区域呢？这就是一个简单的BRNN查询问题。

而我们采用的分布式双色反最近邻算法是基于倒排网格索引的，首先建立 空间网格，我们设定网格单元大小均为δ×δ，并对网格空间进行整体扫描，建立 倒排网格索引(已将顾客和商店的位置信息等数据采集到云服务中心)，在Map 函数中对分片数据区域用PCT轮圈算法，以点c_i(某一个顾客的位置信息)为 圆心，半径r＝|c_i,s_i|(s_i为某一商店的位置信息)进行轮圈，并对圆区域内或与 圆边界相交的网格Cell(i)的Counter(g_i)值计为1，即Counter(g_i)＝1，每个数据分 片区域单独处理完后，最后在Reduce函数中合并，合并的过程中，按照网格处 理算法进行扫描，每次扫描的过程中，用类似于WordCount算法对重叠的网格 Cell(i)的Counter(g_i)值累加，最后输出整个空间区域权值W最大的Cell(j)，即为 最优位置。同时我们利用了多核机制进行了并行化优化，以提高运行速度。

在定址阶段，该商店定址系统会通过基于位置的服务相关技术在移动端获 取到商店和附近客户的位置信息上传并保存到云中心服务系统，然后传送到云 中心服务系统进行处理，得到最佳的商店定址位置区域并反馈给用户。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局 限于此，任何熟悉本技术领域的技术人员在本发明披露的技术范围内，根据本 发明的技术方案及其发明构思加以等同替换或改变，都应涵盖在本发明的保护 范围之内。