Efficient keyword search over graph-structured data based on minimal covered <italic style="font-style: italic">r</italic>-cliques

Asieh GHANBARPOUR; Khashayar NIKNAFS; Hassan NADERI

doi:10.1631/FITEE.1800133

Your Location：

Home >

Browse articles >

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

Regular Papers | Updated：2022-05-19

- Efficient keyword search over graph-structured data based on minimal covered r-cliques
- 基于r-子团最小覆盖的图结构数据高效关键字搜索
- Frontiers of Information Technology & Electronic Engineering Vol. 21, Issue 3, Pages: 448-464(2020)
- Affiliations：
  
  Department of Computer Engineering, University of Sistan and Baluchestan, Zahedan 98167-45845, Iran
  School of Computer Engineering, Iran University of Science and Technology, Tehran 13114-16846, Iran
- Author bio：
  
  Hassan NADERI, E-mail: naderi@iust.ac.ir
- Funds：
- DOI：10.1631/FITEE.1800133
  CLC： TP391
- Received：03 March 2018，
  
  Revised：2020-;3-;5，
  
  Published：2020-03
- Accepted：
Scan QR Code
Asieh GHANBARPOUR, Khashayar NIKNAFS, Hassan NADERI. Efficient keyword search over graph-structured data based on minimal covered r-cliques[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(3): 448-464.
DOI：

Asieh GHANBARPOUR, Khashayar NIKNAFS, Hassan NADERI. Efficient keyword search over graph-structured data based on minimal covered r-cliques[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(3): 448-464. DOI： 10.1631/FITEE.1800133.

摘要

对图结构数据的查询，关键字搜索是结构化查询语言的一种替代方式。关键字查询的结果是图结构数据上一个连接的结构，其覆盖所有或部分关键字。文本覆盖率和结构紧凑性是评价关键字查询结果是否相关的两个主要属性。以往研究通过排序函数对比所有候选结果的上述属性。但是，该过程耗时长，不符合人们在交互系统中短时得到返回结果的需求。近期研究通过在搜索过程中限制搜素结果的结构形状并考察其覆盖率和紧凑性来解决上述问题。然而，这些方法仍无法解决检索结果中存在冗余节点的问题。本文针对关键字查询结果提出基于

-子团最小覆盖（minimal covered

-clique

MCC

）的概念，作为现有定义的扩展模型，并给出高效算法以检测给定查询的MCC

。这些算法的优势在于不仅可以检索出某个关键字查询的全部非重复MCCr，还可以分布式方式执行。此外，提出这些算法的近似版本，以多项式时间复杂度检索最高的

个近似MCC

。论文表明近似算法可基于成对近似排序检索出结果。基于两个真实数据集的大量实验验证了所提算法的效率和有效性。

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

-clique (MCC

) for the results of a keyword query as an extended model of existing definitions. We propose some efficient algorithms to detect the MCC

s of a given query. These algorithms can retrieve a comprehensive set of non-duplicate MCC

s 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-

approximate MCC

s 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.

关键词

Keywords

references

S Bergamaschi , , , F Guerra , , , M Interlandi , , , 等 . . QUEST: a keyword search system for relational data based on semantic and machine learning techniques . . Proc VLDB Endowm , , 2013 . . 6 ( ( 12 ): ): 1222 - - 1225 . . DOI: 10.14778/2536274.2536281 http://doi.org/10.14778/2536274.2536281 . .

S Bergamaschi , , , F Guerra , , , M Interlandi , , , 等 . . Combining user and database perspective for solving keyword queries over relational databases . . Inform Syst , , 2016 . . 55 1 - - 19 . . DOI: 10.1016/j.is.2015.07.005 http://doi.org/10.1016/j.is.2015.07.005 . .

C Bron , , , J Kerbosch . . Finding all cliques of an undirected graph . . Commun ACM , , 1973 . . 16 ( ( 9 ): ): 575 - - 577 . . DOI: 10.1145/362342.362367 http://doi.org/10.1145/362342.362367 . .

P Calado , , , AS da Silva , , , AHF Laender , , , 等 . . A Bayesian network approach to searching Web databases through keyword-based queries . . Inform Process Manag , , 2004 . . 40 ( ( 5 ): ): 773 - - 790 . . DOI: 10.1016/j.ipm.2004.03.002 http://doi.org/10.1016/j.ipm.2004.03.002 . .

NS Dasari , , , D Ranjan , , , Z Mohammad . . Maximal clique enumeration for large graphs on Hadoop framework . . Proc 1 st Workshop on Parallel Programming for Analytics Applications , , 2014 . . p.21 - - 30 . . DOI: 10.1145/2567634.2567640 http://doi.org/10.1145/2567634.2567640 . .

R de Virgilio , , , P Cappellari , , , M Miscione . . Cluster-based exploration for effective keyword search over semantic datasets . . In: Laender AHF, Castano S, Dayal U, et al. (Eds.), Conceptual Modeling - ER 2009. Springer Berlin Heidelberg , , 2009 . . p.205 - - 218 . . DOI: 10.1007/978-3-642-04840-1_17 http://doi.org/10.1007/978-3-642-04840-1_17 . .

BL Ding , , , JX Yu , , , S Wang , , , 等 . . Finding top- k min-cost connected trees in databases . . IEEE 23 rd Int Conf on Data Engineering , , 2007 . . p.836 - - 845 . . DOI: 10.1109/ICDE.2007.367929 http://doi.org/10.1109/ICDE.2007.367929 . .

A Ghanbarpour , , , H Naderi . . A model-based keyword search approach for detecting top- k effective answers . . Comput J , , 2018 . . 62 ( ( 3 ): ): 377 - - 393 . . DOI: 10.1093/comjnl/bxy056 http://doi.org/10.1093/comjnl/bxy056 . .

K Golenberg , , , B Kimelfeld , , , Y Sagiv . . Keyword proximity search in complex data graphs . . Proc ACM SIGMOD Int Conf on Management of Data , , 2008 . . p.927 - - 940 . . DOI: 10.1145/1376616.1376708 http://doi.org/10.1145/1376616.1376708 . .

L Guo , , , F Shao , , , C Botev , , , 等 . . XRANK: ranked keyword search over XML documents . . Proc ACM SIGMOD Int Conf on Management of Data , , 2003 . . p.16 - - 27 . . DOI: 10.1145/872757.872762 http://doi.org/10.1145/872757.872762 . .

YF Hao , , , HP Cao , , , Y Qi , , , 等 . . Efficient keyword search on graphs using MapReduce . . IEEE Int Conf on Big Data , , 2015 . . p.2871 - - 2873 . . DOI: 10.1109/BigData.2015.7364106 http://doi.org/10.1109/BigData.2015.7364106 . .

H He , , , HX Wang , , , J Yang , , , 等 . . BLINKS: ranked keyword searches on graphs . . Proc ACM SIGMOD Int Conf on Management of Data , , 2007 . . p.305 - - 316 . . DOI: 10.1145/1247480.1247516 http://doi.org/10.1145/1247480.1247516 . .

M Kargar , , , AJ An . . Keyword search in graphs: finding r -cliques . . Proc VLDB Endowm , , 2011 . . 4 ( ( 10 ): ): 681 - - 692 . . DOI: 10.14778/2021017.2021025 http://doi.org/10.14778/2021017.2021025 . .

M Kargar , , , AJ An . . Finding top- k r -cliques for keyword search from graphs in polynomial delay . . Knowl Inform Syst , , 2015 . . 43 ( ( 2 ): ): 249 - - 280 . . DOI: 10.1007/s10115-014-0736-0 http://doi.org/10.1007/s10115-014-0736-0 . .

M Kargar , , , AJ An , , , XH Yu . . Efficient duplication free and minimal keyword search in graphs . . IEEE Trans Knowl Data Eng , , 2014 . . 26 ( ( 7 ): ): 1657 - - 1669 . . DOI: 10.1109/TKDE.2013.85 http://doi.org/10.1109/TKDE.2013.85 . .

S Kim , , , W Lee , , , NR Arora , , , 等 . . Retrieving keyworded subgraphs with graph ranking score . . Expert Syst Appl , , 2012 . . 39 ( ( 5 ): ): 4647 - - 4656 . . DOI: 10.1016/j.eswa.2011.08.136 http://doi.org/10.1016/j.eswa.2011.08.136 . .

B Kimelfeld , , , Y Sagiv . . Finding and approximating top- k answers in keyword proximity search . . Proc 25 th ACM SIGMOD-SIGACT-SIGART Symp on Principles of Database Systems , , 2006 . . p.173 - - 182 . . DOI: 10.1145/1142351.1142377 http://doi.org/10.1145/1142351.1142377 . .

EL Lawler . . A procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem . . Manag Sci , , 1972 . . 18 ( ( 7 ): ): 401 - - 405 . . DOI: 10.1287/mnsc.18.7.401 http://doi.org/10.1287/mnsc.18.7.401 . .

TN Le , , , FZ Bao , , , TW Ling . . Exploiting semantics for XML keyword search . . Data Knowl Eng , , 2015 . . 99 105 - - 125 . . DOI: 10.1016/j.datak.2015.06.003 http://doi.org/10.1016/j.datak.2015.06.003 . .

GL Li , , , BC Ooi , , , JH Feng , , , 等 . . EASE: an effective 3-in-1 keyword search method for unstructured, semi- structured and structured data . . Proc ACM SIGMOD Int Conf on Management of Data , , 2008 . . p.903 - - 914 . . DOI: 10.1145/1376616.1376706 http://doi.org/10.1145/1376616.1376706 . .

F Liu , , , C Yu , , , WY Meng , , , 等 . . Effective keyword search in relational databases . . Proc ACM SIGMOD Int Conf on Management of Data , , 2006 . . p.563 - - 574 . . DOI: 10.1145/1142473.1142536 http://doi.org/10.1145/1142473.1142536 . .

Y Mass , , , Y Sagiv . . Language models for keyword search over data graphs . . Proc 5 th ACM Int Conf on Web Search and Data Mining , , 2012 . . p.363 - - 372 . . DOI: 10.1145/2124295.2124340 http://doi.org/10.1145/2124295.2124340 . .

F Mesquita , , , AS da Silva , , , ES de Moura , , , 等 . . LABRADOR: efficiently publishing relational databases on the web by using keyword-based query interfaces . . Inform Process Manag , , 2007 . . 43 ( ( 4 ): ): 983 - - 1004 . . DOI: 10.1016/j.ipm.2006.09.018 http://doi.org/10.1016/j.ipm.2006.09.018 . .

K Nguyen , , , JL Cao . . Top- K data source selection for keyword queries over multiple XML data sources . . J Inform Sci , , 2012 . . 38 ( ( 2 ): ): 156 - - 175 . . DOI: 10.1177/0165551511435875 http://doi.org/10.1177/0165551511435875 . .

XM Ning , , , H Jin , , , WJ Jia , , , 等 . . Practical and effective IR-style keyword search over semantic web . . Inform Process Manag , , 2009 . . 45 ( ( 2 ): ): 263 - - 271 . . DOI: 10.1016/j.ipm.2008.12.005 http://doi.org/10.1016/j.ipm.2008.12.005 . .

YF Pan , , , YQ Wu . . ROU: advanced keyword search on graph . . Proc 22 nd ACM Int Conf on Information & Knowledge Management , , 2013 . . p.1625 - - 1630 . . DOI: 10.1145/2505515.2505743 http://doi.org/10.1145/2505515.2505743 . .

CS Park , , , S Lim . . Efficient processing of keyword queries over graph databases for finding effective answers . . Inform Process Manag , , 2015 . . 51 ( ( 1 ): ): 42 - - 57 . . DOI: 10.1016/j.ipm.2014.08.002 http://doi.org/10.1016/j.ipm.2014.08.002 . .

J Park , , , SG Lee . . Keyword search in relational databases . . Knowl Inform Syst , , 2011 . . 26 ( ( 2 ): ): 175 - - 193 . . DOI: 10.1007/s10115-010-0284-1 http://doi.org/10.1007/s10115-010-0284-1 . .

L Qin , , , JX Yu , , , LJ Chang , , , 等 . . Querying communities in relational databases . . Proc IEEE 25 th Int Conf on Data Engineering , , 2009 . . p.724 - - 735 . . DOI: 10.1109/ICDE.2009.67 http://doi.org/10.1109/ICDE.2009.67 . .

M Sagharichian , , , H Naderi , , , M Haghjoo . . ExPregel: a new computational model for large‐scale graph processing . . Concurr Comput Pract Exp , , 2015 . . 27 ( ( 17 ): ): 4954 - - 4969 . . DOI: 10.1002/cpe.3482 http://doi.org/10.1002/cpe.3482 . .

PS Segundo , , , A Lopez , , , M Batsyn , , , 等 . . Improved initial vertex ordering for exact maximum clique search . . Appl Intell , , 2016 . . 45 ( ( 3 ): ): 868 - - 880 . . DOI: 10.1007/s10489-016-0796-9 http://doi.org/10.1007/s10489-016-0796-9 . .

PS Segundo , , , J Artieda , , , D Strash . . Efficiently enumerating all maximal cliques with bit-parallelism . . Comput Oper Res , , 2018 . . 92 37 - - 46 . . DOI: 10.1016/j.cor.2017.12.006 http://doi.org/10.1016/j.cor.2017.12.006 . .

E Tomita , , , A Tanaka , , , H Takahashi . . The worst-case time complexity for generating all maximal cliques and computational experiments . . Theor Comput Sci , , 2006 . . 363 ( ( 1 ): ): 28 - - 42 . . DOI: 10.1016/j.tcs.2006.06.015 http://doi.org/10.1016/j.tcs.2006.06.015 . .

D Wang , , , L Zou , , , DY Zhao . . Top- k queries on RDF graphs . . Inform Sci , , 2015 . . 316 201 - - 217 . . DOI: 10.1016/j.ins.2015.04.032 http://doi.org/10.1016/j.ins.2015.04.032 . .

YW Xu , , , JH Guan , , , FR Li , , , 等 . . Scalable continual top- k keyword search in relational databases . . Data Knowl Eng , , 2013 . . 86 206 - - 223 . . DOI: 10.1016/j.datak.2013.03.004 http://doi.org/10.1016/j.datak.2013.03.004 . .

T Yu , , , MC Liu . . A linear time algorithm for maximal clique enumeration in large sparse graphs . . Inform Process Lett , , 2017 . . 125 35 - - 40 . . DOI: 10.1016/j.ipl.2017.05.005 http://doi.org/10.1016/j.ipl.2017.05.005 . .

Y Yuan , , , GR Wang , , , L Chen , , , 等 . . Efficient keyword search on uncertain graph data . . IEEE Trans Knowl Data Eng , , 2013 . . 25 ( ( 12 ): ): 2767 - - 2779 . . DOI: 10.1109/TKDE.2012.222 http://doi.org/10.1109/TKDE.2012.222 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Analyzing close relations between target artifacts for improving IR-based requirement traceability recovery

Related Author

Haijuan WANG

Guohua SHEN

Zhiqiu HUANG

Yaoshen YU

Kai CHEN

Related Institution

College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics

Collaborative Innovation Center of Novel Software Technology and Industrialization

Key Laboratory of Safety-Critical Software, Ministry of Industry and Information Technology

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰

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

DOI：10.1631/FITEE.1800133

摘要

Abstract

关键词

Keywords

references