Research On Probabilistic XML Keyword Search Processing Method

Uncertain data is widespread in scientific research, information retrieval, etc. Theflexibility of XML data model can represent and store uncertain data naturally. Users cansimply and easily access the necessary information with the help of keyword search. Thispaper researched keyword search over the probabilistic XML data from the followingseveral aspects.Firstly, we find that the problem of repeatedly processing common ancestor nodes,the redundancy problem of path index and the inefficiency of pruning strategy are themain reasons for influencing the efficiency of keyword search through the analysis of theexisting algorithm.Secondly, aiming at the problem of repeatedly processing the common ancestor nodesand the redundancy problem of path index in keyword query results computation, wepropose the DeweyT labeling scheme which supports node relationship detection and nodetype judgment and path index that merely stores node path probability and nodeconditional probability. Then we propose our PrBwd algorithm, which accesses the nodesof probabilistic XML documents in reversed document order and retrieves the first kresults with the k highest probabilities of existence.Thirdly, as PrBwd algorithm processes a large number of nodes and the existingpruning strategy is inefficient, we propose the PrBwdPrun algorithm based on two newpruning strategies. Before processing the nodes of probabilistic XML documents, ourpruning strategies can get an upper bound to avoid accessing useless nodes, and thusachieve higher performance.At last, we implement our approach on XMark dataset and validate the efficiency andscalability of our method by comparing the time consumption of solving the query results.