超大有向图上Top-k顶点度查询的一种有效处理方法

扫码查看

原文链接

NETL

中文摘要：由于传统的关系数据库存在着数据存储冗余和查询效率低下等缺陷,近年来图数据库的应用越来越广泛,其上的查询也成为人们研究的问题. 本文中要解决的Top-k顶点度查询问题如下: 给定一个超大的有向图,查询其顶点度(包括入度和出度)为前k大的顶点分别是哪些顶点. Top-k顶点度的查询在很多背景上都有其应用.比如根据论文的引用情况可以建立一个图,将所有的论文作为顶点,两篇论文的引用关系作为有向边,构成一个图,那么统计被引用的最多的一些论文,即从中查找Top-k顶点度的顶点. 利用对图进行一遍简单扫描的方法显然可以求得问题的精确解,但是这个方法的时空开销过大,因此在超大图背景下该方法是不实用的.然而在超大图背景下,利用可以承受的时空开销,求得问题的近似解却是一种可行的方法.本文提出的方法的基本思想是先根据查询在内存中建立估计Top-k顶点度的数据结构,后续查询通过访问该数据结构得以回答,从而降低了算法的时空开销。

作者：

于博、李建中、王宏志、高宏

展开 >

作者单位：

哈尔滨工业大学计算机科学与技术学院,哈尔滨,150001

关键词：

超大有向图图数据库 Top-k顶点度查询数据查询

主办单位：

中国计算机学会

会议名称：

第二十三届中国数据库学术会议（NDBC2006）

会议时间：

2006-11-01

会议地点：

广州

会议母体文献：

计算机科学

页码：

106-107,143

出版时间：

2006