BTreeU-Topk:基于二叉树的不确定数据上的Top-k查询算法

应用需求的发展衍生各种查询类型,Top-k查询是交互环境下一种重要查询类型.由于数据的不确定性,传统数据上的Top-k查询技术和方法不能直接应用于不确定数据查询.在已有不确定数据上Top-k查询算法的基础上,提出基于二叉树的不确定数据上Top-k查询算法BTreeU-Topk;为了提高算法执行效率,对二叉树进行修剪操作进而提出BTreeOPTU-Topk和BTreePU-Topk算法.实验结果表明,BTreeU-Topk,BTreeOPTU-Topk以及BTreePU-Topk算法在不同数据分布以及k值增长时均优于现有算法.     

基于Bloom滤波器的对等网多关键字检索

现有基于Bloom滤波器（BF）的对等网(P2P)检索,由于索引表的不断增长且不能确定数据量的上限,存在两个问题:一是难以确定BF向量长度;二是不能高效处理P2P多关键字Top-k查询。提出了一种基于关键词频率进行分块的分块Dynamic Bloom Filter（BDBF）以解决上述问题;并给出了相应的P2P多关键字Top-k查询模型,即当节点传送BF时先传送高频DBF,如不能满足Top-k查询则继续传送次高频的BF。实验分析发现,该结构更能适应数据量的连续增长,降低网络传输流量,并能高效处理多关键字检索中的Top-k查询问题。     

模糊粗糙集在科技文档检索中的应用研究

关于提高文献的检索效率,在科技文献检索过程中,传统的基于关键词匹配的检索方法缺乏对知识的理解和处理,只能检索出包含关键词的文献,而不能检索出与关键词语义相似的文献,因而检索结果在查全率和查准率都无法满足检索者的要求.将模糊粗糙集理论引入信息检索当中,对信息检索模型的缺陷进行了改进.首先用传统的互信息函数计算标引词之间的语义关联权重,构建出模糊近似空间;然后用TF - IDF方法获得文档的模糊向量表示,在计算标引词重要度权重时,不但考虑了标引词出现的频度,还考虑位置因素,查询的模糊向量表示完全由用户的兴趣确定;最后用模糊近似空间对关键词进行概念扩展,挖掘出相似概念类,计算文档和查询模糊表示的上、下近似集,文档和查询的匹配不再是关键词匹配,而是利用布尔逻辑的合取、析取公式对上、下近似集进行模糊匹配,并返回按相似度值排序的检索结果.仿真测试表明,方法能提高科技文档检索的性能,能对科技文献进行概念意义上的检索.     

基于LBS的兴趣点查询与更新机制研究

本文对兴趣点(Point of Interest,POI)数据在位置服务(Location Based Service,LBS)行业的应用现状进行了分析,指出POI数据更新中存在的问题.借鉴一些地图社区的自由共享理念,本文提出了一种用户参与的POI更新模式.为了验证这一模式,本文构建了一个基本的LBS平台,实现了基于LBS的POI查询与数据更新的原型系统.详细的论述了系统的功能模块、业务流程和一些技术细节.系统运行结果表明这一模式是可行和有效的.     

保护位置隐私和查询内容隐私的路网K近邻查询方法

位置隐私和查询内容隐私是LBS兴趣点（point of interest,简称POI）查询服务中需要保护的两个重要内容,同时,在路网连续查询过程中,位置频繁变化会给LBS服务器带来巨大的查询处理负担,如何在保护用户隐私的同时,高效地获取精确查询结果,是目前研究的难题.以私有信息检索中除用户自身外其他实体均不可信的思想为基本假设,基于Paillier密码系统的同态特性,提出了无需用户提供真实位置及查询内容的K近邻兴趣点查询方法,实现了对用户位置、查询内容隐私的保护及兴趣点的精确检索;同时,以路网顶点为生成元组织兴趣点分布信息,进一步解决了高强度密码方案在路网连续查询中因用户位置变化频繁导致的实用效率低的问题,减少了用户的查询次数,并能确保查询结果的准确性.最后从准确性、安全性及查询效率方面对本方法进行了分析,并通过仿真实验验证了理论分析结果的正确性.     

基于高维空间的在线高效子空间Skyline算法——CSky

