一种新的基于流过滤的Twig模式匹配算法

Novel Twig Pattern Matching Algorithm Based on Stream Filtering

针对传统XML文档小枝模式查询算法中,与模式树中标签名相同的节点均入内存,易造成很大的空间浪费问题,提出了一种新的算法—StreamFWM(StreamFilter Without Merging)。StreamFWM采用区间编码方式,依据节点间的结构关系过滤标签流中无用的中间节点,且不用归并,只用简单的栈和列表实现。实验结果证明,算法StreamFWM相比TwigStack在查询处理的性能上有所提高。

Traditional twig pattern matching algorithms for XML document have their defects, the algorithms put all the nodes whose label name is the same with that of pattern tree into memory, resulting in high space complexity. To im- prove the performance of twig pattern matching, a novel algorithm without merging called StreamFWM（StreamFilter With- out Merging） is proposed in the paper. StreamFWM algorithm uses the method of the region code and filters useless interme- diate nodes by the structural relationship between nodes, and uses only a few simple stacks and lists. Experimental results show that the StreamFWM algorithm improves performance of query processing compared with TwigStack.