地理位置的搜索方法、装置、电子设备及存储介质

摘要

本发明实施例涉及自动程序设计技术领域，公开了一种地理位置的搜索方法、装置、电子设备及存储介质。其中，该方法包括：接收目标客户端所发送目标页面的数据查询请求，获取与所述数据查询请求对应的查询数据点的查询经纬度；基于所述查询经纬度在预先构建的K维树中进行K近邻搜索，得到与所述查询数据点对应的至少一个目标数据点，其中，所述K维树基于每个样本数据点的数据经纬度构建；将至少一个所述目标数据点对应的目标地理位置显示于所述目标客户端的目标页面上。本发明实施例的技术方案，通过在预先构建的K维树中进行K近邻搜索，不仅不受限于距离范围，而且能够减少查询量，提升查询速度，更快地响应客户端请求，提升用户体验。

说明书

技术领域

本发明实施例涉及自动程序设计技术领域，尤其涉及一种地理位置的搜索方法、装置、电子设备及存储介质。

背景技术

目前，银行在全国范围内有大量的网点、员工、设备、客户等，业务上需要根据指定地点的经纬度，去查询全国范围内的特定对象，并按照从近到远的方式排序，在客户端可视化展示，为资源调度和决策提供数据支撑。

现有技术基于把地图划分成基本相同大小的一个个的小区块，然后计算每个数据点所归属的区块。在查询时，先找出查询数据点所在区块的所有数据点，然后再逐层的查询外层区块。这种方法，如果碰上数据点相对稀疏，涉及成百上千公里的大范围的搜索时，效率低下，反应速度慢，难以胜任实时查询需求；如果碰上数据点非常稠密，区块内包含的数据点非常多，大大超过显示页面的单页显示容量时，又存在大量冗余计算的问题。

发明内容

本发明实施例提供了一种地理位置的搜索方法、装置、电子设备及存储介质，以实现地理位置地快速查询。

第一方面，本发明实施例提供了一种地理位置的搜索方法，该方法包括：

接收目标客户端所发送目标页面的数据查询请求，获取与所述数据查询请求对应的查询数据点的查询经纬度；

基于所述查询经纬度在预先构建的K维树中进行K近邻搜索，得到与所述查询数据点对应的至少一个目标数据点，其中，所述K维树基于每个样本数据点的数据经纬度构建；

将至少一个所述目标数据点对应的目标地理位置显示于所述目标客户端的目标页面上。

第二方面，本发明实施例还提供了地理位置的搜索装置，该装置包括：

查询请求模块，用于接收目标客户端所发送目标页面的数据查询请求，获取与所述数据查询请求对应的查询数据点的查询经纬度；

数据搜索模块，用于基于所述查询经纬度在预先构建的K维树中进行K近邻搜索，得到与所述查询数据点对应的至少一个目标数据点，其中，所述K维树基于每个样本数据点的数据经纬度构建；

数据显示模块，用于将至少一个所述目标数据点对应的目标地理位置显示于所述目标客户端的目标页面上。

第三方面，本发明实施例还提供了一种电子设备，该电子设备包括：

一个或多个处理器；

存储装置，用于存储一个或多个程序，

当所述一个或多个程序被所述一个或多个处理器执行，使得所述一个或多个处理器实现如本发明实施例中任一技术方案所述的地理位置的搜索方法。

第四方面，本发明实施例还提供了一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现如本发明实施例中任一技术方案所述的地理位置的搜索方法。

本发明实施例的技术方案，通过在预先构建的K维树中进行K近邻搜索，解决了现有的搜索方式搜索速度低以及容易产生冗余计算的技术问题，不仅不受限于距离范围，而且能够减少查询量，提升查询速度，更快地响应目标客户端的数据查询请求，从而提升用户体验。

附图说明

为了更加清楚地说明本发明示例性实施例的技术方案，下面对描述实施例中所需要用到的附图做一简单介绍。显然，所介绍的附图只是本发明所要描述的一部分实施例的附图，而不是全部的附图，对于本领域普通技术人员，在不付出创造性劳动的前提下，还可以根据这些附图得到其他的附图。

图1是本发明实施例一所提供的一种地理位置的搜索方法的流程示意图；

图2是本发明实施例二提供的一种地理位置的搜索方法的流程示意图；

图3是本发明实施例三提供的一种地理位置的搜索装置的结构示意图

图4是本发明实施例四提供的一种电子设备的结构示意图。

具体实施方式

下面结合附图和实施例对本发明作进一步的详细说明。可以理解的是，此处所描述的具体实施例仅仅用于解释本发明，而非对本发明的限定。另外还需要说明的是，为了便于描述，附图中仅示出了与本发明相关的部分而非全部结构。

另外还需要说明的是，为了便于描述，附图中仅示出了与本发明相关的部分而非全部内容。在更加详细地讨论示例性实施例之前应当提到的是，一些示例性实施例被描述成作为流程图描绘的处理或方法。虽然流程图将各项操作(或步骤)描述成顺序的处理，但是其中的许多操作可以被并行地、并发地或者同时实施。此外，各项操作的顺序可以被重新安排。当其操作完成时所述处理可以被终止，但是还可以具有未包括在附图中的附加步骤。所述处理可以对应于方法、函数、规程、子例程、子程序等等。

实施例一

图1为本发明实施例一所提供的一种地理位置的搜索方法的流程示意图，本实施例可适用于对地理位置进行搜索的情况，该方法可以由地理位置的搜索装置来执行，该装置可以通过软件和/或硬件的方式来实现。

如图1所示，本实施例的方法具体可包括如下步骤：

S110、接收目标客户端所发送目标页面的数据查询请求，获取与所述数据查询请求对应的查询数据点的查询经纬度。

其中，查询数据点要计算其最近邻的位置点。在本发明实施例中，查询数据点可以理解为请求查询的地理位置。查询数据点的地理位置可以用查询经纬度来表示。数据查询请求可以理解为查询目标客户端所发送目标页面的页面索要现实的地理位置数据的请求。数据查询请求可以理解为在接收到用于请求数据查询的触发操作所生成的请求指令。

需要说明的是，触发操作的作用区域以及在作用区域的作用方式可以根据实际需求进行设置，在此不做具体限定。可选地，该触发操作的作用方式为通过输入设备所输入的触发操作，或者，通过声音以及手势等人机交互方式输入的操作。触发操作的作用方式的作用区域可以是预先设定的触发元件，或者，预先设定的触发操作识别区域等。例如是，触发操作可以是某列表视图被滚动触发时的操作、某按钮被点击触发时的操作、触发某页面被显示时的操作等等。

