{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:50:20Z","timestamp":1750308620968,"version":"3.41.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,9,1]],"date-time":"2012-09-01T00:00:00Z","timestamp":1346457600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Web"],"published-print":{"date-parts":[[2012,9]]},"abstract":"<jats:p>Publish\/subscribe systems have emerged in recent years as a promising paradigm for offering various popular notification services. In this context, many XML filtering systems have been proposed to efficiently identify XML data that matches user interests expressed as queries in an XML query language like XPath. However, in order to offer XML filtering functionality on an Internet-scale, we need to deploy such a service in a distributed environment, avoiding bottlenecks that can deteriorate performance. In this work, we design and implement FoXtrot, a system for filtering XML data that combines the strengths of automata for efficient filtering and distributed hash tables for building a fully distributed system. Apart from structural-matching, performed using automata, we also discuss different methods for evaluating value-based predicates. We perform an extensive experimental evaluation of our system, FoXtrot, on a local cluster and on the PlanetLab network and demonstrate that it can index millions of user queries, achieving a high indexing and filtering throughput. At the same time, FoXtrot exhibits very good load-balancing properties and improves its performance as we increase the size of the network.<\/jats:p>","DOI":"10.1145\/2344416.2344419","type":"journal-article","created":{"date-parts":[[2012,10,2]],"date-time":"2012-10-02T13:50:00Z","timestamp":1349185800000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["FoXtrot"],"prefix":"10.1145","volume":"6","author":[{"given":"Iris","family":"Miliaraki","sequence":"first","affiliation":[{"name":"National and Kapodistrian University of Athens, Athens, Greece"}]},{"given":"Manolis","family":"Koubarakis","sequence":"additional","affiliation":[{"name":"National and Kapodistrian University of Athens, Athens, Greece"}]}],"member":"320","published-online":{"date-parts":[[2012,10,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/945721.945729"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497469"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2006.63"},{"volume-title":"Proceedings of the 26th International Conference on Very Large Data Bases (VLDB'00)","author":"Altinel M.","key":"e_1_2_1_4_1","unstructured":"Altinel , M. and Franklin , M. J . 2000. Efficient filtering of XML documents for selective dissemination of information . In Proceedings of the 26th International Conference on Very Large Data Bases (VLDB'00) . Morgan Kaufmann, San Francisco, CA, 53--64. Altinel, M. and Franklin, M. J. 2000. Efficient filtering of XML documents for selective dissemination of information. In Proceedings of the 26th International Conference on Very Large Data Bases (VLDB'00). Morgan Kaufmann, San Francisco, CA, 53--64."},{"volume-title":"Proceedings of the14th Annual ACM-SIAM Symposium on Discrete algorithms (SODA'03)","author":"Aspnes J.","key":"e_1_2_1_5_1","unstructured":"Aspnes , J. and Shah , G . 2003. Skip graphs . In Proceedings of the14th Annual ACM-SIAM Symposium on Discrete algorithms (SODA'03) . SIAM, Philadelphia, PA, 384--393. Aspnes, J. and Shah, G. 2003. Skip graphs. In Proceedings of the14th Annual ACM-SIAM Symposium on Discrete algorithms (SODA'03). SIAM, Philadelphia, PA, 384--393."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/606272.606299"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-006-8437-6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031453.1031464"},{"volume-title":"Proceedings of the 19th International Conference on Data Engineering (ICDE'03)","author":"Bruno N.","key":"e_1_2_1_9_1","unstructured":"Bruno , N. , Gravano , L. , Koudas , N. , and Srivastava , D . 2003. Navigation- vs. index-based XML multiquery processing . In Proceedings of the 19th International Conference on Data Engineering (ICDE'03) . IEEE, Los Alamitos, CA, 139--150. Bruno, N., Gravano, L., Koudas, N., and Srivastava, D. 2003. Navigation- vs. index-based XML multiquery processing. In Proceedings of the 19th International Conference on Data Engineering (ICDE'03). IEEE, Los Alamitos, CA, 139--150."},{"volume-title":"Proceedings of the 18th International Conference on Data Engineering (ICDE'02)","author":"Chan C. Y.","key":"e_1_2_1_10_1","unstructured":"Chan , C. Y. , Felber , P. , Garofalakis , M. N. , and Rastogi , R . 2002. Efficient Filtering of XML documents with XPath expressions . In Proceedings of the 18th International Conference on Data Engineering (ICDE'02) . IEEE, Los Alamitos, CA, 235. Chan, C. Y., Felber, P., Garofalakis, M. N., and Rastogi, R. 2002. Efficient Filtering of XML documents with XPath expressions. In Proceedings of the 18th International Conference on Data Engineering (ICDE'02). IEEE, Los Alamitos, CA, 235."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247562"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.70816"},{"volume-title":"Proceedings of the 2nd IEEE International Symposium on Network Computing and Applications (NCA'03)","author":"Chand R.","key":"e_1_2_1_13_1","unstructured":"Chand , R. and Felber , P. A . 2003. A scalable protocol for content-based routing in overlay networks . In Proceedings of the 2nd IEEE International Symposium on Network Computing and Applications (NCA'03) . IEEE, Los Alamitos, CA, 123--. Chand, R. and Felber, P. A. 2003. A scalable protocol for content-based routing in overlay networks. In Proceedings of the 2nd IEEE International Symposium on Network Computing and Applications (NCA'03). IEEE, Los Alamitos, CA, 123--."},{"volume-title":"XML path language (XPath). Version 1.0","author":"Clark J.","key":"e_1_2_1_14_1","unstructured":"Clark , J. and DeRose , S. J. 1999. XML path language (XPath). Version 1.0 . World Wide Web Consortium , Recommendation . http:\/\/www.w3.org\/TR\/xpath. Clark, J. and DeRose, S. J. 1999. XML path language (XPath). Version 1.0. World Wide Web Consortium, Recommendation. http:\/\/www.w3.org\/TR\/xpath."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/191839.191898"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/958942.958947"},{"volume-title":"Proceedings of the 20th International Conference on Very Large Data Bases (VLDB'04)","author":"Diao Y.","key":"e_1_2_1_17_1","unstructured":"Diao , Y. , Rizvi , S. , and Franklin , M. J . 2004. Towards an internet-scale XML dissemination service . In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB'04) . VLDB Endowment, 612--623. Diao, Y., Rizvi, S., and Franklin, M. J. 2004. Towards an internet-scale XML dissemination service. In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB'04). VLDB Endowment, 612--623."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIC.2003.1167339"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/WCW.2005.23"},{"key":"e_1_2_1_20_1","unstructured":"FreePastry release 2009. FreePastry 2.1 release. http:\/\/www.freepastry.org\/FreePastry\/.  FreePastry release 2009. FreePastry 2.1 release. http:\/\/www.freepastry.org\/FreePastry\/."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315526"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.26"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872809"},{"key":"e_1_2_1_24_1","unstructured":"Hopcroft J. E. Motwani R. Rotwani and Ullman J. D. 2000. Introduction to Automata Theory Languages and Computability. Addison-Wesley Boston MA.   Hopcroft J. E. Motwani R. Rotwani and Ullman J. D. 2000. Introduction to Automata Theory Languages and Computability. Addison-Wesley Boston MA."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.115"},{"key":"e_1_2_1_26_1","unstructured":"IBM XML.1999. Generator 1999. IBM XML Generator. http:\/\/www.alphaworks.ibm.com\/xmlgenerator.  IBM XML.1999. Generator 1999. IBM XML Generator. http:\/\/www.alphaworks.ibm.com\/xmlgenerator."},{"volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05)","author":"Jagadish H. V.","key":"e_1_2_1_27_1","unstructured":"Jagadish , H. V. , Ooi , B. C. , Tan , K. , and Vu , Q. H . 2005. BATON:A balanced tree structure for peer-to-peer networks . In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05) . VLDB Endowment, 661--672. Jagadish, H. V., Ooi, B. C., Tan, K., and Vu, Q. H. 2005. BATON:A balanced tree structure for peer-to-peer networks. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05). VLDB Endowment, 661--672."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142475"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2006.208"},{"volume-title":"Proceedings of the Advances in Database Technology (EDBT'04)","author":"Koloniari G.","key":"e_1_2_1_30_1","unstructured":"Koloniari , G. and Pitoura , E . 2004. Content-based routing of path queries in peer-to-peer systems . In Proceedings of the Advances in Database Technology (EDBT'04) . Springer, 29--47. Koloniari, G. and Pitoura, E. 2004. Content-based routing of path queries in peer-to-peer systems. In Proceedings of the Advances in Database Technology (EDBT'04). Springer, 29--47."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11926078_29"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2005.1610546"},{"key":"e_1_2_1_33_1","unstructured":"Manola F. and Miller E. 2004. RDF primer: W3c recommendation. Decision Support Systems.  Manola F. and Miller E. 2004. RDF primer: W3c recommendation. Decision Support Systems."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367614"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1827418.1827422"},{"volume-title":"Proceedings of the 33rd International Conference on Very large Data Bases (VLDB'07)","author":"Moro M. M.","key":"e_1_2_1_37_1","unstructured":"Moro , M. M. , Bakalov , P. , and Tsotras , V. J . 2007. Early profile pruning on XML-aware publish\/subscribe systems . In Proceedings of the 33rd International Conference on Very large Data Bases (VLDB'07) . VLDB Endowment, 866--877. Moro, M. M., Bakalov, P., and Tsotras, V. J. 2007. Early profile pruning on XML-aware publish\/subscribe systems. In Proceedings of the 33rd International Conference on Very large Data Bases (VLDB'07). VLDB Endowment, 866--877."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.131"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2010.01.002"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011823"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 3rd Conference on Networked Systems Design & Implementation (NSDI'06)","volume":"3","author":"Ramasubramanian V.","unstructured":"Ramasubramanian , V. , Peterson , R. , and Sirer , E. G . 2006. Corona: A high performance publish\/subscribe system for the World Wide Web . In Proceedings of the 3rd Conference on Networked Systems Design & Implementation (NSDI'06) . Vol. 3 . USENIX Association, Berkeley, CA, 2--2. Ramasubramanian, V., Peterson, R., and Sirer, E. G. 2006. Corona: A high performance publish\/subscribe system for the World Wide Web. In Proceedings of the 3rd Conference on Networked Systems Design & Implementation (NSDI'06). Vol. 3. USENIX Association, Berkeley, CA, 2--2."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.26"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/964723.383072"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 2nd Conference on Real, Large Distributed Systems (WORLDS'05)","volume":"2","author":"Rhea S.","unstructured":"Rhea , S. , Chun , B.-G. , Kubiatowicz , J. , and Shenker , S . 2005. Fixing the embarrassing slowness of OpenDHT on PlanetLab . In Proceedings of the 2nd Conference on Real, Large Distributed Systems (WORLDS'05) . Vol. 2 , USENIX Association, Berkeley, CA, 25--30. Rhea, S., Chun, B.-G., Kubiatowicz, J., and Shenker, S. 2005. Fixing the embarrassing slowness of OpenDHT on PlanetLab. In Proceedings of the 2nd Conference on Real, Large Distributed Systems (WORLDS'05). Vol. 2, USENIX Association, Berkeley, CA, 25--30."},{"volume-title":"Proceedings of the IFIP\/ACM International Conference on Distributed System Platforms (Middleware '01)","author":"Rowstron A.","key":"e_1_2_1_45_1","unstructured":"Rowstron , A. and Druschel , P . 2001. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems . In Proceedings of the IFIP\/ACM International Conference on Distributed System Platforms (Middleware '01) . Springer, Berlin, 329--350. Rowstron, A. and Druschel, P. 2001. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Proceedings of the IFIP\/ACM International Conference on Distributed System Platforms (Middleware '01). Springer, Berlin, 329--350."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575801_20"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/502034.502050"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383071"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007623"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1076034.1076090"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.50"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the IPTPS.","author":"Voulgaris S.","year":"2006","unstructured":"Voulgaris , S. , Riviere , E. , Kermarrec , A.-M. , and van Steen , M. 2006 . Sub-2-sub: Self-organizing content-based publish\/subscribe for dynamic large scale collaborative networks . In Proceedings of the IPTPS. Voulgaris, S., Riviere, E., Kermarrec, A.-M., and van Steen, M. 2006. Sub-2-sub: Self-organizing content-based publish\/subscribe for dynamic large scale collaborative networks. In Proceedings of the IPTPS."},{"key":"e_1_2_1_53_1","unstructured":"XMark 2001. XMark: An XML benchmark project. http:\/\/www.xml-benchmark.org\/.  XMark 2001. XMark: An XML benchmark project. http:\/\/www.xml-benchmark.org\/."},{"key":"e_1_2_1_54_1","unstructured":"YFilter release. 2004. YFilter 1.0 release. http:\/\/yfilter.cs.umass.edu\/code_release.htm.  YFilter release. 2004. YFilter 1.0 release. http:\/\/yfilter.cs.umass.edu\/code_release.htm."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/11558989_5"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247618"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1859127.1859132"}],"container-title":["ACM Transactions on the Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2344416.2344419","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2344416.2344419","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:39Z","timestamp":1750273659000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2344416.2344419"}},"subtitle":["Distributed structural and value XML filtering"],"short-title":[],"issued":{"date-parts":[[2012,9]]},"references-count":56,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["10.1145\/2344416.2344419"],"URL":"https:\/\/doi.org\/10.1145\/2344416.2344419","relation":{},"ISSN":["1559-1131","1559-114X"],"issn-type":[{"type":"print","value":"1559-1131"},{"type":"electronic","value":"1559-114X"}],"subject":[],"published":{"date-parts":[[2012,9]]},"assertion":[{"value":"2011-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-10-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}