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

图上的关键字搜索算法

作　者: 蒋凯
导　师: 周水庚
学　校: 复旦大学
专　业: 计算机软件与理论
关键词: 关键字搜索随机游走概率模型
分类号: TP391.3
类　型: 硕士论文
年　份: 2010年
下　载: 126次
引　用: 0次
阅　读: 论文下载

内容摘要

近十年来,关键字搜索技术一直是数据库、信息检索和数据挖掘领域的研究热点。而当前,图上的关键字搜索由于具有更加广泛的适用性而备受关注。图上的关键字搜索算法与传统的关键字搜索算法不同,查询处理返回的查询结果是图上的子图,每一个查询结果子图包含所有的查询关键字。现有的图上关键字搜索算法基于最小斯坦纳树,使用反向搜索和正向搜索结合的方法来得到符合查询关键字的子图。然而这类算法具有三个不足,使得查询结果缺乏语义信息：一,在搜索时未考虑节点与查询关键字的匹配程度；二,在搜索是未考虑图结构中隐含的结构信息；三,树结构的子图不能表现出足够的语义信息。本文提出了两个新的图上关键字搜索算法,使用了现代信息检索技术中的向量空间模型和随机游走模型来解决以上缺陷,使得查询结果更具语义信息。基于重启型随机游走的图上关键字搜索算法,在重启型随机游走模型的基础上加入了向量空间模型。该算法首先搜索得到与所有查询关键字相关的中心节点,再通过中心节点搜索连接成子图。而基于概率模型的图上关键字搜索算法,设计了一个综合了向量空间模型和重启型随机游走模型的概率打分函数。该算法首先搜索得到与查询关键字匹配的关键字节点,再由这些关键字节点的中心节点将它们连接成子图。实验结果证明,本文提出的算法是有效的。

全文目录

摘要  5-6
Abstract  6-7
第一章绪论  7-20
  1.1 研究背景  7-9
  1.2 研究现状  9-19
    1.2.1 关系数据库上的关键字搜索算法  9-11
    1.2.2 图上的关键字搜索算法  11-18
    1.2.3 现有算法的不足  18-19
  1.3 本文贡献  19
  1.4 本文结构  19-20
第二章问题描述  20-24
  2.1 现有图上关键词搜索查询语义存在的问题  20-21
  2.2 一个新的图上关键词搜索查询语义  21-22
  2.3 一个新的图上关键字搜索算法框架  22-23
  2.4 本章小结  23-24
第三章基于重启型随机游走的图上关键字搜索  24-39
  3.1 PageRank算法与个人化的PageRank算法  24-25
  3.2 重启型随机游走模型  25-26
  3.3 基于重启型随机游走的关键字搜索算法  26-32
    3.3.1 向量空间模型  27-28
    3.3.2 改进的重启型随机游走模型  28
    3.3.3 图上的关键字搜索算法  28-32
  3.4 实验结果与分析  32-38
    3.4.1 实验环境  32-34
    3.4.2 实验设置  34-35
    3.4.3 查询准确率  35-37
    3.4.4 查询效率  37-38
  3.5 本章小结  38-39
第四章基于概率模型的图上关键字搜索  39-53
  4.1 概率打分函数  39-42
    4.1.1 查询包含两个查询关键字  39-41
    4.1.2 查询包含κ个查询关键字  41-42
  4.2 关键字节点搜索算法  42-45
  4.3 子图连接算法  45-48
    4.3.1 CePS算法  45-46
    4.3.2 基于CePS的子图连接算法  46-48
  4.4 基于概率的图上关键字搜索算法  48
  4.5 实验结果与分析  48-51
    4.5.1 查询准确率  49-50
    4.5.2 查询效率  50-51
  4.6 本章小结  51-53
第五章总结与展望  53-55
参考文献  55-59
致谢  59-60

图上的关键字搜索算法

内容摘要

全文目录

相似论文