基于MapReduce的预处理高效Skyline算法

现有基于MapReduce的算法不能高效地解决大数据的Skyline查询问题。针对这种情况,提出一种高效的预处理Skyline查询算法MRFS(MapReduce based Filter Skyline),对大数据集进行预处理,提取支配能力较强的小点集组成比较点集,在算法开始前用比较点集对原始数据集进行过滤,排除掉一大部分不能成为Skyline结果集的数据对象;再对过滤后的数据集在Map阶段并行计算出局部Skyline集;最后合并到一个Reduce任务,得到最终的Skyline结果集。在不同数据分布下对该算法进行系统实验,结果表明算法比现有的算法在时间效率上提高了20%~30%。     

分布式环境下的Skyline代表点查询

为了克服Skyline查询的不足即结果集大小无法控制,提出了Skyline代表点查询,返回k个可描述全局Skyline轮廓的Skyline代表点。研究了分布式环境下的Skyline代表点查询,提出了Naive算法和FDRA。Naive算法首先转移每个子节点上满足条件的两个局部代表点,再通过比较传来的局部代表点间的评价函数值大小决定子节点是否需要传送余下的局部点,以实现剪枝非代表点;与之相比,FDRA的改进在于过滤元组的选择,运用反馈方法,将每次动态更新最大评价函数值的点作为过滤元组,大大降低了计算代价,中心服务器每次只发送过滤元组到分布节点,这样可以尽早且最大限度地剪枝不可能成为代表的Skyline点。提出的算法降低了服务器间的通信开销,返回了正确的结果集,实验论证了算法的有效性与高效性。     

基于MapReduce的连续概率Skyline查询

大数据对传统的Skyline研究产生了挑战,利用并行框架MapReduce计算大数据下的Skyline已成为一个研究热点。研究了不确定移动对象的Skyline查询问题,提出了一种MapReduce框架下基于事件跟踪的连续概率Skyline查询算法——MR-DTrack(domination-track algorithm based on MapReduce)。首先采用基于角度的划分方法保证负载均衡,通过预计算获取Skyline集可能变化的时刻,在Reduce阶段获取候选概率Skyline集;然后利用局部过滤点剪枝,减少计算开销;最后合并计算出全局概率Skyline集。在人工数据集和真实数据集上的实验验证了算法的有效性。     

度量空间中的Top-k反向Skyline查询算法

不同于传统的度量空间Skyline查询,提出了一种新颖的度量空间中的Skyline查询MkRS(metric top-kreverse skyline).MkRS从反向角度执行度量空间中的Skyline.给定查询对象q和单调参考函数f,MkRS返回k个包含m个数据对象的子集,以至于每个子集G的度量Skyline包含q.评估这种查询,需要执行从输入数据集P中n个数据对象里选择m个对象的穷举搜索以及每个排列子集的度量Skyline.这些计算由于巨大的搜索空间而需要极高成本.提出了基于排序机理的算法STS(sort and threshold skyline),它可以提前终止计算,仅需要检查很少部分的子集.然后,利用信息重用技术给出了基于重用的STS算法rSTS(reuse STS),进一步减少了STS中80%以上的I?O访问.大量的实验表明提出的算法有效、快速.     

RDF数据的Skyline优化查询

为解决海量RDF数据的Skyline查询问题,通过分析现有Skyline查询算法的优缺点,提出一种针对海量RDF数据的查询机制。对RDF数据的存储结构进行分析,根据RDF数据垂直存储结构,设计一种候选Skyline点筛选策略,提前修剪部分非Skyline元组,减少Skyline支配点计算的数据量;在筛选的基础上,给出基于MapReduce的Skyline并行化查询算法。实验结果表明,提前筛选能有效减小查询的数据集,并行化算法能够有效提高查询的效率。     

基于高维空间的在线高效子空间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.     

ZDC-tree:一种支持面向数据流Skyline查询的高效索引结构

数据流上的Skyline查询是近年来数据管理与数据挖掘领域的研究热点.该文针对数据流场景下基于滑动窗口Skyline查询问题,采用基于剪枝策略和分而治之思想,并结合Z-order曲线的性质,提出一种可以在一个分支上进行查询和更新操作的ZDC-tree索引结构,并给出可有效维护Skyline查询计算的ZDCSK算法.算法采用自底向上的方式,归并递归返回Skyline结果集,具备较好的Skyline查询效率.论文从理论和实验上证明了在ZDC-tree上进行Skylike查询的高效性、稳定性及可扩展性.     

无线传感器网络的ProgressiveSkyline连续查询

随着传感器技术的进步,无线传感器网络支持复杂查询在现实应用中越来越重要。Skyline查询由于可用于多种标准下的决策而受到广泛关注。对无线传感器网络中Skyline连续查询进行了研究,提出了一种增量(progressive)算法来解决静态数据集中的Skyline查询求解问题,这种增量算法能够递增返回Skyline结果,而无需事先扫描整个数据集。设计了一种新颖的算法来解决流数据集中的Skyline查询维护问题。通过实验对算法性能进行了验证,结果表明,该算法能够大大延长网络的生命周期。     

高效多子空间Skyline查询处理算法

随着Skyline查询应用的增多,子空间Skyline查询成为热点。针对实际应用中用户从多角度审视某一数据集的需求,充分研究了多子空间Skyline查询问题。在分析现有子空间Skyline查询算法解决该问题不足的基础上,提出了子空间立方体群(subspace skycube group,SSG)结构,并给出了基于该结构的同时计算任意多个子空间Skyline查询的MSSC(multiple subspace skycube)算法。该算法采用子空间候选集(subspace candidate sets,SCS),并充分利用了子空间立方体群结构中各子空间Skyline结果间的共享关系;在此基础上,算法采用求和过滤以及最大值过滤等方法,对数据集进行剪枝和过滤,从而进一步提高算法效率。最后,分别用人造数据和真实数据对算法进行实验,并与现有算法进行比较,结果表明MSSC算法可以高效地解决多子空间Skyline查询问题。     

垂直分布数据集上的安全Skyline查询算法

Skyline查询是指从多维数据集中筛选出不被其他任何数据点支配的数据点,是一种重要的数据分析方法。近年来,随着隐私保护需求的不断增长,分布式数据集上保护隐私的Skyline查询算法也受到越来越多关注。然而,现有的垂直分布数据集上的Skyline查询方案数据以明文存储,不能实现数据的隐私保护。为此,深入研究了垂直分布式数据集上保护隐私的Skyline查询问题,提出了一种抗合谋攻击的多方垂直分布数据集上的Skyline查询协议。理论分析证明了提出协议的正确性和安全性。此外,通过理论分析和模拟实验对协议运行效率进行了评估,结果显示新方案具有较高的运行效率。