Skyline计算是要发现数据集中不被其他点支配的所有点的集合.近来,它在实时在线服务方面的良好应用前景,使其成为数据库研究领域的一个热点.实际应用中,用户通常期望快速、渐进地返回Skyline计算结果,因此文中主要讨论了高维空间子空间Skyline渐进查询问题.据我们所知,现有的Skyline计算方法都不能直接或者通过简单修改来高效解决该种查询问题.BNL(Blocked Nested Loop)算法是一个可用来进行子空间Skyline计算的算法,但是,该方法低效且非渐进.基于此,文中提出了在线高效子空间Skyline算法--CSky(Count the Skyline).该算法充分利用了一个新颖数据结构--InvertS的特征,即通过对目标数据集进行排序,存放最可能为Skyline点的数据于算法优先扫描的位置,这使得CSky算法能高效计算出任意子空间上的Skyline;同时,CSky每次计算子空间Skyline查询时,至多访问一遍数据库;再有,算法扫描一个点时,只需和当前已发现的Skyline点进行比较即能判断该点是否为Skyline点,保证了算法的渐进性.这样,相比BNL,CSky大大减少了计算开销,具有其他基于索引的Skyline算法计算Skyline时的高效,且这种高效适用于所有子空间.理论分析和实验表明,在解决高维空间子空间Skyline查询问题方面,CSky性能大大优于BNL.     

MapReduce框架下的不确定数据Top-k查询计算

Top-k查询是不确定性数据管理中普遍采用的一种技术.基于参数化排名函数的Top-k查询语义是近年来提出的各种查询语义的统一.文中针对海量不确定数据,提出一种基于MapReduce框架的Top-k计算的有效方法.通过分析基于参数化排名函数的不确定数据Top-k查询语义,设计一种获得未计算元组的排名函数值上界的算法,避免计算所有元组的排名函数值,解决Top-k计算中的剪枝问题.在MapReduce计算模型中提出两种不同的策略来实现该算法.文中针对单机环境和Hadoop分布式计算平台进行两组不同的对比实验.实验表明在处理海量不确定数据时,该算法在计算时间上有较高的性能提升.     

面向不确定移动对象的连续K近邻查询算法*

近年来,位置服务等领域急需解决的一个难点问题是不确定移动对象连续K近邻查询.基于此情况,文中提出高效的面向不确定移动对象的连续K近邻查询算法.首先提出2种预测移动对象可能区域算法MaxMin与Rate,利用最近一段时间窗口内的位置采样、速度和方向预测移动对象在查询时刻到未来I区间可能的位置区域.同时使用最小距离与最大距离区间描述移动对象到查询对象的距离.然后采用优化的基于模糊可能度判定的排序方法查找查询对象的K近邻.最后在真实和合成的大规模移动对象数据集上验证文中方法的有效性.     

面向时间依赖路网的空间索引方法

在兴趣点(POI)呈稀疏分布时,现有时间依赖路网中的k近邻查询方法效率较低,且无法高效支持多类型的POI查询。为此,建立基于POI分布的空间索引结构TDG。根据路径权值上、下界对预计算路径进行剪枝优化,在此基础上,提出一种索引更新策略与基于TDG的k近邻查询算法。实验结果表明,与启发式查询算法相比,该算法的扩展节点数量平均减少87.5%,查询响应时间平均缩短33%～66%。     

基于E2LSH的轨迹KNN查询算法

目前海量时空轨迹数据近邻查询算法中存在计算时间复杂度较高的问题,因此提出了一种结合领域POI数据和E2LSH算法的轨迹KNN查询算法。首先利用GeoHash技术对地理空间进行编码,然后结合POI数据实现向量空间的初步降维,进而根据停留时间构建每条轨迹的向量,采用局部敏感哈希函数运算结果建立轨迹索引,最后对查询返回的相似轨迹集合分别进行距离计算,经过排序得到距离最近的K个查询结果。对于增量的轨迹数据,利用E2LSH算法计算哈希值,直接添加轨迹索引,从而避免了复杂的计算过程以及对现有轨迹索引的影响。基于合成数据及真实数据集的实验结果表明,该方法在海量时空轨迹数据的近邻查询中,虽然牺牲了一定的准确率,但有效提升了算法效率,并能够高效简便地处理增量的时空轨迹数据。