下载文档原格式
一种基于压缩策略的高维空间子空间skyline查询算法孟熠;刘玉葆;李启睿【期刊名称】《计算机研究与发展》【年(卷),期】2013(050)0z1【摘要】skyline操作就是找出数据集中不被其他数据点支配的点的集合,但是随着数据属性维度的不断增多,通常人们只对数据集的某几个属性感兴趣,高维空间子空间skyline计算就是发现数据集中在某几个特定维度上不被其他点支配的点的集合,skyline计算在数据量大时其时间花销是非常大的,快速的返回结果才是人们能接受的.基于此提出了一个RSky算法,在原有CSky算法的基础上,指出并改进了其存在的3处明显不足,并根据InvertS索引的特性提出了一个压缩扫描策略,通过设置每个维度的下限来控制要处理的桶,除去不必要处理的桶和不可能是skyline的点,从而减少了点与点之间的比较次数.实验结果表明了RSky算法的有效性.【总页数】8页(P101-108)【作者】孟熠;刘玉葆;李启睿【作者单位】中山大学信息科学与技术学院广州 510006;中山大学信息科学与技术学院广州 510006;中山大学信息科学与技术学院广州 510006【正文语种】中文【中图分类】TP301【相关文献】1.障碍空间中基于R+树的空间Skyline查询方法 [J], 李松;李爽;张丽平;郝晓红2.基于高维空间的在线高效子空间Skyline算法——CSky [J], 周红福;宫学庆;郑凯;周傲英3.一种基于排序子空间的高维聚类算法及其可视化研究 [J], 刘勘;周晓峥;周洞汝4.一种采用Z曲线高维空间范围查询算法 [J], 徐红波;郝忠孝5.基于网格和队列触发的多维空间Skyline查询算法 [J], 张斌;孟凡荣;闫秋艳因版权原因，仅展示原文概要，查看原文内容请购买。
Skyline服务查询实验实验内容：应用BNL算法和SFS算法对QWS数据集进行skyline服务查询算法介绍及实现：➢BNL算法该算法首先在内存中开辟有一块窗口，用于存放从文件中读入的疑似是SP的数据。
还有临时文件T，当内存中的窗口满时，原本需要插入到窗口中的点将被保存在临时文件中。
算法的流程如下：从存放需要查询的数据的文件F中，读取一个数据点p，与窗口中的所有点比较（如果窗口为空，则直接插入），根据比较结果不同执行下面三种操作。
●窗口中存在一点q，q点支配p点，则p点不可能是SP成员，将p点丢弃。
●p点支配窗口中的一个或多个点，则被p点支配的所有点不可能是SP成员，将它们删去。
●p点与窗口内所有的点都不相互支配，若窗口的容量仍够存放p点则插入p点，否则将p点插入临时文件T中。
当所有点都读取完并执行完上述操作时，窗口中在临时文件中加入第一个点之前就已经加入的点作为SP输出。
将临时文件T作为数据来源，即作为存放需要查询的数据的文件F，新建一个空白的临时文件T'，从1开始循环执行该过程。
知道所有的点或者被丢弃，或者被作为SP输出。
具体实现（python）：def BNL(len1,len2,data_array):reslist = []for i in range(len1):if len(reslist) == 0:reslist.append(i)else:deletelist=[]remain = Truefor k in reslist:kqicnt = 0iqkcnt = 0for t in range(len2):if data_array[i][t] >= data_array[k][t]:iqkcnt = iqkcnt + 1if data_array[i][t] <= data_array[k][t]:kqicnt = kqicnt + 1if kqicnt == 9:remain = Falsebreakif iqkcnt == 9:deletelist.append(k)if len(deletelist) > 0:reslist = [reslist[p] for p in range(0, len(reslist), 1 ) if p not in deletelist]if remain:reslist.append(i)return reslist➢SFS算法在BNL的基础上先对数据进行预处理（排序），使得加入的点一定是SP，减少删除的开销具体实现（python）：def SFS(data,len1,len2):reslist = []reslist.append(0)for i in range(1,len1):remain = Truefor k in reslist:kqicnt = 0for t in range(len2):if data[i][t] <= data[k][t]:kqicnt = kqicnt + 1if kqicnt == 9:remain = Falsebreakif remain:reslist.append(i)return reslistQoS服务数据randdataset产生的Qos服务数据集放在了QoSdata文件中，通过传入该数据集检验上面的算法实验结果分析：BNL运行结果（数据较多，截图不全）：SFS运行结果（数据较多，截图不全）：运行速率分析BNL算法：SFS算法：。
《外包空间数据库中范围和移动k近邻skyline的查询验证》篇一一、引言随着空间数据库的广泛应用，对外包空间数据库中范围和移动k近邻查询的需求日益增长。
Skyline查询作为一种重要的空间查询技术，能够有效地找出给定空间范围内的多个目标对象，以构建多维度的轮廓（Skyline）进行信息可视化与挖掘。
本篇论文主要讨论如何对外包空间数据库中范围和移动k近邻的Skyline查询进行验证，以保障查询的准确性和高效性。
二、外包空间数据库与Skyline查询概述外包空间数据库（Outsourced Spatial Database）是一种将空间数据存储在云端或外部服务器上的数据库系统。
其优点在于可以充分利用云计算资源，提高数据处理和存储的效率。
Skyline查询则是一种基于空间对象的多维轮廓查询技术，它能够找出给定空间范围内的多个目标对象，并将它们根据一定规则组合成轮廓图谱。
这种查询技术常用于空间数据分析、地图生成等场景。
三、范围和移动k近邻Skyline查询范围和移动k近邻Skyline查询是外包空间数据库中常见的两种查询需求。
其中，范围k近邻查询是指在给定空间范围内，查找距离指定目标点最近的k个点；而移动k近邻查询则是指在一段时间内，找出离移动点最近的k个点。
这两种查询都需要利用Skyline技术来构建多维度的轮廓图谱，以支持后续的信息挖掘和可视化工作。
四、查询验证方法为了保障外包空间数据库中范围和移动k近邻Skyline查询的准确性和高效性，我们需要采用一系列的验证方法。
首先，我们可以通过设计合理的测试用例来验证查询的正确性。
这些测试用例应该涵盖不同的空间范围、目标点、距离等参数条件，以确保在各种情况下都能得到正确的结果。
其次，我们可以利用已有的数据集进行验证，通过将我们的查询结果与已知的正确结果进行比较，来评估我们的算法性能和准确性。
此外，我们还可以采用一些性能评估指标来衡量我们的算法在处理大规模数据时的效率。
RDF数据的Skyline优化查询郑志蕴;李青;张行进;李全民;李钝【摘要】为解决海量RDF数据的Skyline查询问题,通过分析现有Skyline查询算法的优缺点,提出一种针对海量RDF数据的查询机制.对RDF数据的存储结构进行分析,根据RDF数据垂直存储结构,设计一种候选Skyline点筛选策略,提前修剪部分非Skyline元组,减少Skyline支配点计算的数据量;在筛选的基础上,给出基于MapReduce的Skyline并行化查询算法.实验结果表明,提前筛选能有效减小查询的数据集,并行化算法能够有效提高查询的效率.【期刊名称】《计算机工程与设计》【年(卷),期】2016(037)004【总页数】6页(P933-937,958)【关键词】Skyline查询;RDF数据;MapReduce框架;云计算;多目标决策【作者】郑志蕴;李青;张行进;李全民;李钝【作者单位】郑州大学信息工程学院,河南郑州450001;郑州大学信息工程学院,河南郑州450001;郑州大学信息工程学院,河南郑州450001;河南省旅游局,河南郑州450000;郑州大学信息工程学院,河南郑州450001【正文语种】中文【中图分类】TP311Skyline查询思想是在给定D维属性元组集合中，查询Skyline支配点集合。
所谓一个数据点P(p1,p2,…,pD)支配另一个数据点Q(q1,q2,…,qD)，是指P点在所有维度上的值都不差于Q点，并且至少有一个维度上的值优于Q。
以Skyline查询的经典例子酒店入住来解释说明。
某旅客欲查询某旅游景点周围住宿情况，酒店距离景点的距离和酒店价格是两个主要的参考指标。
如图1中点代表酒店，横轴表示酒店离景点的距离，纵轴表示住宿的价格。
显然，图中折线上的点表示性价比比较好的酒店，但折线上点与点之间相比又互有优势。
这些点即为要查找的Skyline 支配点。
在关系数据库中，Skyline查询技术比较成熟。
基于Skyline的搜索结果排序方法尹文科;吴姗姗;丁峰;荀智德【摘要】针对现有垂直搜索引擎的排序结果存在多样性差和冗余度高的问题,提出了一种基于Skyline的搜索结果排序方法.该方法通过计算搜索结果的轮廓等级、支配度和覆盖度作为排序依据,并且为加快轮廓等级和支配度的计算,使用了一种基于Bitmap的轮廓等级和支配度计算算法.实验结果表明,该方法的排序结果具有低冗余度和高多样性的优点,并且具有更快的轮廓等级和支配度计算速度.【期刊名称】《计算机应用》【年(卷),期】2015(035)004【总页数】6页(P1154-1158,1184)【关键词】Skyline;轮廓等级;支配度;覆盖度;Bitmap【作者】尹文科;吴姗姗;丁峰;荀智德【作者单位】信息系统工程重点实验室,南京210007;信息系统工程重点实验室,南京210007;信息系统工程重点实验室,南京210007;信息系统工程重点实验室,南京210007【正文语种】中文【中图分类】TP301.60 引言随着互联网的发展，垂直搜索引擎的数量和种类得到了极大的丰富，这些垂直搜索引擎采用的排序方法无外乎综合排序和单一维度排序两种。
综合排序一般是将搜索结果的各种属性，如相关度、价格、好评度等，进行加权求和后得出的分值作为排序依据。
而单一维度排序则是按照数据某一维度的属性进行排序，如按价格、热销程度排序等。
然而无论采用综合排序还是单一维度排序，现有垂直搜索引擎的排序结果往往存在冗余度大、多样性差的问题。
例如某用户的搜索请求是“距离天安门5 km 范围内的酒店”，假设其搜索结果如图1 所示。
若采用价格最优排序，则只能得到100 ～150 元，距离3 km ～5 km 的酒店，如右下方矩形框中的点所示;而如果采用距离最优排序，则只能得到250 ～400元，距离1 ～2 km 的酒店，如左上方矩形框中的点所示;若采用综合排序，则通常只能得到中间矩形框中的点。
障碍环境中空间Skyline查询方法李松;窦雅男;张丽平;郝晓红【期刊名称】《计算机科学与探索》【年(卷),期】2018(012)012【摘要】为了弥补现有的研究成果对处理障碍环境下空间Skyline查询问题的不足,提出了在障碍环境下基于Voronoi图的空间Skyline查询方法.该方法在实际应用中可以用来解决多目标决策问题.依据查询点集合是否发生变化提出了两种情况下的障碍环境中空间Skyline查询(spatial Skyline queries in obstacle space,OSSQ)方法:一种是静态查询点的障碍环境中空间Skyline查询(static query points of Skyline query in obstacle space,STA_OSSQ)方法,该查询方法主要包括约剪数据集和支配检查两个过程,最后得到Skyline集合;另一种是动态查询点状态下的障碍环境中Skyline查询(dynamic query points of Skyline query in obstacle space,DYN_OSSQ)方法,该方法主要处理了查询点动态增加和减少情况下障碍环境中空间Skyline查询问题.理论研究和实验表明所提出的方法具有较高的效率.【总页数】9页(P1882-1890)【作者】李松;窦雅男;张丽平;郝晓红【作者单位】哈尔滨理工大学计算机科学与技术学院,哈尔滨 150080;哈尔滨理工大学计算机科学与技术学院,哈尔滨 150080;哈尔滨理工大学计算机科学与技术学院,哈尔滨 150080;哈尔滨理工大学计算机科学与技术学院,哈尔滨 150080【正文语种】中文【中图分类】TP311.13【相关文献】1.障碍空间中基于R+树的空间Skyline查询方法 [J], 李松;李爽;张丽平;郝晓红2.一种障碍空间数据库中的连续反k近邻查询方法 [J], 谷峪;于晓楠;于戈3.障碍物环境中的路网最近邻查询方法 [J], 李林;张丽平;李松4.道路网环境下K-支配空间Skyline查询方法 [J], 李松; 窦雅男; 郝晓红; 张丽平; 郝忠孝5.会展空间室内环境中无障碍设计的研究 [J], 郭无霜;胡平因版权原因，仅展示原文概要，查看原文内容请购买。
