Research On Query Processing For XML Keyword Queries Based On The ID List And Hash Index

Keyword search on XML(eXtensible Markup Language) data has attracted more andmore attention and the computational efficiency of CA(common ancestor) node is the keyproblem of affecting system performance, so we research on how to improve theefficiency of computing CA node.Firstly, through in-depth comparison and analysis of existing keyword queryprocessing algorithms based on the IDList index, we find that the major reason ofinefficiency of existing algorithms is the large number of binary search operations whencomputing CA node. in response to the above problem, we propose FwdSLCA-HSalgorithm based on the IDList index combined with hash index. The FwdSLCA-HS canconvert the binary search into hash probe, while at the same time, be eager in transforminguseless hash probe operations into comparsion operations as many as possible.Secondly, in response to the problem that the FwdSLCA-HS algorithm need hashprobe to process every CA node, we design BwdSLCA-HS algorithm based on the IDListindex. The BwdSLCA-HS algorithm compute all CA nodes in reverse document order,which can avoid the cost of probing the hash table for non-leaf CA nodes.Thirdly, in response to suffering from much more hash probe operation on non-CAnodes in the BwdSLCA-HS algorithm, we propose HybSLCA-HS algorithm combinedFwdSLCA-HS algorithm with BwdSLCA-HS algorithm, which can skip as many non-leafCA nodes as possible in reverse document, while at the same time, process non-CA nodesin document order.At last, we conduct the rich experiments on different database and evaluate the meritsand demerits of the algorithms by different indicators and verify the efficiency of ourmethods.