XML-filtreringssystem syftar till att snabbt och i realtid matcha XML-kodade data med ett stort antal frågespecifikationer som innehåller begränsningar för både struktur och innehåll. Det är nu väl accepterat att metoder som använder händelsebaserad tolkning och Finite State Machines (FSM) kan utgöra grunden för mycket skalbara strukturorienterade XML-filtreringssystem. XFilter-systemet [Altinel och Franklin 2000] var den första publicerade FSM-baserade XML-filtreringsmetoden. XFilter använde en separat FSM per sökväg och en ny indexeringsmekanism för att låta alla FSM utföras samtidigt under behandlingen av ett dokument. Med utgångspunkt i insikterna i XFilter-arbetet beskriver vi en ny metod, kallad "YFilter" som kombinerar alla sökvägens frågor till en enda Nondeterministic Finite Automaton (NFA). YFilter utnyttjar allmängiltighet bland frågor genom att slå samman gemensamma prefix för sökvägarna så att de behandlas som mest en gång. Den resulterande delade behandlingen ger enorma förbättringar i strukturmatchning prestanda men komplicerar hanteringen av värdebaserade predikat. I den här artikeln beskriver vi först XFilter och YFilter metoder och presentera resultat av en detaljerad prestandajämförelse av struktur matchning för dessa algoritmer samt en hybrid metod. Resultaten visar att den vägdelning som används av YFilter kan ge resultat i ordning. Vi föreslår sedan två alternativa tekniker för att förlänga YFilters gemensamma Detta arbete har delvis fått stöd av National Science Foundation inom ramen för ITR bidrag IIS0086057 och SI0122599, och CAREER bidrag IRI-9501353, genom Rom Labs avtal nr. F30602-97-2-0241 under DARPA ordernummer F078, och av Boeing, IBM, Intel, Microsoft, Siemens och UC MICRO programmet. Författarens adress: Y. Diao, M. J. Franklin och H. Zhang, avdelningen för EECS University of California, Berkeley, 421 Soda Hall, Berkeley, CA 94720; e-post: {diaoyl, franklin,nhz}@cs. berkeley.edu; M. Altinel, IBM Almaden Research Center, San Jose, CA 95120; e-post: maltinel@us. ibm.com; P. Fischer, Institutet för datavetenskap, University of Heidelberg, Heidelberg, Tyskland; e-post: peter.fischer@informatik.uni-heidelberg.de. Tillstånd att göra digitala eller hårda kopior av delar eller allt detta arbete för personligt bruk eller klassrum beviljas utan avgift under förutsättning att kopior inte görs eller distribueras för vinst eller direkt kommersiell fördel och att kopior visar detta meddelande på första sidan eller första skärmen av en skärm tillsammans med den fullständiga citering. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar, för att omfördela till listor, eller för att använda någon komponent i detta verk i andra verk krävs förhandsgodkännande och/eller avgift. Tillstånd kan begäras från publikationsavdelningen, ACM, Inc., 1515 Broadway, New York, NY 10036 USA, fax: +1 (212) 869-0481, eller behörigheter@acm.org. Strukturmatchning med stöd för värdebaserade predikat och jämförelse av dessa två teknikers prestanda. Resultaten av denna senare studie visar på några viktiga skillnader mellan delad XML-filtrering och traditionell databasförfrågningsbehandling. Slutligen beskriver vi hur YFilter-metoden utvidgas för att hantera mer komplicerade frågor som innehåller inbäddade sökvägar.
Baserat på XFilter, ett nytt system föreslogs i REF benämnd YFilter som kombinerade alla sökvägar i en enda Nondeterministic Finite Automaton (NFA) och utnyttjade gemensamhet mellan användarprofiler genom att slå samman gemensamma prefix av användarprofil vägar så att de behandlades på mest en gång.
Path sharing and predicate evaluation for high-performance XML filtering
{'venue': 'TODS', 'journal': None, 'mag_field_of_study': ['Computer Science']}