Full Text:
<2593>
Summary: 
<1555>
CLC number: TP391
On-line Access: 2024-08-27
Received: 2023-10-17
Revision Accepted: 2024-05-08
Crosschecked: 2020-03-05
Cited: 0
Clicked: 6938
Efficient keyword search over graph-structured data based on minimal covered r-cliques
| ||||||||||||||
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.
@article{title="Efficient keyword search over graph-structured data based on minimal covered r-cliques",
author="Asieh Ghanbarpour, Khashayar Niknafs, Hassan Naderi",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="21",
number="3",
pages="448-464",
year="2020",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1800133"
}
%0 Journal Article
%T Efficient keyword search over graph-structured data based on minimal covered r-cliques
%A Asieh Ghanbarpour
%A Khashayar Niknafs
%A Hassan Naderi
%J Frontiers of Information Technology & Electronic Engineering
%V 21
%N 3
%P 448-464
%@ 2095-9184
%D 2020
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1800133
TY - JOUR
T1 - Efficient keyword search over graph-structured data based on minimal covered r-cliques
A1 - Asieh Ghanbarpour
A1 - Khashayar Niknafs
A1 - Hassan Naderi
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 21
IS - 3
SP - 448
EP - 464
%@ 2095-9184
Y1 - 2020
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1800133
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
[1]Bergamaschi S, Guerra F, Interlandi M, et al., 2013. QUEST: a keyword search system for relational data based on semantic and machine learning techniques. Proc VLDB Endowm, 6(12):1222-1225.
[2]Bergamaschi S, Guerra F, Interlandi M, et al., 2016. Combining user and database perspective for solving keyword queries over relational databases. Inform Syst, 55:1-19.
[3]Bron C, Kerbosch J, 1973. Finding all cliques of an undirected graph. Commun ACM, 16(9):575-577.
[4]Calado P, da Silva AS, Laender AHF, et al., 2004. A Bayesian network approach to searching Web databases through keyword-based queries. Inform Process Manag, 40(5): 773-790.
[5]Dasari NS, Ranjan D, Mohammad Z, 2014. Maximal clique enumeration for large graphs on Hadoop framework. Proc 1st Workshop on Parallel Programming for Analytics Applications, p.21-30.
[6]de Virgilio R, Cappellari P, Miscione M, 2009. 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, p.205-218.
[7]Ding BL,Yu JX, Wang S, et al., 2007. Finding top-k min-cost connected trees in databases. IEEE 23rd Int Conf on Data Engineering, p.836-845.
[8]Ghanbarpour A, Naderi H, 2018. A model-based keyword search approach for detecting top-k effective answers. Comput J, 62(3):377-393.
[9]Golenberg K, Kimelfeld B, Sagiv Y, 2008. Keyword proximity search in complex data graphs. Proc ACM SIGMOD Int Conf on Management of Data, p.927-940.
[10]Guo L, Shao F, Botev C, et al., 2003. XRANK: ranked keyword search over XML documents. Proc ACM SIGMOD Int Conf on Management of Data, p.16-27.
[11]Hao YF, Cao HP, Qi Y, et al., 2015. Efficient keyword search on graphs using MapReduce. IEEE Int Conf on Big Data, p.2871-2873.
[12]He H, Wang HX, Yang J, et al., 2007. BLINKS: ranked keyword searches on graphs. Proc ACM SIGMOD Int Conf on Management of Data, p.305-316.
[13]Kargar M, An AJ, 2011. Keyword search in graphs: finding r-cliques. Proc VLDB Endowm, 4(10):681-692.
[14]Kargar M, An AJ, 2015. Finding top-k r-cliques for keyword search from graphs in polynomial delay. Knowl Inform Syst, 43(2):249-280.
[15]Kargar M, An AJ, Yu XH, 2014. Efficient duplication free and minimal keyword search in graphs. IEEE Trans Knowl Data Eng, 26(7):1657-1669.
[16]Kim S, Lee W, Arora NR, et al., 2012. Retrieving keyworded subgraphs with graph ranking score. Expert Syst Appl, 39(5):4647-4656.
[17]Kimelfeld B, Sagiv Y, 2006. Finding and approximating top-k answers in keyword proximity search. Proc 25th ACM SIGMOD-SIGACT-SIGART Symp on Principles of Database Systems, p.173-182.
[18]Lawler EL, 1972. A procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem. Manag Sci, 18(7):401-405.
[19]Le TN, Bao FZ, Ling TW, 2015. Exploiting semantics for XML keyword search. Data Knowl Eng, 99:105-125.
[20]Li GL, Ooi BC, Feng JH, et al., 2008. 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, p.903-914.
[21]Liu F, Yu C, Meng WY, et al., 2006. Effective keyword search in relational databases. Proc ACM SIGMOD Int Conf on Management of Data, p.563-574.
[22]Mass Y, Sagiv Y, 2012. Language models for keyword search over data graphs. Proc 5th ACM Int Conf on Web Search and Data Mining, p.363-372.
[23]Mesquita F, da Silva AS, de Moura ES, et al., 2007. LABRADOR: efficiently publishing relational databases on the web by using keyword-based query interfaces. Inform Process Manag, 43(4):983-1004.
[24]Nguyen K, Cao JL, 2012. Top-K data source selection for keyword queries over multiple XML data sources. J Inform Sci, 38(2):156-175.
[25]Ning XM, Jin H, Jia WJ, et al., 2009. Practical and effective IR-style keyword search over semantic web. Inform Process Manag, 45(2):263-271.
[26]Pan YF, Wu YQ, 2013. ROU: advanced keyword search on graph. Proc 22nd ACM Int Conf on Information & Knowledge Management, p.1625-1630.
[27]Park CS, Lim S, 2015. Efficient processing of keyword queries over graph databases for finding effective answers. Inform Process Manag, 51(1):42-57.
[28]Park J, Lee SG, 2011. Keyword search in relational databases. Knowl Inform Syst, 26(2):175-193.
[29]Qin L, Yu JX, Chang LJ, et al., 2009. Querying communities in relational databases. Proc IEEE 25th Int Conf on Data Engineering, p.724-735.
[30]Sagharichian M, Naderi H, Haghjoo M, 2015. ExPregel: a new computational model for large‐scale graph processing. Concurr Comput Pract Exp, 27(17):4954-4969.
[31]Segundo PS, Lopez A, Batsyn M, et al., 2016. Improved initial vertex ordering for exact maximum clique search. Appl Intell, 45(3):868-880.
[32]Segundo PS, Artieda J, Strash D, 2018. Efficiently enumerating all maximal cliques with bit-parallelism. Comput Oper Res, 92:37-46.
[33]Tomita E, Tanaka A, Takahashi H, 2006. The worst-case time complexity for generating all maximal cliques and computational experiments. Theor Comput Sci, 363(1):28-42.
[34]Wang D, Zou L, Zhao DY, 2015. Top-k queries on RDF graphs. Inform Sci, 316:201-217.
[35]Xu YW, Guan JH, Li FR, et al., 2013. Scalable continual top-k keyword search in relational databases. Data Knowl Eng, 86:206-223.
[36]Yu T, Liu MC, 2017. A linear time algorithm for maximal clique enumeration in large sparse graphs. Inform Process Lett, 125:35-40.
[37]Yuan Y, Wang GR, Chen L, et al., 2013. Efficient keyword search on uncertain graph data. IEEE Trans Knowl Data Eng, 25(12):2767-2779.
ORCID: 
Open peer comments: Debate/Discuss/Question/Opinion
<1>