基于重用技术的相互Skyline查询算法

提出了一种新的Skyline查询,即相互Skyline查询(MSQ).给定一个对象集合P和一个查询对象q,MSQ返回一个对象集合,它的每个对象既在q的动态Skyline中,同时也在q的可逆Skyline中.基于传统的R-tree索引、重用堆信息技术以及启发式的修剪策略,显著降低了I/O成本,改进了基于BBS算法和BBRS算法实现的MSQ算法.几个真实数据集的实验表明提出的算法有效而高效,比一般MSQ算法快几个数量级.     

MapReduce模型下基于R树索引的Skyline查询算法

提出一种MapReduce并行计算模型下基于R树索引的Skyline查询算法, 解决了海量空间数据集下执行Skyline查询效率低的问题. 通过建立R树索引实现空间数据不同粒度的范围剪枝, 有效降低了分布式Skyline查询需扫描的数据规模, 提高了在MapReduce模型下Skyline查询的执行效率. 在不同数据分布下进行对比实验的结果表明, 该方法比已有算法在执行效率上更具优势.     

聚类金字塔树：一种新的高维空间数据索引方法

提出了一种新的有效的高维空间数据索引方法-聚类金字塔树,它先对不均匀分布数据进行聚类处理,然后对聚类的结果实施金字塔分割和存储,由此建立一种有效的索引结构。文中给出聚类金字塔树的几种查询算法。实验证明：处理不均匀分布数据时,聚类金字塔树无论在页面访问次数,还是在CPU总占时间上都优于金字塔树。     

一种基于QAAR-树的空间索引方法

针对QCR-树聚类个数需事先确定和处理高维空间数据时面临着"维数灾难"的问题,通过自动确定K-means算法的聚类个数和初始聚类中心,来提高聚类质量,并对原始高维空间数据进行近似压缩来减少磁盘读写代价,提高查询效率,提出一种QAAR-树空间索引结构,同时给出QAAR-树的插入、删除和查询算法。实验结果表明,QAAR-树的查询性能优于QCR-树,能够有效地处理海量高维空间数据。     

空间网络数据库中基于M-tree索引的反最近邻查询算法

欧式空间中的反k最近邻查询算法不适用于空间网络环境,故采用任意度量空间中的M-tree索引结构,进行空间网络数据库中的反k最近邻查询处理.首先通过预计算的方法得到网络距离信息,依据此距离信息,对空间网络对象建立M-tree索引结构.然后,给出并证明了M-tree中间结点修剪定理,提出一种适用于空间网络环境的反k最近邻查询算法.最后实验验证了该算法的有效性.     

基于改进NSGA-Ⅲ的文本空间树聚类算法

构建倒排文本空间索引树(IR)分裂聚类多目标模型,对非支配排序遗传算法(NSGA-Ⅲ)的求解过程进行改进,提出一种基于先验初始种群策略的非支配排序遗传算法(PIPS-NSGA-Ⅲ),使其更适应于倒排文本空间对象分裂聚类问题的求解.通过PIPS-NSGA-Ⅲ算法寻求对象最小包围矩形(MBR)之间的重叠与覆盖面积、对象群间平均距离以及语义相似度等目标的最优前端解.通过对比PIPS-NSGA-Ⅲ,NSGA-Ⅱ,NSGA-Ⅲ和SPEA-Ⅱ进化多目标算法,从对象分类时间、效率、查询时间和准确度等多个方面来评估算法的优劣.实验结果表明:PIPS-NSGA-Ⅲ算法对文本空间对象聚类分裂具有较高的效率;相对于简化传统R树(STR树)与R树空间索引结构,基于改进NSGA-Ⅲ文本空间索引的平均查询时间减少24.8%,平均准确度提高3.75%.     

高效的子空间可逆skyline查询算法

