学位论文 > 优秀研究生学位论文题录展示

结果分级的快速子序列相似查询方法研究

作　者: 朱鹤
导　师: 金顺福
学　校: 燕山大学
专　业: 计算机软件与理论
关键词: 结果分级非线性降维增量式隐私保护模型安全距离计算协议
分类号: TP311.13
类　型: 硕士论文
年　份: 2010年
下　载: 17次
引　用: 0次
阅　读: 论文下载

内容摘要

时间序列相似查询是从时间序列数据中查找与给定序列相似的序列或子序列,是一种新型的、重要的时间序列数据分析方法,具有广阔应用前景。本文在综合分析国内外时间序列相似查询研究现状的基础上,对子序列相似查询进行深入研究,具体内容如下。首先,原有降维技术造成序列数据搜索空间无界性,使得子序列相似查询算法在索引遍历时不能充分实现点过滤。为此,采用一种新的非线性降维技术有效解决点过滤问题。并且引入提前终止技术,有效减少序列距离计算时的冗余计算。对子序列的查询结果分级,提出分级子序列相似查询算法。其次,当数据序列动态变换和查询参数动态更新时,为了减少直接采用分级子序列相似查询算法产生的许多重复计算,利用增量数组记录上次查询计算的序列距离值,以求解本次查询的最优查询参数。针对数据序列范围增加、数据序列范围减少、查询参数动态变换三种情况,分别提出增量式分级子序列相似查询算法。然后,防止分级子序列相似查询中序列数据的隐私泄露,提出隐私保护模型保护序列数据的安全。利用降维来隐藏原序列数据,通过标号替换策略保护序列的均值。提出安全距离计算协议以实现序列数据的安全距离计算。并详细分析了隐私保护模型的正确性、安全性、精确性及计算代价。在此基础上,提出了隐私保护的分级子序列相似查询算法。最后,对提出的算法进行实验验证,并对实验结果进行分析和比较。

全文目录

摘要  5-6
ABSTRACT  6-12
第1章绪论  12-18
  1.1 研究背景  12-13
  1.2 研究现状  13-16
  1.3 存在问题  16
  1.4 研究内容  16-17
  1.5 本文组织结构  17-18
第2章基础知识  18-28
  2.1 引言  18
  2.2 基本概念  18-19
    2.2.1 时间序列  18
    2.2.2 时间序列数据挖掘  18-19
    2.2.3 时间序列相似查询  19
  2.3 时间序列相似查询关键技术  19-24
    2.3.1 序列度量标准  20-21
    2.3.2 序列降维技术  21-23
    2.3.3 序列分割技术  23-24
    2.3.4 序列查询方式  24
  2.4 时间序列索引方式  24-26
    2.4.1 R 树特性  25
    2.4.2 R 树操作  25-26
  2.5 时间序列相似查询的完备性  26-27
  2.6 本章小结  27-28
第3章分级子序列相似查询方法  28-40
  3.1 引言  28
  3.2 最近邻查询技术  28-29
  3.3 MS 非线性降维  29-34
    3.3.1 MS 降维基本定义  29
    3.3.2 MS 降维主要思想  29-30
    3.3.3 MS 降维的正确性  30-33
    3.3.4 MS 降维紧密下限  33-34
  3.4 提前终止原理  34-35
  3.5 分级子序列相似查询算法  35-39
    3.5.1 RankTopk 算法索引构建  35-36
    3.5.2 RankTopk 算法关键问题  36-37
    3.5.3 RankTopk 算法详细描述  37-38
    3.5.4 RankTopk 算法效率分析  38-39
  3.6 本章小结  39-40
第4章增量式分级子序列相似查询方法  40-48
  4.1 引言  40
  4.2 重复计算  40
  4.3 增量数组  40-41
  4.4 增量式分级子序列相似查询算法  41-47
    4.4.1 数据序列范围增加  41-43
    4.4.2 数据序列范围减少  43-45
    4.4.3 查询参数动态变换  45-47
  4.5 本章小结  47-48
第5章隐私保护的分级子序列相似查询方法  48-58
  5.1 引言  48
  5.2 相关定义  48-49
  5.3 隐私保护模型  49-50
    5.3.1 隐私保护模型中参与各方具体流程  49-50
    5.3.2 隐私保护模型中各阶段的安全策略  50
  5.4 隐私保护模型中安全技术  50-53
    5.4.1 标号替换策略  50-51
    5.4.2 安全距离计算  51-53
    5.4.3 参数传递方式  53
  5.5 隐私保护模型分析  53-55
    5.5.1 隐私保护模型正确性分析  53-54
    5.5.2 隐私保护模型安全性分析  54-55
    5.5.3 隐私保护模型精确性分析  55
    5.5.4 隐私保护模型计算代价分析  55
  5.6 隐私保护的分级子序列相似查询算法  55-57
    5.6.1 PPRANKTOPK 算法的详细描述  55-57
    5.6.2 PPRANKTOPK 算法的过程分析  57
    5.6.3 PPRANKTOPK 算法正确性分析  57
  5.7 本章小结  57-58
第6章实验验证  58-64
  6.1 引言  58
  6.2 验证分级子序列相似查询算法  58-60
    6.2.1 实验设置  58
    6.2.2 实验数据  58-59
    6.2.3 实验结果  59-60
  6.3 验证增量式分级子序列相似查询算法  60-62
    6.3.1 实验设置  60
    6.3.2 实验数据  60
    6.3.3 实验结果  60-62
  6.4 本章小结  62-64
结论  64-66
参考文献  66-72
攻读硕士学位期间承担的科研任务与主要成果  72-73
致谢  73-74
作者简介  74

结果分级的快速子序列相似查询方法研究

内容摘要

全文目录

相似论文