چكيده به لاتين
Nowadays, interest in searching for keywords to meet the needs of users in the massive amounts of data sources is growing strongly. Thus providing methods and algorithms that enable users to easily search efficiently their keywords regardless of complex syntax rules in data graphs is essential. In this case the focus keyword search is on to find subgraph structures including input keywords. Most of the works in keyword search over graphs find minimal connected trees contain all or part of the input keywords. Some recent research recommend finding subgraph instead of minimum trees which provide more informative answers. One of the latest researchs with finding r-cliques has improved efficiency and quality of previous methods based on subgraph. An r-clique is a set of content nodes that cover all the input keywords and the distance between each pair of nodes is less than or equal to r. Here we provide methods and algorithms by the idea of finding maximal cliques containing keywords based on Bron Kerbosch algorithm to increase performance in sequential and parallel processing modes rather than r-clique method. The r-clique method for finding approximate top-k answers tries to minimize the weight of edges between central candidate nodes to the other nodes. Thus, it is possible that the maximum distance between the nodes in obtained cliques are not less than or equal to r and they at most are 2r and in this case cliques on the overall weight increase. We provide a novel and efficient approach to achieve top-k approximate answers with a minimum weight of nodes in a row. In addition to maximizing the semantic relationship between keywords successive, approximation quality of the answers will enhance productivity as well because in the answers generated by our proposed method, r is the maximum distance between their nodes. So one of the advantages of the proposed methods is to increase the efficiency and quality of especially in sparse graphs and also mentioned the possibility of parallel processing.
Keywords: Keyword search, Graph data, Maximal clique, Bron Kerbosch, Parallel
