基于GeoHash的沿途POI搜索方法_武继银.pdf

第 39 卷第 2 期2023 年 6 月测 绘 标 准 化Standardization of Surveying and MappingVol 39No 2Jun 2023收稿日期:2022 08 11第一作者简介:武继银，硕士，现主要从事 GIS 系统的研究和开发工作。基于 GeoHash 的沿途 POI 搜索方法武继银吴广君翁郁炜(弈人(上海)科技有限公司上海200333)摘要:兴趣点(Point of Interest，POI)检索是导航和位置服务的关键技术之一。针对传统沿途 POI搜索方法对海量数据检索效率低的问题，本文提出一种基于地理哈希(GeoHash)的沿途 POI 搜索方法，实现快速确定沿途 POI 的搜索范围。首先，计算 POI 数据的 GeoHash;其次，采用道路上逐节点步长递进的方式提取与道路 GeoHash 集合匹配的 POI 数据;最后，计算与道路的欧氏距离，选择符合条件的 POI。实验结果表明，与传统的空间检索方法相比，本文提出的方法能显著减少搜索范围，提高搜索效率，实现了高效且精准的沿途 POI 搜索，在实际工程中具有较高的应用价值。关键词:兴趣点;地理哈希;沿途搜索中图分类号:P208DOI:10 20007/j cnki 61 1275/P 2023 02 06The GeoHash-based POI search method along a routeWU Jiyin，WU Guangjun，WENG Yuwei(Yiren(Shanghai)Technology Co，Ltd，Shanghai 200333，China)Abstract:POI retrieval is one of the key technologies in navigation and location services Aiming at theproblem of low efficiency of traditional POI search method along a route to retrieve massive data，thispaper proposes a POI search method along a route based on Geohash to quickly determine the searchingrange of POI along a route Firstly，the GeoHash of POI data is calculated Secondly，the POI datamatching the GeoHash set of a route is extracted by a step-by-step approach on each node of a routeFinally，the euclid distance from a route is calculated to select the qualified POI The results show thatcompared with the traditional spatial retrieval method，the proposed method can significantly reduce thesearching range，improve the searching efficiency，and realize the efficient and accurate POI search alongthe route，which has high application value in practical engineeringKeywords:POI;GeoHash;search along a route随着移动互联网的高速发展和人们出行需求的提高，电子导航技术已经成为现代生活的重要组成部分，为人们生活提供了很大便利。POI 检索是电子导航的重要功能之一。人们通过此功能不仅可以搜索自己位置附近的银行网点、餐馆、加油站等，而且可以搜索行驶路线沿途中的充电站、服务区、旅游景点等。因此，是否能够快速且高效地检索出相关的 POI，直接影响电子导航的使用体验。POI 检索一般分为关键字检索、地理空间检索和混合检索1 三类。关键字检索是把 POI 的名称或描述进行语义上的分词索引，并将分词作为关键字进行检索的一种技术;地理空间检索指在一定的地理条件下检索空间数据的一种操作，地理空间检索形式多种多样，比如在地理信息系统中查找某点周围的地物，查找某条公路两侧五公里内的乡镇，查找某一个地区内的风景名胜等;混合检索是结合关第 2 期武继银，等:基于 GeoHash 的沿途 POI 搜索方法键字检索和地理空间检索的检索技术，检索结果同时满足关键字检索和地理空间检索的条件。道路沿途 POI 检索是地理空间检索的一种应用，其地理条件为道路两侧一定距离内的所有地理空间，目的是检索出在此空间内的 POI 集合。不少学者对 POI 检索进行了研究。季刚通过 POI 数据预处理的方式，把道路 ID 赋予 POI 的道路属性，并编译生成道路索引文件、沿路 POI 索引文件，最后通过二分查找的方式搜索道路和相关的 POI。该方法索引数据量较大，数据更新不够灵活2。姚霄飞等使用 GeoHash 索引并结合 SQLite 数据库来检索 POI数据。该方法可以快速高效地检索，但仅适用于检索点周边的 POI 数据，不适用于道路沿线 POI 的检索3。Poppen 提出逐级剔除返回的方式来精确检索沿路的 POI。此方法虽然适用于道路沿线 POI的检索，但没有充分利用 POI 的空间特性，搜索效率受到一定限制4。针对以上问题，本文提出一种基于 GeoHash 的沿途 POI 搜索方法，采用道路上逐节点步长递进方式，提取 POI 集合中与其 GeoHash 值匹配的 POI 数据，再通过计算与道路的欧氏距离来选择符合条件的 POI，达到精确匹配的目的。本方法步长可动态灵活适配，POI 数据只需要预先计算 GeoHash 索引，就能方便、灵活地更新。1基于 GeoHash 的沿途 POI 搜索方法1 1GeoHashGeoHash 是由 Gustavo Niemeyer 发明的一种对地理区域进行编码的方法5，它将地理坐标区域映射为一维字符串。每个字符串表示一个特定的网格，在该网格范围内的所有坐标都共用这个字符串，字符串越长，精度越高，对应的网格范围越小。GeoHash 用一个字符串表示经度和纬度坐标，能够表示任意精度的地理位置(只要编码长度足够长)，其编码前缀匹配的越长，地理位置越邻近。GeoHash 是具有层级结构的地理空间位置，将地理空间位置用网格划分，同一网格地理编码相同，GeoHash 编码示例如图 1 所示。图 1(a)为某一区域的 5 位长度的 GeoHash 网格和编码;图 1(b)为图 1(a)中 wtw3e 网格区域的子级 GeoHash编码，其编码长度为 6 位，两者编码前 5 位完全相同。图 1GeoHash 编码示例Fig 1GeoHash coding example当采用 GeoHash 方法对地理区域进行编码时，将一个经纬度坐标转换成一个 GeoHash 编码字符串的步骤:1)将纬度范围(90，90)分为区间(90，0)和区间(0，90)，将经度范围(180，180)分为区间(180，0)和区间(0，180)。计算目标经度落在哪个区间，落在(90，0)区间取0，落在(0，90)区间则取1;计算目标纬度落哪个区间，落在(180，0)区间取0，落在(0，180)区间则取1。2)将得到的区间按照 1)继续细化，得到下一位二进制编码，直到编码长度达到精度需求。编码长度与所表示的精度关系见表 1。3)依据“偶数位放经度，奇数位放纬度”的规则，将得到的二进制编码组合，得到一个新的二进制字符串，将该二进制字符串按照从前往后，每 5 位换算成十进制数字，最后不足 5 位的用 0 补齐。4)根据 base32 的对照表，将二进制字符串翻译成 GeoHash 编码，即得到与地理坐标对应的目标GeoHash 字符串。表 1编码长度与表示精度的关系Tab 1elation of coding length and accuracy编码长度经度位数纬度位数经度误差/纬度误差/距离误差/km513120 0220 0222 4615150 005 50 002 70 61718170 000 680 000 680 076GeoHash 编码后的 POI 在空间位置分布上，可以按照不同的网格进行存储和管理。把编码相同的POI 集合统一存储，以便检索时一次加载出具有相同编码的 POI。1 2沿途 GeoHash 集合计算对于某一路线，若要搜索其沿途的 POI，只需计72测 绘 标 准 化第 39 卷算该路线所覆盖的 GeoHash 编码的网格集合。集合中出现相同编码时只保留一份。计算方法和步骤:1)计算开始节点的 GeoHash 编码，并计算与本编码网格相邻的 8 个网格的编码，放入沿途集合。2)计算后继节点的欧氏距离。若该距离大于表示精度，按表示精度计算下一点的地理坐标，并将其作为本节点的后继节点，对该坐标编码，并计算本编码网格相邻的 8 个网格的编码，放入沿途集合;若该距离小于表示精度，计算本编码网格相邻的 8 个网格的编码，放入沿途集合。3)判断本节点是否为尾节点。若是则结束计算;若不是则重复步骤 2)。计算沿途集合的流程如图 2 所示。图 2计算沿途哈希集合流程Fig 2Process of computing GeoHash setsalong a route1 3基于沿途集合的 POI 搜索在存储介质中加载与得到的沿途集合具有相同编码的 POI 集合，根据具有相同 GeoHash 编码的POI 在同一个区域中，可以一次加载本区域的所有POI，有效避免了复杂的空间计算，最后再计算 POI到该路线的几何距离，小于需求所定义距离集合便为目标结果集。2实验与分析2 1实验数据本文实验所用地图数据为四维图新 2017 年第二季度电子地图，包括商场、酒店、餐馆和商店等全部类型的 POI 数据，共有 22 976 089 个 POI。在实验区选择 19 672 km 的路线(见图 3)。所选路线途经城市主干道，沿途分布大量商铺、酒店和宾馆等，适合开展沿途 POI 检索研究。本文实验搜索在150 m以内的 POI，采用的 GeoHash 编码长度为7，其精度约为 76 m。图 3路线覆盖的 GeoHash 网格与邻接矩形Fig 3GeoHash grids and adjacency gridscovered by the route2 2实验分析2 2 1POI 数据集合构建对于本文的实验路线，分 3 个步骤计算其 Geo-Hash 集合。1)计算路线覆盖的 GeoHash 网格。首先，计算起点的 GeoHash 编码;其次，沿路线方向按步长前进，步长的大小由 GeoHash 的编码长度决定，本文采用的编码长度为 7 位，其精度为 76 m，因此本文的步长也为 76 m;最后，计算前进后路线上点的 Geo-Hash 编码，接着再按本步长前进，直到到达路线的终点。线路覆盖的 GeoHash 网格如图 3 所示。2)计算覆盖 GeoHash 网格的邻接网格。由于路线上的点可能位于网格的边缘区域，若只取路线覆盖的区域，会出现虽然 POI 距离路线较近但却不在覆盖区域内的情况。针对此情况，只需要计算出每个覆盖网格的上、下、左、右、左上、左下、右上、右下 8 个邻接网格，最后查询邻接网格区域的 POI 数据即可。如图 3 所示，线路在其覆盖网格 A、B、C 的边缘区域，邻接矩形 a、b、c 即为所求。3)查询覆盖网格和邻接网格内的 POI 集合。如图 4 所示，查询 POI 的 GeoHash 编码为覆盖网格和邻