S120、基于所述查询经纬度在预先构建的K维树中进行K近邻搜索，得到与所述查询数据点对应的至少一个目标数据点，其中，所述K维树基于每个样本数据点的数据经纬度构建。

其中，K维树是一种对k维空间中的样本数据点进行存储以便对其进行快速检索的树形数据结构。k近邻搜索可以理解为查找距离查询数据点距离最近的k个样本数据点。其中，数据点可以理解为带经纬度信息的一个对象，可以表示银行网点、设备、企业等。

具体地，基于所述查询经纬度在预先构建的K维树中进行K近邻搜索，包括：将所述查询经纬度转化成空间直角坐标系的查询点坐标，并基于所述查询点坐标在预先构建的K维树中进行K近邻搜索。

示例性地，将所述查询经纬度转化成空间直角坐标系的查询点坐标，包括：基于如下公式将所述查询经纬度转化成空间直角坐标系的查询点坐标：

lon＝lon/180*π

lat＝lat/180*π

x＝R*cos(lat)*cos(lon)

y＝R*cos(lat)*sin(lon)

z＝R*sin(lat)

其中，R表示地球半径；lon表示查询数据点的经度；lat表示查询数据点的纬度；π为圆周率；x表示所述查询数据点在空间直角坐标系中的横轴坐标；y 表示所述查询数据点在空间直角坐标系中的纵轴坐标；z表示所述查询数据点在空间直角坐标系中的竖轴坐标。

可选地，基于所述查询点坐标在预先构建的K维树中进行K近邻搜索，包括：确定所述查询点坐标中与预先构建的K维树中每个节点对应的分割轴维度对应的分割轴坐标值；基于所述分割轴坐标值在预先构建的K维树中进行K近邻搜索。

在本发明实施例中，所述K维树的构建方法，具体可包括：获取采集到的每个样本数据点的数据经纬度；将所述数据经纬度转换成空间直角坐标系的数据点坐标；基于样本数据集中每个样本数据点的所述数据点坐标构建所述K维树，其中，所述样本数据集包含有多个样本数据点。

类似地，可获取采集到的每个样本数据点的数据经纬度(lon，lat)，将所述数据经纬度(lon，lat)转换成空间直角坐标系的数据点坐标(x，y，z)，并基于如下公式将所述数据经纬度转化成空间直角坐标系的数据点坐标：

lon＝lon/180*π

lat＝lat/180*π

x＝R*cos(lat)*cos(lon)

y＝R*cos(lat)*sin(lon)

z＝R*sin(lat)

其中，R表示地球半径；lon表示查询数据点的经度；lat表示查询数据点的纬度；π为圆周率；x表示所述查询数据点在空间直角坐标系中的横轴坐标；y 表示所述查询数据点在空间直角坐标系中的纵轴坐标；z表示所述查询数据点在空间直角坐标系中的竖轴坐标。

具体地，基于样本数据集中每个样本数据点的所述数据点坐标构建所述K 维树，可包括：基于样本数据集中多个样本数据点的所述数据点坐标确定所述K维树的当前分割轴维度；基于所述当前分割轴维度以及所述样本数据点分别构建所述K维树的左分支和右分支。

可选地，所述基于样本数据集中多个样本数据点的所述数据点坐标确定所述K维树的当前分割轴维度，包括：对样本数据集中多个样本数据点的所述数据点坐标中每个维度的数据进行方差计算，取最大方差对应的维度作为所述K 维树的当前分割轴维度；或者，随机选择样本数据点的所述数据点坐标中一个维度的数据作为初始分割轴维度，进而在节点发生变化时轮流取不同的维度作为当前分割轴维度。

可选地，基于所述当前分割轴维度以及所述样本数据点分别确定所述K维树的左分支和右分支，包括：基于所述当前分割轴维度对所述样本数据集进行检索，得到所述当前分割轴维度的中位数数据，并将中位数数据作为当前节点数据；基于所述当前分割轴维度、所述当前节点数据以及所述样本数据集中未构建于所述K维树上的样本数据点，分别构建所述K维树的左分支和右分支。

具体地，基于所述当前分割轴维度、所述当前节点数据以及所述样本数据集中未构建于所述K维树上的样本数据点，构建所述K维树的左分支和右分支，包括：基于所述当前分割轴维度，将所有小于所述当前节点数据的样本数据点划分到所述K维树的左分支中，将所有大于或等于所述当前节点数据的样本数据点划分到所述K维树的右分支中。

在本发明实施例中，可选地，如果所述样本数据集中未构建于所述K维树上的样本数据点的数量是否小于预设数量阈值，则将所述当前节点数据作为所述K维树的叶子节点数据。其中，预设数量阈值可以根据实际需求进行设置，其具体数值在此并不做限定，例如可以是10或20等。这样设置的好处，在于能够在保证运算量不大的情况下，有效降低K维树的深度，简化构建操作，加快搜索速度。

S130、将至少一个所述目标数据点对应的目标地理位置显示于所述目标客户端的目标页面上。

示例性地，目标数据点对应的目标地理位置可以是通过名称和/或所处的城市街道等方式进行显示。显示方式可以是文字和/或图片等，在此不做具体限定。

具体地，如果存在两个或两个以上的目标数据点，则可以根据目标数据点与查询数据点之间的距离，确定目标数据点对应的目标地理位置在目标页面上的目标显示顺序，进而，基于该目标显示顺序将目标数据点对应的目标地理位置显示于所述目标客户端的目标页面上。

示例性地，可以按照目标数据点与查询数据点之间的距离由进到远的顺序从上往下或者从前往后将目标数据点对应的目标地理位置显示于所述目标客户端的目标页面上。换言之，优先现实目标数据点与查询数据点之间的距离较近的目标地理位置。

可选地，在所述基于所述查询点坐标在预先构建的K维树中进行K近邻搜索，得到与所述查询数据点对应的至少一个目标数据点之后，还包括：计算每个所述目标数据点与所述查询数据点之间的直线距离；基于所述直线距离计算所述目标数据点与所述查询数据点之间的弧长，并将所述弧长与所述目标地理位置对应显示于所述目标页面上。

具体的，可基于如下公式计算每个所述目标数据点与所述查询数据点之间的直线距离：

其中,L表示目标数据点与所述查询数据点之间的直线距离；x

