点击此处 ,将本页翻译成中文
将本页翻译成中文
您现在的位置:首页> 外文期刊>浙江大学学报(英文版)(C辑:计算机与电子) >文献详情
【24h】

Efficient keyword search over graph-structured data based on minimal covered r-cliques

【摘要】 Keyword search is an alternative for structured languages in querying graph-structured data. A result to a keyword query is a connected structure covering all or part of the queried keywords. The textual coverage and structural compactness have been known as the two main properties of a relevant result to a keyword query. Many previous works examined these properties after retrieving all of the candidate results using a ranking function in a comparative manner. However, this needs a time-consuming search process, which is not appropriate for an interactive system in which the user expects results in the least possible time. This problem has been addressed in recent works by confining the shape of results to examine their coverage and compactness during the search. However, these methods still suffer from the existence of redundant nodes in the retrieved results. In this paper, we introduce the semantic of minimal covered r-clique (MCCr) for the results of a keyword query as an extended model of existing definitions. We propose some efficient algorithms to detect the MCCrs of a given query. These algorithms can retrieve a comprehensive set of non-duplicate MCCrs in response to a keyword query. In addition, these algorithms can be exe-cuted in a distributive manner, which makes them outstanding in the field of keyword search. We also propose the approximate versions of these algorithms to retrieve the top-k approximate MCCrs in a polynomial delay. It is proved that the approximate algorithms can retrieve results in two-approximation. Extensive experiments on two real-world datasets confirm the efficiency and effectiveness of the proposed algorithms.

【期刊名称】 浙江大学学报(英文版)(C辑:计算机与电子)

【作者】 Asieh GHANBARPOUR; Khashayar NIKNAFS; Hassan NADERI;

【作者单位】 School of Computer Engineering Iran University of Science and Technology Tehran 13114-16846 Iran; Department of Computer Engineering University of Sistan and Baluchestan Zahedan 98167-45845 Iran;

【收录信息】;

【年(卷),期】2020(021),003

【年度】2020

【页码】448-464

【总页数】17

【原文格式】PDF

【正文语种】eng

【中图分类】TP391;

【原文服务方】国家工程技术数字图书馆

【关键词】Keyword search;Graph mining;Information retrieval;Database;Clique;

联系方式:18141920177 (微信同号)

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号