大规模动态图中标签约束的频繁子图Top-K查询

摘要：

Top-K子图查询作为重要的图搜索技术,因可更具针对性地为用户返回查询结果而被广泛应用于社交网、生物信息网等新兴领域.随着图规模增大且动态演变,用户通常希望通过增加约束条件而快速、准确获得查询结果.鉴于上述查询需求,提出了一种标签约束的频繁子图Top-K查询方法(LVC-FS Top-K).该方法通过建立频繁结构映射与标签值聚合的二级索引(FSM-LVA),快速准确地锁定查询图结构并根据约束限制剪枝过滤,缩小查询范围,提高查询效率;利用FSM-LVA索引对同构于查询图的频繁结构进行查找以实现频繁结构查询,同时结合查询图的约束条件及K值限制对频繁子图进行匹配筛选,缩小比较空间,加快查询效率.实验结果表明提出的方法能快速准确地在大规模动态图中进行具有约束限制的频繁子图Top-K查询.

关键词：大规模动态图、标签约束、聚合划分、Top-K查询

所属期刊栏目：12

分类号：TP311(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant Nos. 61472169, 61502215;the National Key Research and Development Program of China under Grant No. 2016YFC0801406;the Science Research Normal Foundation of Education Department of Liaoning Province under Grant No. L2015193;the Doc-toral Science Research Start Foundation of Liaoning Province under Grant No. 201501127

在线出版日期：2018-12-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：1740-1747