空间文本数据流上连续查询评估技术综述

空间文本数据流上连续查询(CQST)在基于位置的服务中应用广泛,其在不断更新的数据流上,持续监控满足空间和文本约束的结果。为了将数据流中的对象尽快匹配给CQST,在CQST上构建高效的过滤技术是关键。CQST查询评估方法——为查询选取恰当的空间文本索引,构建高效的过滤策略提升索引的空间文本过滤性能,为数据流中到来的对象过滤大量不相关的查询,避免高昂的验证代价,提高对象与查询的匹配效率。现有工作利用有限的空间索引和文本索引构建空间文本混合索引,其评估性能差异取决于采用的过滤策略,即提升索引过滤性能的技术。以现有CQST查询优化技术为主要研究对象,对评估CQST的流程以及存在的挑战进行了介绍;对在中央服务器及分布式集群上评估CQST的空间过滤技术及文本过滤技术进行综述比较,包含采用的空间文本混合索引,为提升索引过滤性能采用的空间过滤策略、文本过滤策略及二者的结合机制,分析总结其利弊,讨论评估CQST未来可能的研究方向。     

一种基于HBase的高效空间关键字查询策略

随着移动定位技术的发展以及智能手机的普及,互联网中空间文本对象的数量正在急速增长,如何在规模庞大且动态增长的空间文本对象中进行高效的空间关键字查询成为了许多空间关键字查询应用所关心的问题.现有的方法通常利用基于R树和倒排索引的混合索引结构来处理空间关键字查询,然而,面对数量巨大而且不断增长的空间文本对象,这些方法往往难以为空间关键字查询的高效性和扩展性提供支持.对此,提出一种基于HBase的空间文本数据索引结构SK-HBase.SK-HBase以HBase作为数据存储,通过有效的数据分配策略对空间文本对象的空间信息和文本信息同时进行索引.在SK-HBase的基础上,本文提出了两种空间关键字查询算法,以保证不同空间范围下的空间关键字查询的高效性和可扩展性.实验证明,我们的方法能够在海量数据下进行高效的空间关键字查询并具有良好的可扩展性.     

RB树:一种支持空间近似关键字查询的外存索引

空间近似关键字查询包含一个空间条件和一组关键字相似性条件,这种查询在空间数据库中返回同时满足以下条件的对象:1)对象的位置信息满足查询中的空间条件;2)对于查询中的任何一个关键字,对象中至少包含一个关键字与其相似度大于给定阈值.随着当前数据的爆炸性增长,空间数据库无法完整地存放在内存中,因此空间数据库需要支持空间近似关键字查询的外存索引.目前,还没有在外存中支持精确的空间近似关键字查询的索引结构.设计了一种新型的外存索引RB树,在外存中支持精确的空间近似关键字查询.RB树支持的空间近似关键字查询包括多种空间条件,如范围查询、NN查询,同时支持多种关键字相似性度量,包括编辑距离、规范化编辑距离等.通过真实数据中的性能测试验证了RB树的效率.     

已知时间的空间文本skyline查询

现有的空间文本skyline查询忽略了地理空间对象的时间信息,考虑到时间信息对应用的重要性,将时间信息应用到空间文本skyline查询中,提出了一种新的查询,即已知时间的空间文本skyline查询（Time-aware Spatial-Textual Skyline Query,TSTSQ）。TSTSQ中skyline对象的筛选依赖于三个条件：文本相关性、空间邻近和有效时间。分别设计了对象的空间文本相关性和时间文本相关性的计算函数,构建时空信息和文本信息的对象索引结构TKR-Tree,通过构造高效的裁剪策略实现了TSTSQ的查询算法。通过实验数据的分析和对比,验证了TSTSQ查询的有效性。     

基于MIR树的空间查询验证方法