其中，基于所述直线距离计算所述目标数据点与所述查询数据点之间的弧长具体可以通过如下公式实现：

S＝2*R*arcsin(L/2R)，

其中，S为目标数据点与所述查询数据点之间的弧长；L为目标数据点与所述查询数据点之间的直线距离，R为地球半径。

本技术方案中，以弧长作为目标地理位置与查询数据点对应的查询位置之间的实际距离，相对于根据二维经纬度计算，更加精准。

本发明实施例的技术方案，通过在预先构建的K维树中进行K近邻搜索，解决了现有的搜索方式搜索速度低以及容易产生冗余计算的技术问题，不仅不受限于距离范围，而且能够减少查询量，提升查询速度，更快地响应目标客户端的数据查询请求，从而提升用户体验。

实施例二

图2为本发明实施例二所提供的一种地理位置的搜索方法的流程示意图，本实施例在本发明实施例中任一可选技术方案的基础上，可选地，所述基于所述查询经纬度在预先构建的K维树中进行K近邻搜索，包括：以根节点为当前分支的根节点，以确定当前分支；判断当前分支包含的样本数据点是否全部被访问过；如果当前分支包含的样本数据点没有全部被访问过，则判断所述根节点的分割轴坐标值是否小于所述查询数据点的查询经纬度所对应的分割轴坐标值；如果是，则进入预先构建的K维树的左分支进行搜索，并将所述当前分支的根节点更新为左分支的根节点；如果否，则进入预先构建的K维树的右分支进行搜索，并将所述当前分支的根节点更新为右分支的根节点；如果所述当前分支包含的样本数据点已全部被访问过，则获取缓存信息中包含的所述当前分支包含的样本数据点与所述查询数据点之间的分支最大距离和分支最小距离；基于所述分支最大距离和分支最小距离在预先构建的K维树中进行K近邻搜索。

如图2所示，本实施例的方法具体可包括：

S210、接收目标客户端所发送目标页面的数据查询请求，获取与所述数据查询请求对应的查询数据点的查询经纬度。

S220、以根节点为当前分支的根节点，以确定当前分支。

换言之，以K维树的根节点作为起点，进行搜索，以根节点所在的分支作为当前分支。

S230、判断当前分支包含的样本数据点是否全部被访问过，如果当前分支包含的样本数据点没有全部被访问过，执行S240，如果所述当前分支包含的样本数据点已全部被访问过，则执行S270。

在本发明实施例中，如果检测到基于该查询数据点的数据查询请求为首次请求，则可以搜索出预设数量的显示页面所对应的目标数据点，并将所述目标数据点与所述显示页面对应存储。

这样设置的好处在于，当目标客户端接收到的后续的数据查询请求查询所对应的数据如果落在这预先缓存的样本数据点中时，则直接读取并返回与该数据查询请求对应的目标数据点，避免了频繁的进行k近邻查询，如果落在所缓存的样本数据点之外才进行k近邻查询，提升响应速度。

考虑到现有的数据显示方式多采用分页显示，为了进一步提升搜索效率，避免重读搜索，产生冗余计算，本发明实施例的技术方案，在进行k近邻分页搜索时，可保存如下两类信息：

针对每次分页的搜索结果，保存该页面包含的样本数据点到查询数据点的页面最大距离

如果当前分支所包含的所有样本数据点均已被访问过，保存所述当前分支包含的样本数据点到查询数据点的分支最小距离和分支最大距离。

如果当前分支包含的样本数据点已经全部被访问过，则无需重复访问，可读取包含的所述当前分支包含的样本数据点与所述查询数据点之间的分支最大距离和分支最小距离。

如果当前分支包含的样本数据点没有全部被访问过，则需要对该当前分支的数据进行进一步搜索。

S240、判断所述根节点的分割轴坐标值是否小于所述查询数据点的查询经纬度所对应的分割轴坐标值，如果是，执行S250，否则执行S260。

具体地，可基于当前分支的根节点的分割轴坐标值与查询数据点的查询经纬度所对应的分割轴坐标值的大小确定搜索路径。

S250、进入预先构建的K维树的左分支进行搜索，并将所述当前分支的根节点更新为左分支的根节点，返回执行S240。

S260、进入预先构建的K维树的右分支进行搜索，并将所述当前分支的根节点更新为右分支的根节点，返回执行S240。

S270、获取缓存信息中包含的所述当前分支包含的样本数据点与所述查询数据点之间的分支最大距离和分支最小距离，执行S280。

其中，当前分支包含的样本数据点与所述查询数据点之间的分支最大距离和分支最小距离，需要分别计算当前分支包含的每个样本数据点与查询数据点之间的直线距离，从计算出的所有距离中选出最大值作为分支最大距离，选出最小值作为分支最小距离。其中，计算直线距离的方式可以参见前述方式，在此不再赘述。

S280、基于所述分支最大距离和分支最小距离在预先构建的K维树中进行 K近邻搜索，得到与所述查询数据点对应的至少一个目标数据点，其中，所述 K维树基于每个样本数据点的数据经纬度构建。

具体地，基于所述分支最大距离和分支最小距离在预先构建的K维树中进行K近邻搜索，可包括：如果所述缓存信息中包含与所述目标页面对应的相邻页面的页面最大距离，且未包含所述目标页面的页面最大距离和页面最小距离，则基于所述相邻页面的页面最大距离、所述目标页面的页面最大距离、所述当前分支的分支最小距离以及分支最小距离确定预先构建的K维树中的待搜索分支，并基于所述待搜索分支在K维树中进行K近邻搜索。

如果所述缓存信息中未包含所述目标页面的页面最大距离和页面最小距离，则说明之前没有搜索过这一页面的数据，此时可以判断缓存中是否包含与所述目标页面对应的相邻页面的页面最大距离，如果是，可以基于所述相邻页面的页面最大距离、所述目标页面的页面最大距离、所述当前分支的分支最小距离以及分支最小距离确定预先构建的K维树中的待搜索分支。

需要说明的时，目标页面的页面最大距离可以根据实际情况进行设定，其具体数值在此不做限定，为了便于计算，可以将其设置为无穷大。

具体地，所述基于所述相邻页面的页面最大距离、所述目标页面的页面最大距离以及所述当前分支的分支最小距离和分支最大距离确定预先构建的K维树中的待搜索分支，包括：如果所述当前分支的分支最大距离小于等于所述相邻页面的页面最大距离，或者，所述当前分支的分支最小距离大于所述目标页面的页面最大距离，则将所述当前分支标记为已访问，并将所述当前分支的根节点的父节点更新为所述当前分支的根节点，以更新所述当前分支；进而，返回执行判断当前分支包含的样本数据点是否全部被访问过的操作。

