Abstract
Publish-subscribe systems present the state of the art in information dissemination to multiple users. Such systems have evolved from simple topic-based to the current XML-enabled systems. Here, users pose complex queries (expressed in XPath) on the structure and content of the streaming documents. The parts of the documents that match the user queries are then returned to the users. This paper proposes a novel hardware architecture that would exploit the parallelism found in XPath filtering systems. Using an incoming XML stream, parsing and matching with thousands of user profiles are performed simultaneously on a single FPGA, thus yielding up to three orders of magnitude higher throughput when compared to conventional approaches bound by the sequential aspect of software computing. By converting XPath expressions into custom stacks, our architecture is the first providing full support for all structural XPath constructs, including parent-child and ancestor descendant relations, whilst allowing wildcarding and recursion.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Altinel, M., Franklin, M.J.: Efficient Filtering of XML Documents for Selective Dissemination of Information. In: Proceedings of the 35th Int’l Conference on Very Large Data Bases (VLDB), pp. 53–64 (2000)
Barbosa, D., Mendelzon, A., Keenleyside, J., Lyons, K.: ToXgene: a template-based data generator for XML. In: Proceedings of ACM Management of Data (SIGMOD), p. 616 (2002)
Block RAM v1.00a, http://www.xilinx.com/support/documentation/ip_documentation/bram_block.pdf
Distributed Memory Generator v4.1, http://www.xilinx.com/support/documentation/ip_documentation/dist_mem_gen_ds322.pdf
W3.org on DOM, http://www.w3.org/DOM
Diao, Y., Altinel, M., Franklin, M.J., Zhang, H., Fischer, P.: Path sharing and predicate evaluation for high-performance XML filtering. ACM Trans. on Database Systems (TODS) 28, 467–516 (2003)
Green, T.J., Gupta, A., Miklau, G., Onizuka, M., Suciu, D.: Processing XML streams with deterministic automata and stream indexes. ACM Trans. on Database Systems (TODS), 752–788 (2004)
Guo, Z., Najjar, W., Vahid, F., Vissers, K.: A quantitative analysis of the speedup factors of fpgas over processors. In: Proc. of the 12th ACM/SIGDA Int’l Symp. on Field programmable gate arrays (FPGA), pp. 162–170 (2004)
Kwon, J., Rao, P., Moon, B., Lee, S.: FiST: scalable XML document filtering by sequencing twig patterns. In: Proceedings of the 31st international conference on Very Large Databases (VLDB), pp. 217–228 (2005)
Letz, S., Zedler, M., Thierer, T., Schutz, M., Roth, J., Seiffert, R.: XML offload and acceleration with Cell broadband engine. XTech.: Building Web 2.0 (2006)
Linderman, R.W., Lin, C.S., Linderman, M.H.: FPGA acceleration of information management services. In: High Performance Embedded Computing, HPEC (2004)
Lu, W., Gannon, D.: ParaXML: A Parallel XML Processing Model on Multicore CPUs, Techincal Report (2008)
Lunteren, J.V., Engbersen, T., Bostian, J., Carey, B., Larsson, C.: XML accelerator engine. In: 1st Int. Workshop on High Performance XML Processing (2004)
Mitra, A., Vieira, M.R., Bakalov, P., Najjar, W., Tsotras, J.T.: Boosting XML Filtering with a Scalable FPGA-based Architecture. In: 4th Biennial Conference on Innovative Data Systems Research, Asilomar (2009)
Muller, R., Teubner, J., Alonso, G.: Streams on Wires – A Query Compiler for FPGAs. In: Proceedings of the 35th Int’l Conference on Very Large Data Bases, VLDB (2009)
Clark, C.R., Schimmel, D.E.: Efficient Reconfigurable Logic Circuits for Matching Complex Network Intrusion Detection Patterns. In: 13th international conference on Field Programmable Logic and Applications, pp. 956–959. Springer, Lisbon (2003)
SAX home page, http://www.saxproject.org
XILINX DELIVERS 65nm VIRTEX-5 LX330, http://www.xilinx.com/prs_rls/2006/silicon_vir/06130lx330delivery.htm
XML Path Language (XPath) Version 1.0, W3C Recommendation (1999), http://www.w3.org/TR/xpath
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Moussalli, R., Salloum, M., Najjar, W., Tsotras, V. (2010). Accelerating XML Query Matching through Custom Stack Generation on FPGAs. In: Patt, Y.N., Foglia, P., Duesterwald, E., Faraboschi, P., Martorell, X. (eds) High Performance Embedded Architectures and Compilers. HiPEAC 2010. Lecture Notes in Computer Science, vol 5952. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11515-8_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-11515-8_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11514-1
Online ISBN: 978-3-642-11515-8
eBook Packages: Computer ScienceComputer Science (R0)