Abstract: Probabilistic XMI. can describe the uncertain data effectively, and Dewcy code is the most important encoding method for indexing probabilistic XML documents. But during the keyword search in big probabilistic XML documents,it takes much time for comparing the Dewey code of keyword index frectuently. To deal with the problem above, the probabilistic XML document was partitioned into several fragments, and a new Dewey encoding method of keyword index for probabilistic XML documents was designed, thus, a Parallel Top-k Keyword Search Algorithm (PTKS) was proposed. I}he experiment results show that the PTKS algorithm has low time complexity, especially, its efficiency is improved significantly when the structure of the document is complicated.

Key words: Probabilistic XML,SLCA,XML document partition,Dewey code,Parallel search