多用户Skyline查询交互处理技术研究
发布时间：2021-08-13 09:13
大数据时代下,数据呈多维化、海量化的特征,查询趋于个性化,用户对结果的准确度、查询效率要求更高。传统的多维数据查询方法存在不能高效地解决静态和空间属性相结合、动态的多用户查询以及分类域上的个性化查询等问题,因此研究在度量空间中的多用户查询以及分类域上的用户偏好获取对于找出高质量的结果集具有十分重要的意义。多维Skyline查询根据对象数据点的属性值特性主要分成两类:数值域和分类域。本文重点关注空间数值属性查询和分类域属性交互问题,设计并提出高效的多用户Skyline查询交互算法,主要研究内容如下:（1）欧式空间中Skyline查询大多仅对空间属性进行探究,而忽略了与静态属性相结合的问题,本文基于Voronoi图、R-tree、凸包等结构的性质,提出查询区域的概念,给出Voronoi R-tree Search算法。该算法通过对数据集剪枝、分阶段支配比较等方式,有效减少了距离计算和数据点间的支配检验次数。在真实和模拟数据集中验证了该算法的有效性。（2）基于道路网的Skyline查询在动态属性上存在仅考虑距离,并未考虑用户速度对查询结果影响的问题。本文给出能处理用户速度变化的查询算法Exi...
【文章来源】：南京航空航天大学江苏省 211工程院校
【文章页数】：74 页
【学位级别】：硕士
【部分图文】：
Nassau海滩旅馆的Skyline如图1.1是Skyline查询领域中的一个经典示例
图 2.1 空间支配关系示例义 2.10 （完全支配） 对于给定的m维数据集 POI， 、∈POI，给定用以下两个必要条件时，称 完全支配 ，记为 q ： ns s 。文将分别针对这三类 Skyline 查询的相关工作进行详细阐述。静态属性上的 Skyline 查询 Skyline 研究中受到关注最早，并且研究最多的工作为对象数据集中仅包含静line 查询操作。按是否构建索引可将经典算法分为两类，如表 2.4 所示。表 2.4 经典算法不基于索引 基于索引块嵌套循环（BNL）算法[7]边际贡献（EAPSQ）算法[41]分治（D&C）算法[7]最近邻（NN）算法[40]排序过滤（SFS）算法[25]Index 算法[28]
南京航空航天大学硕士学位论文 窗口中存在点被 p 支配：将 存入窗口，剔除窗口中 所支配的 窗口中的点和 不可相互支配：如果窗口还可以继续写入，则将 ，将 存入文件，在下一次处理时调用。处理结束后，可将窗口中的对象点直接输出，其是 Skyline 结果集的环迭代中，再用上述方法将磁盘临时文件中的对象数据点进行支配比数为零时则停止迭代，此时的结果集即为最终的 Skyline 结果集。可于数据规模较小的查询。最差情况下的时间复杂度为 2O n ，最好度为 O n 。icki 等[25]基于 BNL 提出了 SFS 算法（SortFilter Skyline）。该算法首先序处理，保证后面的点无法支配排序在其前面的所有点，由此可以判的对象点一定都属于 Skyline 结果集。由此可得，SFS 既加快了计算 BNL 算法简单通用的优势。
【参考文献】：
期刊论文
[1]空间Skyline查询处理:应用、研究与挑战[J]. 余未,郑吉平,王海翔,王永阁,陈嘉良,江顺青. 计算机科学. 2017(02)
[2]基于位置范围的道路网skyline查询[J]. 施常月,秦小麟,许建秋,胡彩平. 计算机科学. 2014(09)
[3]一种处理Skyline查询的有效方法[J]. 黄震华,向阳,薛永生,刘啸岭. 计算机研究与发展. 2010(11)
[4]Skyline查询处理[J]. 魏小娟,杨婧,李翠平,陈红. 软件学报. 2008(06)
[5]Skyline计算研究综述[J]. 朱琳,关佶红,周水庚. 计算机工程与应用. 2008(06)
硕士论文
[1]道路网skyline查询处理技术研究[D]. 施常月.南京航空航天大学 2015
本文编号：3340154
【文章来源】：南京航空航天大学江苏省 211工程院校
【文章页数】：74 页
【学位级别】：硕士
【部分图文】：
Nassau海滩旅馆的Skyline如图1.1是Skyline查询领域中的一个经典示例
图 2.1 空间支配关系示例义 2.10 （完全支配） 对于给定的m维数据集 POI， 、∈POI，给定用以下两个必要条件时，称 完全支配 ，记为 q ： ns s 。文将分别针对这三类 Skyline 查询的相关工作进行详细阐述。静态属性上的 Skyline 查询 Skyline 研究中受到关注最早，并且研究最多的工作为对象数据集中仅包含静line 查询操作。按是否构建索引可将经典算法分为两类，如表 2.4 所示。表 2.4 经典算法不基于索引 基于索引块嵌套循环（BNL）算法[7]边际贡献（EAPSQ）算法[41]分治（D&C）算法[7]最近邻（NN）算法[40]排序过滤（SFS）算法[25]Index 算法[28]
南京航空航天大学硕士学位论文 窗口中存在点被 p 支配：将 存入窗口，剔除窗口中 所支配的 窗口中的点和 不可相互支配：如果窗口还可以继续写入，则将 ，将 存入文件，在下一次处理时调用。处理结束后，可将窗口中的对象点直接输出，其是 Skyline 结果集的环迭代中，再用上述方法将磁盘临时文件中的对象数据点进行支配比数为零时则停止迭代，此时的结果集即为最终的 Skyline 结果集。可于数据规模较小的查询。最差情况下的时间复杂度为 2O n ，最好度为 O n 。icki 等[25]基于 BNL 提出了 SFS 算法（SortFilter Skyline）。该算法首先序处理，保证后面的点无法支配排序在其前面的所有点，由此可以判的对象点一定都属于 Skyline 结果集。由此可得，SFS 既加快了计算 BNL 算法简单通用的优势。
【参考文献】：
期刊论文
[1]空间Skyline查询处理:应用、研究与挑战[J]. 余未,郑吉平,王海翔,王永阁,陈嘉良,江顺青. 计算机科学. 2017(02)
[2]基于位置范围的道路网skyline查询[J]. 施常月,秦小麟,许建秋,胡彩平. 计算机科学. 2014(09)
[3]一种处理Skyline查询的有效方法[J]. 黄震华,向阳,薛永生,刘啸岭. 计算机研究与发展. 2010(11)
[4]Skyline查询处理[J]. 魏小娟,杨婧,李翠平,陈红. 软件学报. 2008(06)
[5]Skyline计算研究综述[J]. 朱琳,关佶红,周水庚. 计算机工程与应用. 2008(06)
硕士论文
[1]道路网skyline查询处理技术研究[D]. 施常月.南京航空航天大学 2015
本文编号：3340154
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3340154.html
