1.一种基于Trie的范围查询方法,其特征在于:包括:
数据预处理步骤,将数据集中所有位置点编码成长度为n的字符串,根据字符串后缀按字典序对数据集中的位置点排序并编号ID;
空间索引建立步骤,根据排序后的字符串前缀构建Trie空间索引结构;
范围查询步骤,在索引结构上获取查询域内的位置点,经过滤得到候选集,并对候选集验证返回查询范围内的所有位置点。
2.根据权利要求1所述的基于Trie的范围查询方法,其特征在于:所述数据预处理步骤,具体包括如下步骤:步骤110:给定一个由一系列位置点构成的数据集D,通过geohash算法将D中的位置点编码成长度为n的字符串s;其中,位置点由纬度、经度数据构成;
步骤120:将每一个位置点编码的字符串s分为m位前缀部分spre和n-m位后缀部分ssuf,根据字符串后缀按字典序对数据集中的位置点排序并编号,该编号即为对应的位置点ID;
其中,m≤n。
3.根据权利要求1所述的基于Trie的范围查询方法,其特征在于:所述空间索引建立步骤,具体为:步骤210:根据字符串前缀构建Trie索引结构,每个spre可映射为Trie中一条从根到叶节点的路径,那么spre可称为该叶节点的前缀,每个叶节点存储由该节点的前缀对应的ID构成的反向列表。
4.根据权利要求3所述的基于Trie的范围查询方法,其特征在于:所述空间索引建立步骤,还包括步骤220,具体为:步骤220:构建字符串后缀和ID范围的映射表;其中,ID范围指包含字符串后缀的字符串对应ID的起始值至结束值。
5.根据权利要求1所述的基于Trie的范围查询方法,其特征在于:所述范围查询步骤,具体包括如下步骤:步骤310:给定查询位置点q和查询距离范围d,根据geohash精度表选定与d相对应的geohash编码长度p,通过geohash算法将位置点q编码为p位长度的字符串qs,获取字符串qs周围8个区域的geohash编码,并将字符串qs及其周围8个区域作为查询域;其中,p对应的距离误差不小于d且为最小值;
步骤320:若d>d1,通过检索Trie索引结构即可返回9个查询域内的ID;反之,需通过映射表辅助查询方可返回9个查询域内的ID;其中,d1表示geohash精度表中|spre|+1对应的距离;
步骤330:根据查询位置点q和查询距离范围d分别确定纬度范围与经度范围,通过经纬度范围对9个查询域内的ID进行筛选,最终得到候选集;
步骤340:计算候选集中ID对应的位置点到q的距离dq:若dq≤d,则返回该位置点,否则,不返回。
6.根据权利要求2所述的基于Trie的范围查询方法,其特征在于:所述步骤110,包括下列步骤111、112:步骤111:根据geohash精度表确定geohash编码长度n;
步骤112:通过geohash算法将所有位置点编码成长度为n的字符串。
7.根据权利要求2或5所述的基于Trie的范围查询方法,其特征在于:所述通过geohash算法将位置点编码成字符串具体为:首先,将经纬度范围看作二维平面坐标系;然后,采用二分法对经度/纬度进行划分,根据位置点经度/纬度在划分结果中的位置分别赋值0或1,直到划分次数满足对应的经/纬度位串的位数;之后,通过位交错方法合并经度位串与纬度位串;最后,通过Base32编码将经纬度位串编码为相应长度的字符串。
8.根据权利要求5所述的基于Trie的范围查询方法,其特征在于:所述步骤310中,获取qs周围8个区域的geohash编码的方法:根据qs的经纬度位串,东/西方向的区域编码:经度位串不变,纬度位串加/减1,通过位交错方法得到该区域的经纬度位串;南/北方向的区域编码:纬度位串不变,经度位串减/加1,通过位交错方法得到该区域的经纬度位串;东北/西南方向的区域编码,经纬度位串均加/减1,通过位交错方法得到该区域的经纬度位串;东南方向的区域编码:纬度位串加1,经度位串减1,通过位交错方法得到该区域的经纬度位串;西北方向的区域编码:纬度位串减1,经度位串加1,通过位交错方法得到该区域的经纬度位串;之后,通过Base32编码将以上8个位串进行编码即可获得qs周围8个区域的geohash编码。
9.根据权利要求5所述的基于Trie的范围查询方法,其特征在于:所述步骤330中根据查询位置点q和查询距离范围d分别确定纬度范围与经度范围方法如下:纬度的最大值maxLat = lat + range,纬度的最小值minLat = lat - range;经度的最大值 maxLng = lon + lngR,经度的最小值minLng = lon - lngR;其中,lat表示查询位置点q的纬度值,lon 表示查询位置点q的经度值,range =180 / π * d / 6372.797,lngR = range / cos(lat *π/ 180.0)。
10.一种基于Trie的范围查询装置,其特征在于:包括:
数据预处理装置,用于将数据集中所有位置点编码成长度为n的字符串,根据字符串后缀按字典序对数据集中的位置点排序并编号ID;
空间索引建立装置,用于根据排序后的字符串前缀构建Trie空间索引结构,并构建字符串后缀和对应的位置点ID范围的映射表;
范围查询装置,用于在索引结构上获取查询域内的位置点,经过滤得到候选集,并对候选集验证返回查询范围内的所有位置点。