如果所述当前分支的分支最大距离小于等于所述相邻页面的页面最大距离，则表明这些数据点都落在第i+1页之前的页面中，所以可以将该分支标记为已访问，无需再进行访问。

如果所述当前分支的分支最小距离大于所述目标页面的页面最大距离，则表明该分支包含的数据点都落在第i+1页之外，将该分支标记为已访问，无需再进行访问。

可选地，基于所述相邻页面的页面最大距离、所述目标页面的页面最大距离以及所述当前分支的分支最小距离和分支最大距离确定预先构建的K维树中的待搜索分支，包括：确定所述当前分支的分支最小距离和分支最大距离所构成的第一距离区间，以及所述相邻页面的页面最大距离和所述目标页面的页面最大距离所构成的第二距离区间之间是否存在交集；如果所述第一距离区间与所述第二距离区间存在交集，则将所述当前分支作为预先构建的K维树中的待搜索分支。

如果第一距离区间与所述第二距离区间存在部分相交，或者，该当前分支不存在缓存信息，则表明当前分支可能存在落在目标页面之内的样本数据点，此时需要基于当前分支进行搜索。

可选地，基于所述分支最大距离和/或分支最小距离在预先构建的K维树中进行K近邻搜索，包括：如果所述缓存信息中包含所述目标页面的页面最大距离和页面最小距离，则基于所述目标页面的页面最小距离和页面最大距离以及所述当前分支的分支最小距离和分支最大距离在K维树中进行K近邻搜索。

如果所述缓存信息中包含所述目标页面的页面最大距离和页面最小距离，则之前搜索过的页，此时可基于所述目标页面的页面最小距离和页面最大距离以及所述当前分支的分支最小距离和分支最大距离在K维树中进行K近邻搜索。

可选地，基于所述目标页面的页面最小距离和页面最大距离以及所述当前分支的分支最小距离和分支最大距离在K维树中进行K近邻搜索，可包括：如果所述当前分支的分支最大距离小于所述目标页面的页面最小距离，或者，所述当前分支的分支最小距离大于所述目标页面的页面最大距离，则将所述当前分支标记为已访问，并将所述当前分支的根节点的父节点更新为所述当前分支的根节点，以更新所述当前分支；进而，返回执行判断当前分支包含的样本数据点是否全部被访问过的操作，继续进行搜索。

可选地，基于所述目标页面的页面最小距离和页面最大距离以及所述当前分支的分支最小距离和分支最大距离在K维树中进行K近邻搜索，包括：如果所述目标页面的最小距离小于或等于所述当前分支的分支最小距离且所述当前分支的最大距离小于所述目标页面的页面最大距离，则将所述当前分支的包含的样本数据点添加至候选集中，将所述当前分支标记为已访问，并将所述当前分支的根节点的父节点更新为所述当前分支的根节点，以更新所述当前分支；进而，返回执行判断当前分支包含的样本数据点是否全部被访问过的操作，继续进行搜索。

可选地，基于所述目标页面的页面最小距离和页面最大距离以及所述当前分支的分支最小距离和分支最大距离在K维树中进行K近邻搜索，包括：确定所述当前分支的分支最小距离和分支最大距离所构成的第三距离区间，以及所述目标页面的页面最大距离和所述目标页面的页面最大距离所构成的第四距离区间之间是否存在交集；如果所述第三距离区间与所述第四距离区间存在交集，则判断所述当前分支的根节点是否为叶子节点；如果是，则将所述叶子节点对应的样本数据点中到查询数据点的距离处于所述目标页面的页面最小距离与页面最大距离范围内的样本数据点添加至候选集中；当所述候选集中的样本数据点的数量达到预设阈值时，将所述候选集中的样本数据点作为所述查询数据点对应的至目标数据点。

如果当前分支的根节点不是叶子节点，则进入该当前分支的子分支继续进行递归搜索。

S290、将至少一个所述目标数据点对应的目标地理位置显示于所述目标客户端的目标页面上。

本实施例的技术方案，能够通过判断当前分支包含的样本数据点是否全部被访问过，确定在K维树中进行K近邻搜索中的搜索方式，避免对已访问过的分支进行不必要的重复访问，提升搜索效率，进而通过缓存信息中的所缓存的分支包含的样本数据点与所述查询数据点之间的分支最大距离和分支最小距离，辅助进行K近邻搜索，能够在不占用过多缓存空间的同时，借助分支最大距离和分支最小距离更加准确地更加快速地进行K近邻搜索。

实施例三

本实施例提供了一种基于本发明实施例中的地理位置的搜索方法进行地理位置搜索的可选实例。其具体实现过程如下：

一、建立数据索引

在基于K维树(K-Dimensional tree，KDTree)进行K邻近搜索之前，需要先基于KDTree建立数据索引。具体可以包括：

1)经纬度转直角坐标系

获取采集到的每个样本数据点的数据经纬度(lon，lat)，将所述数据经纬度(lon，lat)转换成空间直角坐标系的数据点坐标(x，y，z)，并基于如下公式将所述数据经纬度转化成空间直角坐标系的数据点坐标：

lon＝lon/180*π

lat＝lat/180*π

x＝R*cos(lat)*coS(lon)

y＝R*cos(lat)*sin(lon)

z＝R*sin(lat)

其中，R表示地球半径；lon表示样本数据点的经度；lat表示样本数据点的纬度；π为圆周率；x表示所述样本数据点在空间直角坐标系中的横轴坐标；y表示所述样本数据点在空间直角坐标系中的纵轴坐标；z表示所述样本数据点在空间直角坐标系中的竖轴坐标。

2)使用KDTree数据结构对(x，y，z)样本数据集建立二叉树索引

KDTree是一种分割k维数据空间的数据结构，主要应用于多维空间关键数据的高效搜索，如范围搜索和最近邻搜索。因此，可以基于样本数据集中每个样本数据点的数据点坐标构建KDTree，其中，所述样本数据集包含有多个样本数据点。

对于样本数据点的空间坐标数据(x，y，z)，有3个维度，具体地，建立 KDTree的步骤可以包括：

1、初始化分割轴维度：对样本数据集中多个样本数据点的所述数据点坐标中每个维度的数据进行方差计算，取最大方差对应的维度作为所述K维树的当前分割轴维度，标记为r。

