|
|
Frontiers of Information Technology & Electronic Engineering
ISSN 2095-9184 (print), ISSN 2095-9230 (online)
2020 Vol.21 No.3 P.448-464
Efficient keyword search over graph-structured data based on minimal covered r-cliques
Abstract: 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 executed 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.
.
This article has been corrected, see doi:10.1631/FITEE.18e0133
Key words: Keyword search, Graph mining, Information retrieval, Database, Clique
1伊朗科技大学计算机工程学院，伊朗德黑兰，13114-16846
2锡斯坦-俾路支斯坦大学计算机工程系，伊朗扎黑丹，98167-45845
摘要：对图结构数据的查询，关键字搜索是结构化查询语言的一种替代方式。关键字查询的结果是图结构数据上一个连接的结构，其覆盖所有或部分关键字。文本覆盖率和结构紧凑性是评价关键字查询结果是否相关的两个主要属性。以往研究通过排序函数对比所有候选结果的上述属性。但是，该过程耗时长，不符合人们在交互系统中短时得到返回结果的需求。近期研究通过在搜索过程中限制搜素结果的结构形状并考察其覆盖率和紧凑性来解决上述问题。然而，这些方法仍无法解决检索结果中存在冗余节点的问题。本文针对关键字查询结果提出基于r-子团最小覆盖（minimal covered r-clique,MCCr）的概念，作为现有定义的扩展模型，并给出高效算法以检测给定查询的MCCr。这些算法的优势在于不仅可以检索出某个关键字查询的全部非重复MCCr，还可以分布式方式执行。此外，提出这些算法的近似版本，以多项式时间复杂度检索最高的k个近似MCCr。论文表明近似算法可基于成对近似排序检索出结果。基于两个真实数据集的大量实验验证了所提算法的效率和有效性。
关键词组：
References:
Open peer comments: Debate/Discuss/Question/Opinion
<1>
DOI:
10.1631/FITEE.1800133
CLC number:
TP391
Download Full Text:
Downloaded:
2336
Download summary:
<Click Here>Downloaded:
1406Clicked:
6304
Cited:
0
On-line Access:
2020-03-18
Received:
2018-03-03
Revision Accepted:
2018-09-11
Crosschecked:
2020-03-05