图上的关键字搜索算法

摘要

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