提出了一种高效的子空间可逆skyline查询算法RSQS.该算法采用基于分区的B+树对可逆Skyline进行计算,不同于传统的R-tree修剪方法;RSQS利用提出的几种修剪策略,包括相互修剪、预计算、尽早终止搜索等,采用过滤-精炼框架实现,能快速地修剪搜索空间,避免了大部分的I/O操作.实验结果表明:RSQS算法具有极高的修剪能力和很高的效率:在二维子空间中每个对象平均仅需与约1.2个其他对象比较.     

一种高效的移动对象索引

提出了一种基于R-树和聚类算法的高效移动对象索引,这种索引能够有效地回答各种查询,包括范围查询、瞬时查询和最邻近查询。这种索引的新特征是在节点发生分裂时采用另外一种的聚类方法,即k-mealls算法,取代传统的“两路”分裂算法,而采用“多路”分裂算法。通过实验比较,这种新的索引结构在各种条件下性能比其它相关算法优越。     

基于混合聚类算法的动态R-树

针对动态R-树是通过动态插入算法建立起来的, 其节点分裂算法的性能直接影响到R-树的性能和查询效率的问题, 为了使动态R-树适应多维复杂空间数据的要求, 提出一种用于实现R-树节点分裂的混合聚类算法（HCR）, 它建立在普通聚类算法的基础上, 并进行了一系列扩充. 针对空间对象的均匀分布与不均匀分布, HCR算法在实现R-树节点分裂时分别采用不同的聚类准则以提高其聚类效果和查询效率. 此外, 还将HCR算法与其他算法进行对比实验, 结果表明该算法具有较高的查询效率.     

面向推荐系统的多目标决策优化算法

针对推荐系统利用多目标决策技术进行位置信息的查询与推荐时,由于查询者位置的移动和空间障碍物的位置变化导致传统多目标决策技术的查询效率较低的问题,提出了一种基于范围的障碍空间连续Skyline查询算法。首先,根据静态Skyline点的特征对由空间数据对象信息组成的初始数据集进行约减;然后,根据障碍空间中查询者的位置移动的特点构建距离相交模型,利用距离相交模型和数据对象的属性提出了剪枝策略,再根据剪枝策略过滤掉当查询者的位置移动时对查询结果无影响的数据对象,从而精减了冗余数据,得到过滤后的候选数据集;最后,根据数据对象的非空间属性和相互间的支配关系特征得出影响候选数据集的事件,利用影响候选数据集的事件再对候选数据集进行精炼计算,从而减少了冗余计算,查询出当前时刻的结果集。理论研究与实验结果表明：所提算法在查询者位置移动和空间障碍物位置变化时,能提升多目标决策技术的查询效率;相对传统对比算法,在数据集规模、障碍物数量、查询范围增大时,所提查询算法的平均效率提升约13%;针对多维度数据信息的查询,所提查询算法的平均效率提高了约11%。     

PSP：一种高效的偏序域上skyline查询处理方法

为解决偏序域上的skyline查询问题,本文提出一种高效的偏序域上的skyline查询处理方法,来满足人们对查询效率日益增长的需求.首先,为提高偏序域上skyline的查询效率,将倒排索引引入skyline查询,提出一种基于倒排的索引结构.其次,提出基础算法(Basic Partially-ordered Skyline Processing based on inverted index,PSP_B),PSP_B包含两个阶段:第一阶段,能够通过映射将偏序域转化成全序域,并建立倒排索引;第二阶段,通过倒排索引提前找到扫描结束点,得到最终的skyline结果.再次,在PSP_B的基础上,进一步提出优化算法(Improved Partially-ordered Skyline Processing based on inverted index,PSP_I).PSP_I通过先分组再建索引的方法能够进一步提高计算效率.最后,用大量的实验证明本文所提算法的正确性和高效性.     

移动环境中的位置依赖连续轮廓查询

