面向不确定数据的Top-k查询处理关键技术研究
发布时间：2021-01-02 06:55
Top-k查询作为一种重要的数据管理操作,在信息检索、生物医疗、多目标决策支持等领域都发挥着重要的作用。由于网络传输延迟、数据采集设备精度限制、以及保护用户隐私数据等主客观原因,在日常的生产生活中,不确定数据广泛存在,从而为数据的查询带来了新的挑战。另外,随着云计算的普及,人们对于数据的隐私保护越来越重视,在数据安全与可用性之间需要作出审慎的权衡。针对不确定数据top-k查询处理面临的挑战,对该问题的研究工作分别从以下三个维度进行开展:首先,针对不确定数据上查询语义多样性导致查询复杂度高的问题,给出了基于期望编辑距离的不确定字符串top-k查询的形式化定义,提出了一个新的距离语义概率n-gram集合映射距离,进而结合查询语义以及概率n-gram分词的特点,提出基于概率n-gram集合映射距离的近似匹配过滤算法,并通过建立基于概率n-gram划分的多层倒排索引以及频率矩阵来进一步优化算法实现。通过对该算法进行时间复杂度分析和一系列对比实验性能评测,验证该算法实现对不确定字符串top-k查询的高效处理,相比于基准算法具有较高的剪枝过滤能力和良好的可扩展性。其次,针对查询候选集规模膨胀导致单...
【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校
【文章页数】：111 页
【学位级别】：博士
【部分图文】：
基于概率n-gram划分的两层倒排索引
n-grams 的其他可能映射显示为虚线，从而计算得出1SG 与2SG 的 (,)12SSe ：=1+1+(0.8×1+0.2×1)+(0.8×1+0.2×2)+(0.8×1+0.2×1)+1=5.4.3.2 基于 GMD 的近似匹配过滤算法定理 2.1 给定两个不确定字符串1S 和2S ，如果 (,)12SSe 的值小于等于 τ，那么 至少包含有 (S,S) 12 个 n-gram 的 gram 映射编辑距离 GED 小于等 (0 n)，其中(S,S){|S|,|S|}-n1-(,,)1212 max n + (2即，1S 和2S 至多有 ( , ,n)个 n-gram 的 GED 大于 (0 n)，其中 ( , ,n) max{1,n 2 }+n( 1)(2
华 中 科 技 大 学 博 士 学 位 论 文图 2.5（a）和图 2.5（b）分别描述了随着不确定字符串数据集中字符串平均长度的变化，TUSK 算法和 Baseline 基准算法（在以下实验数据图中标注为 Direct）在执行时间和过滤效果上的性能对比。通过分别令 y 0,1,2,3，分别得到字符串平均长度从 13.6, 27.2, 40.8 到 54.4 不等的不确定字符串集合。如图 2.5（a）所示，随着字符串长度的增加，TUSK 和 Baseline 基准算法的查询时间都随之增大，但无论是从查询时间绝对值还是查询时间增长的速率来看，TUSK 都明显优于基准算法；同时，如图 2.5（b）所示，基准算法无论在何种情况下都需要遍历所有的测试集合才能返回查询结果，而 TUSK 只需要访问其中很小一部分数据，大概 80%以上的数据都被算法剪枝过滤掉了，这些实验结果也从另一个角度反映了 TUSK 算法的查询性能要明显优于基准算法。
【参考文献】：
期刊论文
[1]指数衰减模式下基于矩阵机制的差分隐私流数据发布算法[J]. 吴英杰,葛晨,张立群,孙岚. 中国科学:信息科学. 2017(11)
[2]面向数据发布和分析的差分隐私保护[J]. 张啸剑,孟小峰. 计算机学报. 2014(04)
[3]云数据管理系统中查询技术研究综述[J]. 史英杰,孟小峰. 计算机学报. 2013(02)
[4]云环境下一种隐私保护的高效密文排序查询方法[J]. 程芳权,彭智勇,宋伟,王书林,崔一辉. 计算机学报. 2012(11)
[5]不确定性Top-K查询处理[J]. 李文凤,彭智勇,李德毅. 软件学报. 2012(06)
[6]P2P环境下面向不确定数据的Top-k查询[J]. 孙永佼,袁野,王国仁. 计算机学报. 2011(11)
[7]集合和字符串的相似度查询[J]. 林学民,王炜. 计算机学报. 2011(10)
[8]一种面向不确定对象的可见k近邻查询算法[J]. 王艳秋,徐传飞,于戈,谷峪,陈默. 计算机学报. 2010(10)
[9]面向查询服务的数据隐私保护算法[J]. 朱青,赵桐,王珊. 计算机学报. 2010(08)
[10]不确定性数据管理技术研究综述[J]. 周傲英,金澈清,王国仁,李建中. 计算机学报. 2009(01)
博士论文
[1]面向多维不确定数据的若干查询处理关键技术的研究[D]. 徐传飞.东北大学 2013
本文编号：2952879
【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校
【文章页数】：111 页
【学位级别】：博士
【部分图文】：
基于概率n-gram划分的两层倒排索引
n-grams 的其他可能映射显示为虚线，从而计算得出1SG 与2SG 的 (,)12SSe ：=1+1+(0.8×1+0.2×1)+(0.8×1+0.2×2)+(0.8×1+0.2×1)+1=5.4.3.2 基于 GMD 的近似匹配过滤算法定理 2.1 给定两个不确定字符串1S 和2S ，如果 (,)12SSe 的值小于等于 τ，那么 至少包含有 (S,S) 12 个 n-gram 的 gram 映射编辑距离 GED 小于等 (0 n)，其中(S,S){|S|,|S|}-n1-(,,)1212 max n + (2即，1S 和2S 至多有 ( , ,n)个 n-gram 的 GED 大于 (0 n)，其中 ( , ,n) max{1,n 2 }+n( 1)(2
华 中 科 技 大 学 博 士 学 位 论 文图 2.5（a）和图 2.5（b）分别描述了随着不确定字符串数据集中字符串平均长度的变化，TUSK 算法和 Baseline 基准算法（在以下实验数据图中标注为 Direct）在执行时间和过滤效果上的性能对比。通过分别令 y 0,1,2,3，分别得到字符串平均长度从 13.6, 27.2, 40.8 到 54.4 不等的不确定字符串集合。如图 2.5（a）所示，随着字符串长度的增加，TUSK 和 Baseline 基准算法的查询时间都随之增大，但无论是从查询时间绝对值还是查询时间增长的速率来看，TUSK 都明显优于基准算法；同时，如图 2.5（b）所示，基准算法无论在何种情况下都需要遍历所有的测试集合才能返回查询结果，而 TUSK 只需要访问其中很小一部分数据，大概 80%以上的数据都被算法剪枝过滤掉了，这些实验结果也从另一个角度反映了 TUSK 算法的查询性能要明显优于基准算法。
【参考文献】：
期刊论文
[1]指数衰减模式下基于矩阵机制的差分隐私流数据发布算法[J]. 吴英杰,葛晨,张立群,孙岚. 中国科学:信息科学. 2017(11)
[2]面向数据发布和分析的差分隐私保护[J]. 张啸剑,孟小峰. 计算机学报. 2014(04)
[3]云数据管理系统中查询技术研究综述[J]. 史英杰,孟小峰. 计算机学报. 2013(02)
[4]云环境下一种隐私保护的高效密文排序查询方法[J]. 程芳权,彭智勇,宋伟,王书林,崔一辉. 计算机学报. 2012(11)
[5]不确定性Top-K查询处理[J]. 李文凤,彭智勇,李德毅. 软件学报. 2012(06)
[6]P2P环境下面向不确定数据的Top-k查询[J]. 孙永佼,袁野,王国仁. 计算机学报. 2011(11)
[7]集合和字符串的相似度查询[J]. 林学民,王炜. 计算机学报. 2011(10)
[8]一种面向不确定对象的可见k近邻查询算法[J]. 王艳秋,徐传飞,于戈,谷峪,陈默. 计算机学报. 2010(10)
[9]面向查询服务的数据隐私保护算法[J]. 朱青,赵桐,王珊. 计算机学报. 2010(08)
[10]不确定性数据管理技术研究综述[J]. 周傲英,金澈清,王国仁,李建中. 计算机学报. 2009(01)
博士论文
[1]面向多维不确定数据的若干查询处理关键技术的研究[D]. 徐传飞.东北大学 2013
本文编号：2952879
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/2952879.html
