1.一种基于Trie的空间关键词查询方法,其特征在于:包括:数据预处理步骤,将数据集D中所有位置点编码成长度为n的字符串geoStr,根据字符串geoStr后缀ssuf按字典序对数据集D中的每行数据排序并生成编号id,每一行数据称为一条记录r,则由一至多行记录r组成的数据集称为记录集R;其中ssuf指字符串geoStr的后n‑m位字符,m≤n,m表示字符串geoStr前缀部分的位数;
空间关键词索引建立步骤,对字符串前缀spre构建Trie,Trie的叶节点指向根据该域内关键词构建的倒排索引,倒排索引的列表元素为关键词及与其相对应的id列表,得到空间关键词索引结构;其中,该域指从根节点到叶节点所构成的geoStr前缀sprei,sprei指第i个字符串geoStr的前m位字符,spre指字符串geoStr的前m位字符;
空间关键词查询步骤,检索空间关键词索引结构,获取满足查询条件的id,经过滤得到id候选集,并对候选集验证返回满足空间查询条件的位置点;
所述空间关键词索引建立步骤,具体为:
步骤210:对Rspre构建Trie索引结构,每个spre可映射为Trie中一条从根到叶节点的路径,叶节点指向根据该域内关键词构建的倒排索引;其中,Rspre表示R中所有spre,该域指从根节点到叶节点所构成的前缀sprei,i表示Rspre中第i个字符串;
步骤220:对Ritems中每个独立元素item,构建一个由包含item的rpart.id组成的倒排列表;其中,rpart表示R中r.geoStr的前m位等于sprei的r.id、r.items,r.geoStr表示r的geoStr,r.id表示r的id,r.items表示r的关键词集,Rpart表示由一至多行rpart组成的数据集,Ritems表示Rpart中全部关键词,rpart.id表示rpart的id;
步骤230:对Rsuf构建geoStr后缀ssuf与id的映射表;其中,Rsuf表示R中所有ssuf。
2.根据权利要求1所述的基于Trie的空间关键词查询方法,其特征在于:所述数据预处理步骤,具体包括如下步骤:
步骤110:给定一个由一系列位置点、关键词集构成的数据集D,通过geohash空间编码方法将数据集D中的位置点编码成长度为n的字符串geoStr;其中,位置点由纬度、经度数据构成;其中geoStr即geohash编码,表示geohash精度表中n对应的范围区域,步骤120:将每一个geoStr分为m位前缀部分spre和n‑m位后缀部分ssuf,根据ssuf按字典序对数据集D中每行数据排序并编号id,每一行数据称为一条记录r,则由一至多行记录r组成的数据集称为记录集R;其中,R中每行数据r由id、纬度lat、经度lon、字符串geoStr、关键词集items组成,items至少包含一个关键词item。
3.根据权利要求1所述的基于Trie的空间关键词查询方法,其特征在于:所述空间关键词查询步骤,具体包括如下步骤:
步骤310:给定查询位置点q、查询距离范围d、查询关键词集qitems,根据geohash精度表选定与d相对应的geohash编码长度p,通过geohash空间编码方法将位置点q编码为p位长度的字符串qs,获取字符串qs周围8个区域的geohash编码,并将字符串qs及其周围8个区域的geohash编码分别作为查询域,共9个查询域;其中,p对应的距离误差不小于d且为最小值;
qitems至少由一个关键词item构成;
步骤320:检索空间关键词索引结构返回满足查询条件的id;其中,查询条件指查询域内包含全部qitems的id;
步骤330:根据查询位置点q和查询距离范围d分别确定纬度范围与经度范围,之后按经纬度范围对与步骤320返回的id相对应的位置点进行筛选,最终得到id候选集;
步骤340:计算候选集中id对应的位置点到q的距离dq:若dq≤d,则返回该位置点,否则,不返回。
4.根据权利要求2所述的基于Trie的空间关键词查询方法,其特征在于:所述步骤110,包括下列步骤111、112:
步骤111:根据geohash精度表确定geohash编码长度n;
步骤112:通过geohash空间编码方法将所有位置点编码成长度为n的字符串。
5.根据权利要求2或3所述的基于Trie的空间关键词查询方法,其特征在于:通过geohash空间编码方法将位置点编码成字符串,具体为:首先,将经纬度范围看作二维平面坐标系;然后,采用二分法对经度/纬度进行划分,根据位置点经度/纬度在划分结果中的位置分别赋值0或1,直到划分次数满足对应的经/纬度位串的位数;之后,通过位交错方法合并经度位串与纬度位串;最后,通过Base32编码将经纬度位串编码为相应长度的字符串。
6.根据权利要求3所述的基于Trie的空间关键词查询方法,其特征在于:所述步骤310中,获取qs周围8个区域的geohash编码的方法:根据qs的经纬度位串,东方向的区域编码:经度位串不变,纬度位串加1,通过位交错方法得到该区域的经纬度位串;西方向的区域编码:经度位串不变,纬度位串减1,通过位交错方法得到该区域的经纬度位串;南方向的区域编码:纬度位串不变,经度位串减1,通过位交错方法得到该区域的经纬度位串;北方向的区域编码:纬度位串不变,经度位串加1,通过位交错方法得到该区域的经纬度位串;东北方向的区域编码,经纬度位串均加1,通过位交错方法得到该区域的经纬度位串;西南方向的区域编码,经纬度位串减1,通过位交错方法得到该区域的经纬度位串;东南方向的区域编码:纬度位串加1,经度位串减1,通过位交错方法得到该区域的经纬度位串;西北方向的区域编码:纬度位串减1,经度位串加1,通过位交错方法得到该区域的经纬度位串;之后,通过Base32编码将以上8个位串进行编码即可获得qs周围8个区域的geohash编码。
7.根据权利要求3所述的基于Trie的空间关键词查询方法,其特征在于:所述步骤320具体为:
步骤321:若d>d1,根据geohash编码检索Trie选取待检索的倒排列表;反之,若d≤d1,根据geohash编码前m位检索Trie选取待检索的倒排列表;
步骤322:若d>d1,检索步骤321选取的倒排列表,分别获取包含查询关键词的id列表,并求交集,即为该查询域内满足查询条件的id;反之,若d≤d1,检索步骤321选取的倒排列表,分别获取包含查询关键词的id列表,求交集得到集合Sid,之后检索映射表,返回满足匹配条件的id列表,与Sid求交集,即为该查询域内满足查询条件的id;其中,匹配条件指SufStr等于geohash编码末尾p‑m位,SufStr表示映射表中后缀ssuf的前p‑m位;
据上述方法分别获取每个查询域内满足查询条件的id,之后求并集,即为9个查询域内满足查询条件的id。
8.根据权利要求3所述的基于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)。
9.一种采用权利要求1所述方法的基于Trie的空间关键词查询装置,其特征在于:包括:
数据预处理装置,用于将数据集D中所有位置点编码成长度为n的字符串geoStr,根据字符串geoStr后缀ssuf按字典序对数据集D中的每行数据排序并生成编号id,每一行数据称为一条记录r,则由一至多行记录r组成的数据集称为记录集R;其中ssuf指字符串geoStr的后n‑m位字符,m≤n,m表示字符串geoStr前缀部分的位数;
空间关键词索引建立装置,用于对字符串前缀spre构建Trie,Trie的叶节点指向根据该域内关键词构建的倒排索引,倒排索引的列表元素为关键词及与其相对应的id列表,得到空间关键词索引结构;其中,该域指从根节点到叶节点所构成的geoStr前缀sprei,sprei指第i个字符串geoStr的前m位字符,spre指字符串geoStr的前m位字符;
空间关键词查询装置,用于检索空间关键词索引结构,获取满足查询条件的id,经过滤得到id候选集,并对候选集验证返回满足空间查询条件的位置点。