Abstract
XML message filtering systems are used for sifting through real-time messages to support business data mining and reporting. An XML message filtering system needs to (a) process registered filter predicates on multiple distributed real-time streams and (b) match and validate the filter results with local data to identify the relevant data that can be used for higher-level processing. Although efficient real-time filtering schemes exists, the matching phase of the operation where filter results have to be matched against local data to select those matches that are relevant to the particular task remains to be expensive as it requires expensive join operations. In this paper, we present an efficient middleware (FMware) for filtering and matching XML messages against locally available data. The proposed operator relies on a novel cluster-domain matching scheme to reduce the cost of the process. We analytically study the cost of the proposed middleware and experimentally show that it adaptively reduces the number of local data accesses and provides large savings in matching time with respect to cluster-unaware matching.
This research is funded by NSF grants ITR-0326544 and IIS-0308268.
Chapter PDF
Similar content being viewed by others
References
JMS: Sun microsystem inc. (2006), http://java.sun.com/products/jms
Mohan, C., Dievendorff, D.: Recent work on distributed commit protocols, and recoverable messaging and queuing. IEEE Data Eng. Bull. 17(1), 22–28 (1994)
IBM-MQSeries (2005), http://www.ibm.com
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)
Papaemmanouil, O., Çetintemel, U.: Semcast: Semantic multicast for content-based data dissemination. In: ICDE, pp. 242–253 (2005)
Anand, A., Chawathe, S.S.: Cooperative data dissemination in a serverless environment. In: CS-TR-4562, University of Maryland, College Park (2004)
Chen, J., DeWitt, D.J., Tian, F., Wang, Y.: Niagaracq: a scalable continuous query system for internet databases. In: SIGMOD (2000)
DataPower: Xs40 XML firewall (2006), http://www.datapower.com/products/
Sarvega: XML security gateway (2006), http://www.sarvega.com/xml-guardian-gateway.html
DataPower: Xs40 XML router (2006), http://www.datapower.com/products/
Sarvega: XML context router (2006), http://www.sarvega.com/xml-context.html
Diao, Y., Franklin, M.: Query processing for high-volume XML message brokering. In: VLDB (2003)
Candan, K., Hsiung, W.P., Chen, S., Tatemura, J., Agrawal, D.: Afilter: Adaptable XML filtering with prefix-caching and suffix-clustering. In: VLDB (2006)
Josifovski, V., Fontoura, M., Barta, A.: Querying XML streams. The VLDB Journal 14(2), 197–210 (2005)
Peng, F., Chawathe, S.S.: Xsq: A streaming xpath engine. In: CS-TR-4493, University of Maryland, College Park (2003)
Jiang, H., Lu, H., Wang, W., Ooi, B.C.: XR-Tree: Indexing XML data for efficient structural joins. In: ICDE (2003)
Xpath (1999), http://www.w3.org/TR/xpath
Xquery (2006), http://www.w3.org/TR/xquery
Bruno, N., Srivastava, D., Koudas, N.: Holistic twig joins: Optimal XML pattern matching. In: SIGMOD (2002)
Chen, T., Lu, J., Ling, T.: On boosting holism in XML twig pattern matching using structural indexing techniques. In: SIGMOD (2005)
Al-Khalifa, S., Jagadish, H.V., Koudas, N., Patel, J.M.: Structural joins: A primitive for efficient XML query pattern matching. In: ICDE (2002)
Li, Q., Moon, B.: Indexing and querying XML data for regular path expressions. In: VLDB (2001)
Jiang, H., Wang, W., Lu, H.: Holistic twig joins on indexed XML documents. In: VLDB (2003)
Chien, S.Y., Tsotras, V.J., Zaniolo, C., Zhang, D.: Efficient complex query support for multiversion XML documents. In: Jensen, C.S., Jeffery, K., Pokorný, J., Šaltenis, S., Bertino, E., Böhm, K., Jarke, M. (eds.) EDBT 2002. LNCS, vol. 2287, p. 161. Springer, Heidelberg (2002)
Grust, T.: Accelerating XPath location steps. In: SIGMOD (2002)
Wang, H., Park, S., Fan, W., Yu, P.: ViST: A dynamic index method for querying XML data by tree structures. In: SIGMOD (2003)
Zhang, C., Naughton, J.F., DeWitt, D.J., Luo, Q., Lohman, G.M.: On supporting containment queries in relational database management systems. In: SIGMOD (2001)
Bremer, J., Gertz, M.: An efficient XML node identification and indexing scheme. In: VLDB (2003)
Rao, P., Moon, B.: PRIX: Indexing and querying XML using Prüfer sequences. In: ICDE (2004)
BerkeleyDB (2006), http://www.sleepycat.com/
UW XML Repos (2006), http://www.cs.washington.edu/research/xmldatasets/
Shah, M.A., Chandrasekaran, S.: Fault-Tolerant, Load-Balancing Queries in Telegraph. SIGMOD Record 30(2) (2001)
Carney, D., Cetintemel, U., Cherniack, M., Lee, C.C.S., Seidman, G., Stonebraker, M., Tatbul, N., Zdonik, S.B.: Monitoring Streams-A New Class of Data Managment Applications. In: VLDB (2003)
Tatbul, N., Cetintemel, U., Zdonik, S.B., Cherniack, M., Stonebraker, M.: Load Shedding in a Data Stream Manager. In: VLDB (2003)
Babu, S., et al.: Adaptive ordering of pipelined stream filters. In: SIGMOD (2004)
Tian, F., DeWitt, D.: Tuple Routing Strategies for Distributed Eddies. In: VLDB (2003)
Carey, M.J., Lu, H.: Load Balancing in a Locally Distributed DB System. SIGMOD Record 15(2), 108–119 (1986)
Urhan, T., Franklin, M.J.: XJoin: Getting fast answers from slow and bursty networks. Technical Report CS-TR-3994 (1999)
Mokbel, M., Lu, M., Aref, W.: Hash-merge join: A non-blocking join algorithm for producing fast and early join results. In: ICDE (2004)
Chien, S.Y., Vagena, Z., Zhang, D., Tsotras, V., Zaniolo, C.: Efficient structural joins on indexed XML documents. In: VLDB (2002)
Cooper, G.R.H.B., Franklin, M.J., Shadmon, M.: A fast index for semistructured data. In: VLDB (2001)
Milo, T., Sicuo, D.: Index structures for path expressions. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol. 1540, pp. 277–295. Springer, Heidelberg (1998)
Chen, Y., Davidson, S., Zheng, Y.: BLAS: An Efficient XPath Processing System. In: SIGMOD (2004)
Kaushik, R., Bohannon, P., Naughton, J., Korth, H.: Covering indexes for branching path queries. In: SIGMOD (2002)
Bertino, E., Catania, B., Wang, W.Q.: XJoin Index: Indexing XML data for efficient handling of branching path expressions. In: ICDE (2004)
Chung, J.M.C., Shim, K.: Apex: An adaptive path index for xml data. In: ACM SIGMOD (2002)
Ramanan, P.: Covering indexes for XML queries: Bisimulation - simulation = negation. In: VLDB (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 IFIP International Federation for Information Processing
About this paper
Cite this paper
Candan, K.S., Dönderler, M.E., Qi, Y., Ramamoorthy, J., Kim, J.W. (2006). FMware: Middleware for Efficient Filtering and Matching of XML Messages with Local Data. In: van Steen, M., Henning, M. (eds) Middleware 2006. Middleware 2006. Lecture Notes in Computer Science, vol 4290. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11925071_16
Download citation
DOI: https://doi.org/10.1007/11925071_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49023-4
Online ISBN: 978-3-540-68256-1
eBook Packages: Computer ScienceComputer Science (R0)