2、选择分割点：基于所述当前分割轴维度对所述样本数据集进行检索，得到所述当前分割轴维度的中位数数据，并将所述中位数数据作为当前节点数据，即对当前数据集按分割轴维度进行检索，找到该维度的中位数数据，并将其放入到当前节点上。如果当前数据集中包含的样本数据点的数量是否小于预设数量阈值N，则将所述当前节点数据作为所述K维树的叶子节点数据。其中，当前数据集可以理解为包含未构建于所述K维树上的样本数据点的数据集，可通过更新样本数据集得到；N为正整数。若当前节点为叶子节点，不再进行进一步划分双支。

3、划分双支：

划分左支：基于所述当前分割轴维度，将所有小于所述当前节点数据的样本数据点划分到所述K维树的左分支中；

划分右支：基于所述当前分割轴维度，将所有大于或等于所述当前节点数据的样本数据点划分到所述K维树的右分支中。

4、更新分割轴维度：

可选地，采用r＝(r+1)％3的方式确定分割轴纬度，轮流选择不同维度作为分割轴维度，或者，选择均采用方差最大的维度作为分割轴维度。

5、建立子树：

建立左子树：在左分支的数据中递归进行步骤2；

建立右子树：在右分支的数据中递归进行步骤2。

二、数据搜索

当接收目标客户端所发送目标页面的数据查询请求时，获取与所述数据查询请求对应的查询数据点的查询经纬度，将查询经纬度转化成空间直角坐标系的查询点坐标转换成直角坐标(x，y，z)，具体地，可基于如下公式将所述查询经纬度转化成空间直角坐标系的查询点坐标：

lon＝lon/180*π

lat＝lat/180*π

x＝R*cos(lat)*cos(lon)

y＝R*cos(lat)*sin(lon)

z＝R*sin(lat)

其中，R表示地球半径；lon表示查询数据点的经度；lat表示查询数据点的纬度；π为圆周率；x表示所述查询数据点在空间直角坐标系中的横轴坐标；y 表示所述查询数据点在空间直角坐标系中的纵轴坐标；z表示所述查询数据点在空间直角坐标系中的竖轴坐标。

然后，在建立好的KDTree索引上，进行k近邻搜索。

KDTree上的每一个节点代表空间当中的一小块区域，搜索时基于区域进行片区检索。搜索步骤如下：

1、寻找查询数据点所归属的叶子节点：

1)设定当前节点为根节点

2)如果当前节点的分割轴坐标值小于所述查询数据点的查询经纬度所对应的分割轴坐标值，则进入左子树，并将当前节点更新为左子树根节点；如果当前节点的分割轴坐标值大于所述查询数据点的查询经纬度所对应的分割轴坐标值，则进入右子树，将当前节点更新为右子树的根节点

3)重复第2)步，直到达到叶子节点

2、递归搜索

1)建立空的候选集S

2)对于分支节点：

2.1)如果左右子分支均已访问，则将该分支节点标记为已访问并跳转到该分支节点的父节点；

2.2)如果当前分支存在未访问子节点：

2.2.1)如果候选集S中样本数据点的数量小于k或者查询数据点到子分支的分割轴的距离小于候选集中的最大距离，则进入子分支，并跳转到第2)步；

2.2.2)如果候选集S中样本数据点的数量为k且查询数据点到子分支的分割轴的距离大于等于候选集中的最大距离，则提前剪枝，并将该分支标记为已访问；

3)对于叶子节点对应的每个样本数据点，如果候选集S样本数小于k或者查询数据点到叶子节点每个样本数据点的距离小于候选集S中的最大距离，则将该样本数据点加入候选集，并踢出候选集中最大距离的样本数据点，然后跳转到该叶子节点的父节点。

当KDTree的根节点为已访问时，则完成搜索过程，候选集S的数据点即为最终搜索出来的k近邻。

需要说明的时，在搜索过程中，可以通过计算目标数据点与所述查询数据点之间的直线距离来确定最近邻目标数据点。

具体地，可以基于如下公式计算每个所述目标数据点与所述查询数据点之间的直线距离：

其中,L表示目标数据点与所述查询数据点之间的直线距离；x

上述技术方案尤其适用于弧长小于180度的情况，例如在中国的国家领土范围内，此时，当弦长A大于弦长B时，与弦长A对应的弧长A大于与弦长B 对应的弧长B；故，求最近邻时不需要精确计算真实弧长，只要知道目标数据点与查询数据点的直线距离即可。

三、搜索状态缓存与恢复

在本发明实施例中，为了进一步提升搜索效率，可通过建立二级缓存的方式来保证高效搜索。

第一级缓存：结果缓存

如果接收到的目标客户端发送的数据查询请求所对应的实际分页大小是n，则实际每次基于KDTree进行k近邻查询的时候，可一次性查询10*n个最近样本数据点出来，并缓存下来；其中，n是正整数。例如，n可以是小于等于 100的正整数。

即，如果检测到基于该查询数据点的数据查询请求为首次请求，则可以搜索出预设数量的显示页面所对应的目标数据点，并将所述目标数据点与所述显示页面对应存储。

这样设置的好处在于，当目标客户端接收到的后续的数据查询请求查询所对应的数据如果落在这预先缓存的10*n个样本数据点中时，则直接读取并返回与该数据查询请求对应的目标数据点，避免了频繁的进行k近邻查询，如果落在这10*n个数据点之外才进行k近邻查询，提升响应速度。

第二级缓存：基于KDTree进行k近邻搜索时的搜索状态缓存

在进行k近邻分页搜索时，保存如下两类信息：

a.对于每次分页的搜索结果，保存该页面包含的样本数据点到查询数据点的页面最大距离

b.设分支所包含的所有样本数据点均访问过，则该分支为已全访问分支，保存该分支包含的样本数据点到查询数据点的分支最小距离MinDist和分支最大距离MaxDist。

基于缓存数据的分页最近邻查询，分两种情况：

1、查询新的一页：设已经查询过从第1页到第i页的地理位置数据，现在查询第i+1页，每一页包含数据点个数为n，n为正整数：

首先，将第i+1页的

1)寻找已访问分支：(下沉)

1.1)设定根节点为当前分支的根节点

1.2)如果当前分支包含的样本数据点没有全部被访问过，则不存在缓存信息，如果当前分支的根节点的分割轴坐标值小于所述查询数据点的查询经纬度所对应的分割轴坐标值，，则进入预先构建的K维树的左分支进行搜索，并将所述当前分支的根节点更新为左分支的根节点；否则，进入预先构建的K维树的右分支进行搜索，并将所述当前分支的根节点更新为右分支的根节点；