针对移动环境中查询点快速移动时连续、高效输出给定搜索区域数据轮廓的问题,提出一种位置依赖连续轮廓查询算法(LDCS).该算法结合数据流技术,首先使用R树快速更新查询数据,然后利用两次连续计算时搜索区域的重叠性构造被动数据流,并对新增和失效数据分别进行处理,从而连续输出轮廓.由于充分利用了已有结果,LDCS的计算量较传统算法有大幅下降.实验结果表明,LDCS特别适合计算频度要求较高的场合,与基于网格索引的算法相比,时间效率随着数据集规模的增大显著提升.     

基于窗口查询的轮廓查询算法

轮廓查询在涉及多标准决策的空间数据库应用中起着非常重要的作用,轮廓的计算在数据库通信方面受到很大关注,特别是无需访问所有的数据文件就能很快的返回轮廓中的点的算法.本文提出一种基于窗口查询的轮廓查询算法,通过不断变换查询窗口来缩减查询空间,所访问的空间数据点数目大大减少,查询结果有很好的健全性和完整性.     

一种基于路网D树的无线广播环境下路网最近邻查询处理算法

位置相关查询是数据库领域的一个研究热点。重点研究了无线广播环境下路网最近邻查询（NN）处理问题。对一个给定的路网结构及路网上分布的数据对象,构造对应的路网Voronoi图（NVD）,并在NVD图的基础上构建路网D树索引结构。然后,将路网D树索引结构线性化以支持无线广播环境下路网NN查询的处理,并提出了相应的路网NN查询处理算法。模拟实验表明,所提出的算法是有效的。     

Sampling-Based Approximate Skyline Query in Sensor Equipped IoT Networks

The ever increasing requirements of data sensing applications result in the usage of Io T networks. These networks are often used for efficient data transfer. Wireless sensors are incorporated in the Io T networks to reduce the deployment and maintenance costs. Designing an energy efficient data aggregation method for sensor equipped Io T to process skyline query, is one of the most critical problems. In this paper, we propose two approximation algorithms to process the skyline query in wireless sensor networks. These two algorithms are uniform samplingbased approximate skyline query and Bernoulli sampling-based approximate skyline query. Solid theoretical proofs are provided to confirm that the proposed algorithms can yield the required query results. Experiments conducted on actual datasets show that the two proposed algorithms have high performance in terms of energy consumption compared to the simple distributed algorithm.     

一种分布式环境下的skyline查询算法

skyline计算在多标准决策、数据挖掘和数据库可视化等领域具有非常重要的作用.研究了分布式环境下的skyline查询问题.提出通过合并局部skyline集合得到全局skyline集合的思想,在计算全局skyline集合时,先对局部skyline集合进行区域划分和动态编码,然后根据各个区域之间的制约关系进行数据合并.通过实验分析可知,当全局skyline集合的规模较大时,经过区域划分的算法比起直接合并的算法执行效率更好.     

缓存模式下的轮廓查询优化方法

研究在缓存模式下,利用一组预存储的临时轮廓快照集来高效等价重构用户新提交的轮廓查询Q,并提出一种新颖的缓存模式下轮廓查询处理算法(APSQCM)来完成该任务.APSQCM算法由两阶段组成,第一阶段捕获Q与缓存中临时轮廓快照间的内在关联,进而获取能够用来等价重构Q的所有轮廓基;而在第二阶段中,APSQCM算法使用轮廓基来快速产生Q的正确结果集.实验结果表明,APSQCM算法具有有效性和实用性.     

无线传感器网络中基于划分的二维轮廓监控算法

针对传统数据库领域的轮廓查询算法无法直接移植到无线传感器网络领域问题,提出了一种基于划分的二维轮廓监控算法(P2S).P2S算法利用轮廓查询的特点将二维平面进行划分,为每个传感器节点分配一个矩形区域作为过滤器来减少网络中的数据传输,达到降低节点的能量消耗的目的.实验结果表明,P2S算法可以过滤传感器节点的大量不必要的数据,有效地减少了节点向基站发送的消息数量,使得节点有限的电能得到更加合理的利用,从而极大地延长了无线传感器网络的使用寿命.