基于数据广播的空间关键字查询处理

为了解决无线广播环境下空间关键字查询的问题,研究广播环境下空间关键字k近邻查询处理(BkSKQ),设计了一种结合kd树、倒排位图和(1,m)索引机制的空间关键字索引(ISKW)结构,以有效地组织对象的关键字信息、位置信息以及索引信息.该索引结构为客户的查询处理提供有效的指导,使得他们尽可能只下载查询处理所必须的数据信息.在ISKW索引结构的基础上,提出了BkSKQ查询处理算法.最后,通过模拟实验验证了提出的索引结构和算法的性能,实验结果表明所提出方法在访问时间和调谐时间上明显优于基于IR树的方法(BIRM).     

空间多样化约束下的移动k近邻查询

考虑为移动中的查询对象连续返回k个距离近并且满足空间多样化约束的对象，提出了空间多样化约束下的移动k近邻(SDC-MkNN)查询.在此，满足空间多样化约束代表对象之间的相互距离大于距离阈值.为了高效处理SDC-MkNN查询问题，提出了两种基于安全区域技术的算法.算法均通过减少重新计算查询结果的次数来提高查询效率.其中一种为精确算法EA，可连续返回精确的查询结果；另一种为近似算法ρAA，可连续返回具有近似率保障的近似查询结果.采用真实数据集验证了所提出算法的有效性.     

路网移动对象空间关键字连续Top-k查询

为了克服现有空间关键字查询方法大多只适用于欧氏空间查询处理的局限性,提出了一种渐增监控查询处理方法(CMA),以高效处理路网中移动对象空间关键字连续top-k查询问题(CMkSK).该方法用一棵组合扩展树CEtree来界定查询的监控范围,通过识别、处理监控范围内对查询结果有影响的查询点和移动对象的位置更新对相应的CEtree进行修正,以保证查询结果的持续有效性.所提出的方法考虑了现实生活中对象的可移动性,可以处理查询点和数据对象在路网中自由移动的情形.最后,通过模拟实验证明了所提出算法较参照算法的性能提高约1.1倍.     

传感器网络空间关键字近似Top-k查询算法

提出了一种基于节点剪枝的Top-k査询算法.定义集合支配区域与剪枝规则,根据用户查询位置的变动,按照给定的剪切规则,对传感器网络节点进行剪枝处理,将符合规则的节点预先筛除,运用统计学抽样理论,设计了空间关键字近似Top-k查询算法.在2个真实数据集上进行验证.实验结果表明,该算法能够满足传感器网络环境中用户的需求,并且相比于边界距离增量算法(IBD)与基于改进的MW-Voronoi区域的空间关键字查询算法(MSK-uvr),其网络通信开销较低.     

基于MapReduce的并行加权k近邻与离群检测

利用MapReduce编程模型,提出一种并行的加权k近邻与离群检测方法 WKNNOM-MR.该算法首先对输入数据随机均匀采样,在样本数据集中采用信息熵计算各个属性的权值;然后在集群中的数据节点上对输入数据进行加权,并将其映射到Z-order空间填充曲线,给出了一种基于Z-order的加权k近邻查询方法;根据每个对象与其加权k近邻之间的距离计算离群因子,在兼顾最小距离与平均距离的基础上,给出离群点检测算法;最后在具有5个节点的Hadoop集群上实现该算法,并采用人工合成数据集、UCI标准数据集进行实验,结果验证了该算法的有效性、可扩展性和可伸缩性。     

面向组近邻的Top-k空间偏好查询

空间偏好查询是当前空间查询研究中的一类热点问题,而现有的空间偏好查询不能有效支持面向组用户的位置服务应用.为此,提出一类新型空间偏好查询——面向组近邻的Top-k空间偏好查询(Topk spatial preference query for group nearest neighbor).该查询通过查找特征对象的λ子集组近邻最终为用户返回评分值最高的前k个λ子集.为了高效执行这一查询,给出了两种查询算法:TSPQ-G及TSPQ-G*.其中TSPQ-G*在TSPQ-G的基础上,通过空间剪枝及高效的特征对象索引树遍历策略大幅减少I/O代价,进而有效提高了该查询的执行效率.实验采用多个数据集验证了所提算法在不同参数设置下的有效性.     

空间网络数据库关键字查询的高效空中索引

研究无线广播环境下空间网络数据库关键字查询问题,提出一种包含路网加权四叉树、各关键字四叉树和路网距离矩阵的空中索引结构(KSSN).讨论了kNN查询处理问题,提出了高效的查询处理算法.所提出的算法能综合利用路网距离信息和关键字信息高效地消减不存在查询结果对象的路网空间,提高查询处理的效率.KSSN索引结构可推广至其他类型的查询,比如范围查询、Rank查询.在一个真实路网上进行了仿真实验,验证了基于KSSN索引结构的查询处理算法的性能.实验结果表明:所提出算法的访问时间和调谐时间分别为参照的IRRDA算法的25.13%和12.31%.     

路网中速度不确定移动对象的K范围近邻查询方法

K范围近邻查询是指查找给定范围区域内所有点的近邻对象。现有工作主要考虑对象固定不动情况下的K范围近邻查询,实际上对象不但可能移动,而且由于外界环境和自身情况等不确定性因素的影响,移动对象运动速度的不确定性也是客观存在的。基于此,本文考虑了速度不确定移动对象的K范围近邻查询,提出路网中速度不确定的移动对象的K范围近邻查询的处理算法,利用共享查询的思想减少了冗余查询的代价,最后,通过实验验证了所提算法的有效性。     

空间关键字任务匹配算法

互联网的发展带动了电商等应用的普及,产生了大量具有临时匹配性质的服务。这些服务需要考虑任务的类型与人员具备技能的匹配,同时最小化匹配对象间的路程开销。针对以上实际需求,提出了空间关键字任务匹配问题,给定具有空间位置及关键字的任务集与成员集,在所有任务均可完成的前提下,使所有匹配的任务与成员的距离之和最小。所提出的问题考虑了任务由不同的关键字表示,由于任务和成员数量的海量性及关键字的多样性使得高效求解高质量的匹配结果成为挑战。该文提出了k近邻增量优化策略,引入关键字设计了k近邻空间关键字任务匹配算法,提高了任务匹配质量;提出了基于空间划分的分组优化匹配算法,以适应海量数据的任务匹配情况。针对真实数据集进行了充分测试,验证了算法的有效性。     

受约束的设施最优选址研究

基于双色子反近邻的查询在空间数据库领域很有应用价值.在实际中,设施会要受到自身服务能力的限制.当需求快速增长时,那些处于服务密集区域的设施很可能不堪重负.研究了一种与双色子反近邻集合相关的查询,旨在找到最具潜力的候选位置来最大程度的提高整个区域的服务质量.使用剪枝技术和空间索引技术,提出了时间复杂度为O(nlogn)的算法快速有效的完成这种查询.为了评价算法的效率,我们在真实数据集和合成数据集上做了实验,结果显示提出的算法十分优于基本算法.