1.3)重复第1.2)步直到找到一个已访问分支且

2.递归搜索第i+1页：(回溯)

2.1)建立第i+1页包含样本数据点的空候选集S

2.2)对于当前分支：

2.2.1)如果当前分支包含的样本数据点已全部访问过：

2.2.1.1)如果该分支的

2.2.1.2)如果该分支

2.2.1.3)如果该分支的距离区间[MinDist，MaxDist]与区间

3.当KDTree的根节点为已访问时，则完成搜索过程，候选集S的样本数据点即为最终搜索出来的k近邻。

(二)查询之前搜索过的页：设已经查询从1到i页，假设现在用户往前翻页，要查看第j页的数据(1≤j

首先从缓存信息中查询得到第j页的

1、寻找查询数据点归属叶子节点，与前述寻找查询数据点所归属的叶子节点的方式相同，在此不再赘述。

2、递归搜索中，对于分支节点：

2.1)如果该分支没有缓存信息，则处理方式与前述递归搜索的方式相同

2.2)如果该分支下有缓存信息，则表示该分支所包含的所有样本数据点已经全部访问过：

2.2.1)如果该分支

2.2.2)如果该分支

2.2.3)如果该分支

2.2.4)如果该分支[MinDist，MaxDist]与区间

3、如果j页候选集中样本数据点的数量达到n，则结束搜索。

将候选集中的样本数据点作为目标数据点，确定与目标数据点对应的目标地理位置，然后还可以基于所述直线距离计算所述目标数据点与所述查询数据点之间的弧长，并将所述弧长与所述目标地理位置对应显示于所述目标页面上。

其中，基于所述直线距离计算所述目标数据点与所述查询数据点之间的弧长具体可以通过如下公式实现：

S＝2*R*arcsin(L/2R)，

其中，S为目标数据点与所述查询数据点之间的弧长；L为目标数据点与所述查询数据点之间的直线距离，R为地球半径。

本实施例的技术方案，通过KDTree对数据点在内存中建立索引，在实时查询时，通过KDTree进行快速最近邻查找，并不受限于距离范围；同时，为每一个查询数据点缓存KDTree查找状态，可以根据分页参数，在历史查找信息的基础上继续最近邻搜索，避免了计算上的冗余，通过缓存少量的数据，在不保存每一页具体数据点的条件下，可以大大减少分页查询需要访问的数据点数量，减小候选集，提高分页查询的效率，提升响应时间；实现空间与时间上的最优。

实施例四

图3为本发明实施例三提供的一种地理位置的搜索装置的结构示意图，本实施例可适用于对地理位置进行搜索情况，该装置具体可包括：查询请求模块、数据搜索模块和数据显示模块。

其中，查询请求模块，用于接收目标客户端所发送目标页面的数据查询请求，获取与所述数据查询请求对应的查询数据点的查询经纬度；数据搜索模块，用于基于所述查询经纬度在预先构建的K维树中进行K近邻搜索，得到与所述查询数据点对应的至少一个目标数据点，其中，所述K维树基于每个样本数据点的数据经纬度构建；数据显示模块，用于将至少一个所述目标数据点对应的目标地理位置显示于所述目标客户端的目标页面上。

本发明实施例的技术方案，通过在预先构建的K维树中进行K近邻搜索，解决了现有的搜索方式搜索速度低以及容易产生冗余计算的技术问题，不仅不受限于距离范围，而且能够减少查询量，提升查询速度，更快地响应目标客户端的数据查询请求，从而提升用户体验。

在本发明实施例任一可选技术方案的基础上，可选地，所述数据搜索模块包括：分支确定单元、访问判断单元、坐标判断单元、左分支搜索单元、右分支搜索单元、分支距离获取单元和分支距离搜索单元。

其中，分支确定单元，用于以根节点为当前分支的根节点，确定当前分支；访问判断单元，用于判断所述当前分支包含的样本数据点是否全部被访问过；坐标判断单元，用于如果当前分支包含的样本数据点没有全部被访问过，则判断所述根节点的分割轴坐标值是否小于所述查询数据点的查询经纬度所对应的分割轴坐标值；左分支搜索单元，用于如果是，则进入预先构建的K维树的左分支进行搜索，并将所述当前分支的根节点更新为左分支的根节点；右分支搜索单元，用于如果否，则进入预先构建的K维树的右分支进行搜索，并将所述当前分支的根节点更新为右分支的根节点；分支距离获取单元，用于如果所述当前分支包含的样本数据点已全部被访问过，则获取缓存信息中包含的所述当前分支包含的样本数据点与所述查询数据点之间的分支最大距离和分支最小距离；分支距离搜索单元，用于基于所述分支最大距离和分支最小距离在预先构建的K维树中进行K近邻搜索。

在本发明实施例任一可选技术方案的基础上，可选地，所述分支距离搜索单元可用于：

如果所述缓存信息中包含与所述目标页面对应的相邻页面的页面最大距离，且未包含所述目标页面的页面最大距离和页面最小距离，则基于所述相邻页面的页面最大距离、所述目标页面的页面最大距离、所述当前分支的分支最小距离以及分支最小距离确定预先构建的K维树中的待搜索分支，并基于所述待搜索分支在K维树中进行K近邻搜索。

在本发明实施例任一可选技术方案的基础上，可选地，所述分支距离搜索单元具体可用于：

如果所述当前分支的分支最大距离小于等于所述相邻页面的页面最大距离，或者，所述当前分支的分支最小距离大于所述目标页面的页面最大距离，则将所述当前分支标记为已访问，并将所述当前分支的根节点的父节点更新为所述当前分支的根节点，以更新所述当前分支；

返回执行判断当前分支包含的样本数据点是否全部被访问过的操作。

在本发明实施例任一可选技术方案的基础上，可选地，所述分支距离搜索单元具体可用于：

确定所述当前分支的分支最小距离和分支最大距离所构成的第一距离区间，以及所述相邻页面的页面最大距离和所述目标页面的页面最大距离所构成的第二距离区间之间是否存在交集；

如果所述第一距离区间与所述第二距离区间存在交集，则将所述当前分支作为预先构建的K维树中的待搜索分支。

在本发明实施例任一可选技术方案的基础上，可选地，所述分支距离搜索单元可用于：

