陶 杰，廖湖声，高红雨

(北京工业大学 信息学部，北京 100124)

一种基于图归约的XPath高性能流数据查询方法*

陶 杰，廖湖声，高红雨

(北京工业大学 信息学部，北京 100124)

作为网络数据交换和数据共享的标准，XML数据越来越多地用于表示应用系统的流数据。然而，受制于流数据处理有限空间开销等特征，如何高效地实现这种查询成为值得探讨的问题。与传统的基于自动机或层次栈方法不同，文中提出了一种基于图归约的XML查询自动机(GRAT)，采用一种图结构来表示针对不同XML流元素的子查询任务之间的关系，通过图的归约变化来实现XPath查询。实验结果表明，基于GRAT的查询算法能够高效地完成复杂的XML查询，流数据处理的吞吐量达到了较高水平。

XML；图归约；流数据

0 引言

网络中有如传感器网络、气象监控、金融服务和网络监控等很多应用系统会持续地自动产生大量的数据。这些数据是一个随着时间延续而无限递增的动态集合，称为流数据。不同于传统数据处理，流数据[1]无法控制自身到来的顺序，并且到来的数据一经处理，就不能再次被取出或者耗费昂贵的代价取出，除非特意将数据保存。因此，流数据的处理需要满足一次存取、持续处理、有限存储和快速响应的特点。网络上用于传输和共享的数据的标准以半结构化数据为准[2]，而标记扩展语言 (eXtensible Markup Language, XML)因其自描述、半结构化等特征，已经成为了互联网上主导的数据交换和数据共享的标准[3]。随着近年来网络数据吞吐量以及各行各业的网络应用的爆炸性增长，数据量也在不断地增加，以XML为主的流数据处理已成为研究人员普遍关注的一个热点[4-5]。……