Abstract: In order to avoid storing large amounts of intermediate results and merging those intermediate results when matching twig patterns in uncertain XML,this paper proposed the algorithm ProTwigList．First,it uses Tag＋Level stream pruning to reduce the number of nodes to be processed．Second,it extends the range encoding to encode the remaining ordinary nodes,and adopts rules to mark distributed nodes．Third,it uses the path of common distributed node to deal with distributed nodes．Finally,it utilizes the probability of the lowest common ancestor node to calculate the probability of every result．The theoretical analysis and experimental results prove the efficiency of ProTwigList.

Key words: Uncertain XML,P-document,Distributed node,Rang encoding,Twig pattern