如果所述缓存信息中包含所述目标页面的页面最大距离和页面最小距离，则基于所述目标页面的页面最小距离和页面最大距离以及所述当前分支的分支最小距离和分支最大距离在K维树中进行K近邻搜索。

在本发明实施例任一可选技术方案的基础上，可选地，所述分支距离搜索单元可用于：

如果所述当前分支的分支最大距离小于所述目标页面的页面最小距离，或者，所述当前分支的分支最小距离大于所述目标页面的页面最大距离，则将所述当前分支标记为已访问，并将所述当前分支的根节点的父节点更新为所述当前分支的根节点，以更新所述当前分支；

返回执行判断当前分支包含的样本数据点是否全部被访问过的操作。

在本发明实施例任一可选技术方案的基础上，可选地，所述分支距离搜索单元可用于：

如果所述目标页面的最小距离小于或等于所述当前分支的分支最小距离且所述当前分支的最大距离小于所述目标页面的页面最大距离，则将所述当前分支的包含的样本数据点添加至候选集中，将所述当前分支标记为已访问，并将所述当前分支的根节点的父节点更新为所述当前分支的根节点，以更新所述当前分支；

返回执行判断当前分支包含的样本数据点是否全部被访问过的操作。

在本发明实施例任一可选技术方案的基础上，可选地，所述分支距离搜索单元可用于：

确定所述当前分支的分支最小距离和分支最大距离所构成的第三距离区间，以及所述目标页面的页面最大距离和所述目标页面的页面最大距离所构成的第四距离区间之间是否存在交集；

如果所述第三距离区间与所述第四距离区间存在交集，则判断所述当前分支的根节点是否为叶子节点；

如果是，则将所述叶子节点对应的样本数据点中到查询数据点的距离处于所述目标页面的页面最小距离与页面最大距离范围内的样本数据点添加至候选集中；

当所述候选集中的样本数据点的数量达到预设阈值时，将所述候选集中的样本数据点作为所述查询数据点对应的至目标数据点。

在本发明实施例任一可选技术方案的基础上，可选地，所述数据搜索模块用于：

将所述查询经纬度转化成空间直角坐标系的查询点坐标，并基于所述查询点坐标在预先构建的K维树中进行K近邻搜索。

在本发明实施例任一可选技术方案的基础上，可选地，所述数据搜索模块具体可用于：

基于如下公式将所述查询经纬度转化成空间直角坐标系的查询点坐标：

lon＝lon/180*π

lat＝lat/180*π

x＝R*cos(lat)*cos(lon)

y＝R*cos(lat)*sin(lon)

z＝R*sin(lat)

其中，R表示地球半径；lon表示查询数据点的经度；lat表示查询数据点的纬度；π为圆周率；x表示所述查询数据点在空间直角坐标系中的横轴坐标；y 表示所述查询数据点在空间直角坐标系中的纵轴坐标；z表示所述查询数据点在空间直角坐标系中的竖轴坐标。

在本发明实施例任一可选技术方案的基础上，可选地，所述数据搜索模块进一步可用于：

确定所述查询点坐标中与预先构建的K维树中每个节点对应的分割轴维度对应的分割轴坐标值；

基于所述分割轴坐标值在预先构建的K维树中进行K近邻搜索。

在本发明实施例任一可选技术方案的基础上，可选地，所述地理位置的搜索方法还包括：

距离显示模块，用于在所述基于所述查询点坐标在预先构建的K维树中进行K近邻搜索，得到与所述查询数据点对应的至少一个目标数据点之后，计算每个所述目标数据点与所述查询数据点之间的直线距离；

基于所述直线距离计算所述目标数据点与所述查询数据点之间的弧长，并将所述弧长与所述目标数据点对应显示于所述目标页面上。

在本发明实施例任一可选技术方案的基础上，可选地，所述距离显示模块用于：

基于如下公式计算每个所述目标数据点与所述查询数据点之间的直线距离：

其中,L表示目标数据点与所述查询数据点之间的直线距离；x

在本发明实施例任一可选技术方案的基础上，可选地，所述地理位置的搜索装置还包括所述K维树的构建模块，其中，K维树的构建模块具体可包括：

数据经纬度获取单元，用于获取采集到的每个样本数据点的数据经纬度；

数据点坐标转换单元，用于将所述数据经纬度转换成空间直角坐标系的数据点坐标；

K维树构建单元，用于基于样本数据集中每个样本数据点的所述数据点坐标构建所述K维树，其中，所述样本数据集包含有多个样本数据点。

在本发明实施例任一可选技术方案的基础上，可选地，所述K维树构建单元用于：

分割轴维度确定子单元，用于基于样本数据集中多个样本数据点的所述数据点坐标确定所述K维树的当前分割轴维度；

左右分支构建子单元，用于基于所述当前分割轴维度以及所述样本数据点分别构建所述K维树的左分支和右分支。

在本发明实施例任一可选技术方案的基础上，可选地，所分割轴维度确定子单元用于：

对样本数据集中多个样本数据点的所述数据点坐标中每个维度的数据进行方差计算，取最大方差对应的维度作为所述K维树的当前分割轴维度。

在本发明实施例任一可选技术方案的基础上，可选地，所述左右分支构建子单元用于：

基于所述当前分割轴维度对所述样本数据集进行检索，得到所述当前分割轴维度的中位数数据，并将所述中位数数据作为当前节点数据；

基于所述当前分割轴维度、所述当前节点数据以及所述样本数据集中未构建于所述K维树上的样本数据点，分别构建所述K维树的左分支和右分支。

在本发明实施例任一可选技术方案的基础上，可选地，所述左右分支构建子单元具体可用于：

基于所述当前分割轴维度，将所有小于所述当前节点数据的样本数据点划分到所述K维树的左分支中，将所有大于或等于所述当前节点数据的样本数据点划分到所述K维树的右分支中。

在本发明实施例任一可选技术方案的基础上，可选地，所述K维树构建子单元具体可用于：

如果所述样本数据集中未构建于所述K维树上的样本数据点的数量是否小于预设数量阈值，则将所述当前节点数据作为所述K维树的叶子节点数据。

上述地理位置的搜索装置可执行本发明任意实施例所提供的地理位置的搜索方法，具备执行地理位置的搜索方法相应的功能模块和有益效果。

实施例五

图4为本发明实施例六所提供的一种电子设备的结构示意图。图4示出了适于用来实现本发明实施方式的示例性电子设备12的框图。图4显示的电子设备12仅仅是一个示例，不应对本发明实施例的功能和使用范围带来任何限制。