在数据外包服务中,空间多项式函数查询能确保返回用户查询信息的真实性,因而具有较高的应用价值。为解决MIR树中倒排索引文件通信代价过高的问题,采用位图替代倒排索引文件,构造一种支持查询验证的数据索引结构——MRH树,在此基础上构造验证对象生成算法验证查询结果。实验结果表明,在保证查询结果可靠、正确和完整的前提下,相较于MIR树,MRH树能显著地降低通信开销和计算时间。     

基于最短路径的道路网络k近邻查询处理

针对基于空间道路网络的k近部查询处理,提出了分布式移动对象更新策略以有效减少服务器计算代价,利用基于内存的空间道路网络部接矩阵、最短路径矩阵结构和移动对象哈希表索引分别对道路网络无向图与移动对象进行存储管理。提出了基于最短路径度量的网络扩展搜索(SPNE)算法,以通过裁剪网络搜索空间来减少k近部查询搜索代价。实验表明,SPNE算法的性能优于传统的NE和MKNN等k近邻查询处理算法。     

一种基于HBase的空间关键字查询算法

针对传统关系数据库处理海量空间文本数据的不足,基于HBase数据库提出了一种结合Geohash编码与分词技术的空间文本索引方案,并基于该空间文本索引提出了一种多边形区域内的空间关键字查询算法。通过与传统经纬度索引方案的实验比较,验证了算法的高效性和可扩展性。     

基于位置-文本关系的空间对象top-k查询与排序方法

针对普通的空间关键字查询通常会导致多查询结果的问题。本文提出了一种基于空间对象位置-文本相关度的top- k 查询与排序方法,用于获取与给定空间关键字查询在文本上相关且位置上相近的典型空间对象。该方法分为离线处理和在线查询处理2个阶段。在离线阶段,根据空间对象之间的位置相近性和文本相似性,度量任意一对空间对象之间的位置-文本关系紧密度。在此基础上,提出了基于概率密度的代表性空间对象选取算法,根据空间对象之间的位置-文本关系为每个代表性空间对象构建相应的空间对象序列。在线查询处理阶段,对于一个给定的空间关键字查询,利用Cosine相似度评估方法计算查询条件与代表性空间对象之间的相关度,然后使用阈值算法（threshold algorithm,TA）在预先创建的空间对象序列上快速选出top- k 个满足查询需求的典型空间对象。实验结果表明:提出的空间对象top- k 查询与排序方法能够有效地满足用户查询需求,并且具有较高的准确性、典型性和执行效率。     

基于iMeMex数据模型的数据空间索引方法研究

目前,个人和组织的信息呈现急剧增长趋势,且非结构化数据所占比重在不断增加,这些属于某个主体的海量、分布、异构和共存的数据构成了一个异构数据空间,如何为用户提供高效、便捷和多样化的搜索查询服务是数据空间面临的巨大挑战,为数据空间中异构数据构建高效的索引方法是解决这一问题的基础。对iMeMex数据模型的特点和数据空间中查询方法进行了分析,在此基础上通过扩展倒排列表方法,提出了一种基于iMeMex数据模型的索引方法,来提高对数据空间中异构数据的搜索查询效率。新的索引方法通过扩展倒排列表的关键字列和链表节点信息索引资源视图,来支持和提高关键字查询、谓词查询和路径查询的处理效率。实验结果表明,该索引方法能够有效、可行地解决数据空间中异构数据索引和查询效率问题。     

ISU -Tree:一种支持概率k近邻查询的不确定高维索引

文中提出一种支持概率k近邻查询的不确定高维索引结构--ISU-Tree.在高维空间,首先对n个不确定数据对象进行k平均聚类,然后分别对每个不确定超球进行初始"切片",并对其进行多特征编码得到对应的统一化索引键值,并且用B+树建立索引.这样,高维空间的概率查询就转变成对一维空间的启发式的范围查询及求精运算.理论及实验分析表明ISU-Tree索引能更有效地缩小搜索空间,减少积分计算的代价.在查询效率方面要明显优于其它的索引方法,尤其适合海量高维不确定数据的概率查询.