如图4所示，电子设备12以通用计算设备的形式表现。电子设备12的组件可以包括但不限于：一个或者多个处理器或者处理单元16，系统存储器28，连接不同系统组件(包括系统存储器28和处理单元16)的总线18。

总线18表示几类总线结构中的一种或多种，包括存储器总线或者存储器控制器，外围总线，图形加速端口，处理器或者使用多种总线结构中的任意总线结构的局域总线。举例来说，这些体系结构包括但不限于工业标准体系结构(ISA) 总线，微通道体系结构(MAC)总线，增强型ISA总线、视频电子标准协会(VESA) 局域总线以及外围组件互连(PCI)总线。

电子设备12典型地包括多种计算机系统可读介质。这些介质可以是任何能够被电子设备12访问的可用介质，包括易失性和非易失性介质，可移动的和不可移动的介质。

系统存储器28可以包括易失性存储器形式的计算机系统可读介质，例如随机存取存储器(RAM)30和/或高速缓存存储器32。电子设备12可以进一步包括其它可移动/不可移动的、易失性/非易失性计算机系统存储介质。仅作为举例，存储系统34可以用于读写不可移动的、非易失性磁介质(图4未显示，通常称为“硬盘驱动器”)。尽管图4中未示出，可以提供用于对可移动非易失性磁盘(例如“软盘”)读写的磁盘驱动器，以及对可移动非易失性光盘(例如CD-ROM, DVD-ROM或者其它光介质)读写的光盘驱动器。在这些情况下，每个驱动器可以通过一个或者多个数据介质接口与总线18相连。系统存储器28可以包括至少一个程序产品，该程序产品具有一组(例如至少一个)程序模块，这些程序模块被配置以执行本发明各实施例的功能。

具有一组(至少一个)程序模块42的程序/实用工具40，可以存储在例如系统存储器28中，这样的程序模块42包括但不限于操作系统、一个或者多个应用程序、其它程序模块以及程序数据，这些示例中的每一个或某种组合中可能包括网络环境的实现。程序模块42通常执行本发明所描述的实施例中的功能和/或方法。

电子设备12也可以与一个或多个外部设备14(例如键盘、指向设备、显示器24等)通信，还可与一个或者多个使得用户能与该电子设备12交互的设备通信，和/或与使得该电子设备12能与一个或多个其它计算设备进行通信的任何设备(例如网卡，调制解调器等等)通信。这种通信可以通过输入/输出(I/O) 接口22进行。并且，电子设备12还可以通过网络适配器20与一个或者多个网络(例如局域网(LAN)，广域网(WAN)和/或公共网络，例如因特网)通信。如图4所示，网络适配器20通过总线18与电子设备12的其它模块通信。应当明白，尽管图4中未示出，可以结合电子设备12使用其它硬件和/或软件模块，包括但不限于：微代码、设备驱动器、冗余处理单元、外部磁盘驱动阵列、RAID 系统、磁带驱动器以及数据备份存储系统等。

处理单元16通过运行存储在系统存储器28中的程序，从而执行各种功能应用以及数据处理，例如实现本发实施例所提供的一种地理位置的搜索方法。

实施例六

本发明实施例六还提供一种包含计算机可执行指令的存储介质，所述计算机可执行指令在由计算机处理器执行时用于执行一种地理位置的搜索方法，该方法包括：

接收目标客户端所发送目标页面的数据查询请求，获取与所述数据查询请求对应的查询数据点的查询经纬度；

基于所述查询经纬度在预先构建的K维树中进行K近邻搜索，得到与所述查询数据点对应的至少一个目标数据点，其中，所述K维树基于每个样本数据点的数据经纬度构建；

将至少一个所述目标数据点对应的目标地理位置显示于所述目标客户端的目标页面上。

本发明实施例的计算机存储介质，可以采用一个或多个计算机可读的介质的任意组合。计算机可读介质可以是计算机可读信号介质或者计算机可读存储介质。计算机可读存储介质例如可以是——但不限于——电、磁、光、电磁、红外线、或半导体的系统、装置或器件，或者任意以上的组合。计算机可读存储介质的更具体的例子(非穷举的列表)包括：具有一个或多个导线的电连接、便携式计算机磁盘、硬盘、随机存取存储器(RAM)、只读存储器(ROM)、可擦式可编程只读存储器(EPROM或闪存)、光纤、便携式紧凑磁盘只读存储器 (CD-ROM)、光存储器件、磁存储器件、或者上述的任意合适的组合。在本文件中，计算机可读存储介质可以是任何包含或存储程序的有形介质，该程序可以被指令执行系统、装置或者器件使用或者与其结合使用。

计算机可读的信号介质可以包括在基带中或者作为载波一部分传播的数据信号，其中承载了计算机可读的程序代码。这种传播的数据信号可以采用多种形式，包括但不限于电磁信号、光信号或上述的任意合适的组合。计算机可读的信号介质还可以是计算机可读存储介质以外的任何计算机可读介质，该计算机可读介质可以发送、传播或者传输用于由指令执行系统、装置或者器件使用或者与其结合使用的程序。

计算机可读介质上包含的程序代码可以用任何适当的介质传输，包括——但不限于无线、电线、光缆、RF等等，或者上述的任意合适的组合。

可以以一种或多种程序设计语言或其组合来编写用于执行本发明实施例操作的计算机程序代码，所述程序设计语言包括面向对象的程序设计语言—诸如Java、Smalltalk、C++，还包括常规的过程式程序设计语言——诸如“C”语言或类似的程序设计语言。程序代码可以完全地在用户计算机上执行、部分地在用户计算机上执行、作为一个独立的软件包执行、部分在用户计算机上部分在远程计算机上执行、或者完全在远程计算机或服务器上执行。在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络——包括局域网(LAN)或广域网(WAN)—连接到用户计算机，或者，可以连接到外部计算机(例如利用因特网服务提供商来通过因特网连接)。

注意，上述仅为本发明的较佳实施例及所运用技术原理。本领域技术人员会理解，本发明不限于这里所述的特定实施例，对本领域技术人员来说能够进行各种明显的变化、重新调整和替代而不会脱离本发明的保护范围。因此，虽然通过以上实施例对本发明进行了较为详细的说明，但是本发明不仅仅限于以上实施例，在不脱离本发明构思的情况下，还可以包括更多其他等效实施例，而本发明的范围由所附的权利要求范围决定。