DEIM Forum 2014 A1-5

Path-based Keyword Search over XML Streams
Savong BOU† , Toshiyuki AMAGASA†† , and Hiroyuki KITAGAWA††† Graduate School of Systems and Information Engineering, University of Tsukuba
1-1-1 Tennodai, Tsukuba, Ibaraki 305-8573, Japan†† Faculty of Engineering, Information and Systems, University of Tsukuba
1-1-1 Tennodai, Tsukuba, Ibaraki 305-8573, Japan
E-mail: †savong.bou@kde.cs.tsukuba.ac.jp, ††{amagasa,kitagawa}@cs.tsukuba.ac.jp
Abstract Recently, a great deal of attention has been focusing on processing keyword search over XML and XML
streams. The keyword search is simple and provides a user-friendly way of retrieving required data from an XML
data. Though its popularity, there is a concern over its eﬃciency. For this reason, several methods have been
proposed to enable keyword search over XML streams. However, most of them primarily aim at processing pure
keyword search where only keywords are allowed as a query. However, in many cases, there is a demand to combine
keyword search and path-based query. To address this problem, we propose a method to integrate XPath andkeyword search so that we can combine XPath- and keyword-based query, thereby making users possible to express
their search demands in more specific ways. The experimental results show that the proposed scheme can process
queries over XML streams practically.
Key words XML Streams, Keyword Search, XPath, XQuery

1. Introduction

than a complicated XPath-based query. For this reason, keyword search over XML data has been studied well, and many

Extensible Markup Language (XML) [1] is a standard for

XML database systems support such functionality. However,representing semi-structured data. XML has been used inthose engines support keyword search over XML data, which

various applications, because it is powerful and versatile

are permanently stored and can be indexed for eﬃcient re-while it is simple.

trieval, and few research works address keyword search overIn many applications, information represented using XML

XML data in streaming environments [6, 8, 13].

is exchanged in real-time. This kind of information is called

In [8, 13], they proposed a scheme to process multiple

XML streams [9]. Several applications of XML streams have

keyword-based queries over XML streams. It oﬀers a goodemerged recently, such as web services, sensor networks, etc.

compromise between performance and memory usage, which

In such applications, it is often required to filter necessary

makes it the best choice in real world scenarios. Besides, [6]data out of incoming XML streams, and, typically, such re-proposed a technique based on refining a keyword query to aquests are represented in terms of XPath expressions [9].

query graph being a sub-graph of corresponding DTD docu-

In the meantime, a large number of web services, such as

ment so that their stack-based algorithm can process XML

blogs, news sites, and podcast hosts, are currently dissem-

stream and manage the buﬀer of search results in a single

inating their contents in the form of streaming XML data.

pass eﬃciently using their new search heuristic.

The variability and heterogeneity of those sources make the

It is worth to mention that, in many application scenar-

usage of traditional querying schemes, which are based on

ios, there is a strong need to make keyword search against

path-based query language [9], cumbersome for end users,

some specific parts of XML data whose structures constantly

because those languages require precise knowledge about thechange and are unknown or little known. Taking a biblio-

underlying schemas of XML data being queried in order tographic XML data for example, one may make a query only

formulate meaningful queries. On the other hand, keyword

on abstract, but not to elsewhere. However, since keywords

search [4, 6–8, 10, 12–14], where only few keywords are usedin keyword search can appear either as label(XML element)

to query XML data, provides a simple and eﬀective queryor textual value, and can carry multiple and diﬀerent mean-

paradigm. For example, if one wishes to retrieve partial XML

ings, it is hard to express the exact search intention only withdata related to XML query processing, he only needs to put

keywords. In particular, it is hard to specify which parts ofthree keywords, “XML”, “query” and “processing” rather

XML data the keyword search should be applied to.

The above problem can be solved by combining XPath-source, which is shown in Figure 1. From this data source,

based query with keyword search. The XPath-based query

if a user wants to retrieve information on any publication

will be used as a mean to specify which part of XML data

which is written by author "Porter" and has type "Novel",the keyword search should be applied to, and the keywords

he may issue a keyword search, q1 , with two keywords as

are used to specify the user’s demand for the query results.

"author::Porter type:Novel". Similarly, the user may is-

It should be noticed that the combination of XPath- andsue a query, q2 , "author::Porter War" if he wants to know

keyword-based queries is beneficial to the users, because they

any publication which is about "War" and written by author

can exploit the benefits from both query styles, that is, one"Porter". Note that, in this data source, we observe that

does not need to fully understand the structure of the doc-

the word "book" appears as both XML element and textual

uments being queried, while having the freedom to limit thevalue. Therefore, if the user issues keyword search, q3 , "bookparts of the documents to be retrieved in terms of an XPathauthor::Hiroki", the keyword book matches both XML ele-

expression. However, to the best of authors’ knowledge, noment "book" whose ID is 2 and textual value of XML element

research has been made on this type of query in a streaming"title" whose ID is 8 because this keyword is in the form

setting so far.

of k as mentioned above.

To address this problem, we propose a scheme to process XPath queries combined with keyword search over XML
streams. More precisely, we extend NFA model to support
XPath-based keyword search. We also extend NFA-based
YFilter [5] with the method used in CKStream [8].

2. Preliminaries
First, we would like to explain some preliminaries related
to our work.

Fig. 1: An example of XML data

XPath XML Path Language (XPath) [9] is an expres-

Combining XPath with keyword search: it is nat-sion language that allows us to locate specific XML fragmentsural to extend XPath so that it can deal with keyword-

in a given piece of XML data. More precisely, an XPath ex-

based queries. More precisely, keyword search can be usedpression, P, is defined as the following grammar [9]:to specify a query predicate in an XPath expression. In fact,

P ::= /N | //N | PP

XQuery and XPath Full Text 1.0 [2] is a W3C standard for

N ::= E | A | text(S) | *that purpose. Since our objective is to combine keyword

Here, E, A, and S are an element label, an attribute label,search with XPath-based queries, we partially borrow theand a string constant, respectively, and * is the wild card.

syntax from it. Here is the basic syntax.

The function text(S) matches a text node whose value is/XPath[ftcontains(keyword-search query)]the string S.

where XPath is an XPath expression and ftcontains is

XML Keyword Search is a style of XML data search,a dedicated function to specify a keyword search query ac-

where a set of keywords are given as the input, and the set ofcording to [4,8,13]. Note that the XPath and keyword-searchranked XML fragments that match with the query specifica-

query are connected by a descendant axis.

tion is returned as the query result. In [4, 8, 13], the syntax

Node Relatedness Heuristics in XML keyword search,of keyword search is defined as follows.

for a set of given keywords, it is essential to decide which［Definition 1］ An XML keyword search Q is a set of search

XML fragments are most eligible to be query results. For

terms (t1 , ..,tm ). Each query term is of the form: l::k,

this reason, many heuristics have been proposed [4,10,12,14].

l::, ::k, or k, where l is a node label and k a keyword. A

Among these, LCA (Lowest Common Ancestor) is known tonode ni satises a query term of the form:

be the fundamental method, where the lowest XML frag-•l::k if ni ’s label equals l and the tokenized textual

content of ni contains the word k.

ments that subsume the entire keyword set and the fragments are identified. Subsequently, to improve LCA, many•l:: if ni ’s label equals label l.

•variants have been proposed.

::k if the textual content of ni contains the word k.

•［Definition 2］ SLCA (Smallest Lowest Common Ancestor)

k if either ni ’s label is k or the tokenized textual con-[14]: two nodes n1 and n2 that belong to the same XML data

tent of ni contains the word k.
To better illustrate the concept of keyword search, we
present an example with a fragment of bibliography datadi are meaningfully related if there are no nodes n3 ∈ di andn4 ∈ di such that LCA(n3 , n4 ) descendant of LCA(n1 , n2 ).

Node v ∈ di , such that v ∈ LCA(n1 , n2 ), v ∈ SLCA(n1 , n2 ).

Figure 2 shows the NFA fragments of basic location steps.

However, there are some criticisms against SLCA heuris-

There is a transition from one state to another state via atic, for its answer is too compact, and the smallest subtree

directed edge representing a transition. The symbol on an

is not always the correct answer of keyword search.

Asedge represents the incoming XML element that triggers thea result, some accurate answers are discarded. For exam-

transition. The special symbol "*" matches any element.

ple, we have a keyword search "author::Porter title::",The symbol "ε" is used to denote an epsilon-transition.

which is to search for the title of any publication writtenby author "Porter". Based on SLCA heuristic, the subtree rooted at node chapter ID 6 is returned. However, thesubtree rooted at node book ID 2 is not returned as answer
eventhough it is also the correct result of this query. To
complement such loopholes, MLCA heuristic [11] has been
proposed. MLCA heuristic takes the relationship between

Fig. 3: XPath queries and a corresponding NFA

pairs of all keywords in the query into consideration; consequently, each result under MLCA heuristic is a patternFigure 3 shows an example of such a Non-deterministic Fi-

match, in which every two nodes are meaningfully related.

nite Automation (NFA) corresponding to five XPath queries.

Therefore, with MLCA heuristic, the answers of the above

A circle denotes a state. Circles with double lines denote ac-query are sets of all matched nodes in subtrees rooted at node

cepting states, marked by the IDs of accepted queries.

chapter ID 6 and book ID 2. MLCA is defined as follow:［Definition 3］ MLCA (Meaningful Lowest Common Ances-

When processing an XML data, it is parsed with a SAX
parser, which is an event-based XML parser; whenever ittor) [11]: Let the set of nodes in an XML data be N . Two

reads a new XML constructs, such as start- and end-tags,

nodes are of the same type if and only if they have the sametext content, etc., it raises a corresponding event and is no-

tag name. Given A, B ⊆ N , where A is comprised of nodes

tified to the application program. When YFilter receives aof type α, and B is comprised of nodes of type β, the MLCA

start element events, it triggers a state transitions in the

set C ⊆ N of A and B satisfies the following conditions:

FSMs, while an end element event is received, YFilter must•∀ck ∈ C, ∃ai ∈ A, bj ∈ B, such that ck = LCA(ai , bj ).

ck is denoted as M LCA(ai , bj ).
•backtrack to previous states. A run-time stack is used to
track the active and previously processed states.

∀ai ∈ A, bj ∈ B, if dij = LCA(ai , bj ) and dij ∈/ C,then ∃ck ∈ C, ck is descendant of dij .
•Then set C is denoted as M LCASET (A, B).

3. Existing Approaches
3. 1 YFilter
YFilter [5] is an XML filtering system that provides realtime, fast matching of large numbers of queries, containing constraints on both structure and content, against bothFig. 4: An example of query processing in YFilter

static XML data and XML streams. The key innovation in

Figure 4 shows a running example of the run-time stack,

YFilter is that it generates a single Nondeterministic Finite

which process queries in Figure 3 by XML data in Figure 1.

Automation (NFA) from all the input-queries. YFilter also

The content of stack is a set of active state ID. When receiv-

provides better structure matching and additional benefits

ing a start element event, it follows all matching transitions

including a relatively small number of machine states, incre-

from the currently active states. First, if a transition marked

mental machine construction, and ease of maintenance.

by the incoming element name exists, the next state is added
to the set of new active states. A transition marked by the"*" symbol is checked in the same way. Then, the state itself is added to the set. Finally, if an "ε"-transition exists,
the state after the "ε"-transition is processed immediately
according to these same rules.
3. 2 CKStream

Fig. 2: Basic NFA Location Step

CKStream [8] is an algorithm to process multiple keyword

search over XML streams. It relies on parsing stacks and4. Proposed Scheme

query indexes specially designed to allow the simultaneous
matching of terms from diﬀerent queries. CKStream also

4. 1 Proposal Overview

relies on a SAX parser.

We extend NFA-based YFilter [5] with keyword-based CK-

Parsing Stack: when parsing an XML stream, each vis-

Stream [8] in an attempt to make the filtering engine sup-ited XML node, e.g., element or text, is associated with anports XPath query, keyword search query, and XPath-based

entry in a stack, and that entry handles the following in-

keyword search. More precisely, we extend the NFA-basedformation: (1) the label of the element of the entry; (2) afinite state machine in YFilter by adding the data struc-bitmap called CAN BE SLCA , which contains one bit fortures in CKStream, such as a set of used queries and query

each query being evaluated, (3) a set used queries contain-

bitmap, thereby combining the keyword-search capability of

ing the IDs of the queries whose terms include keywords andCKStream and the path-based filtering of YFilter. In ad-(4) keywords. Each entry is popped from the stack when its

dition, we use MLCA heuristic to generate query results,

corresponding node and all its descendants have been visited.

whereas SLCA is used in CKStream, because it gives more re-Query Index: To eﬃciently deal with a large number

lated and compact results than other heuristics [12]. MLCA

of queries, the algorithms exploits query indexes for eﬃcient

returns a set of nodes that match queries.

query look up. Each index entry represents a query term and4. 2 Extension of NFA Model in YFilter

refers to queries in which this term occurs. It also diﬀeren-

In YFilter, a state transition occurs only when an XML el-tiates between structural (label) and non-structural (value)

ement is read, but, to support keyword search, a state tran-

query terms. A sample query index created from queries q1 ,sition is also needed for text content. For this reason, we

q2 , and q3 above is shown in Figure 5.

modify the NFA model as follows. The edges with the labelsof the form "text() con" represent state transitions corresponding to text nodes, that are enabled when text nodecontains the specified keywords. In addition, each accepting

Fig. 5: Example of Query Index

state in the extended NFA contains the position of bit inside
the query bitmap. Queries are matched by checking if all

Query Bitmap: Stores information about which key-

bits corresponding to their respective queries are matched.

words from each query have occurred in an XML node, which

The basic extended-NFA location steps are shown in Figure

is kept using a bitmap stored on the stack entry correspond-7.

ing to such a node. This bitmap is called query bitmap andeach of its bits is associated with one unique search termfrom each query. The information stored in query bitmap issimilar to that of query index, but they are used diﬀerently.
A sample of query bitmap from queries q1 , q2 , and q3 above
is shown in Figure 6.

Fig. 6: An Example of Query Bitmap
When a startelement(tag) comes, it searches the query in-

Fig. 7: Basic Extended-NFA Location Step
4. 3 Combining YFilter and CKStream

dex for the current node’s label, obtaining the positions as-

By using the extended NFA model, our proposed work con-sociated with the entry corresponding to this label. It sets to

structs an extended-NFA corresponding to a set of XPath-true the bit position associated with this occurrence in thebased keyword search. Similar to YFilter and CKStream, thequery bitmap of the new stack entry. Similarly, when charac-

proposed scheme based on SAX parser. In addition, two datater() comes, it searches the query index and sets true to thestructures, query bitmap and used query, are borrowed fromcorresponding bits. Notice that terms of the form l::k are

CKStream to process keyword queries; they are used when-handled in this function and receive a specic treatment. Fi-

ever there is a push of an entry into the stack. When there

nally, when an endelement(tag) comes, it looks for complete

is a trigger to pop an entry from stack, queries are evaluatedqueries , i.e., those in which all search terms are satised by

to be matched or not by looking at bits in query bitmap

the node being processed (or by its decedents).

corresponding to each used queries from set used query.

The details of our proposed algorithm are shown in AlFunction Start of Element, Callback Function Text,

Algorithm 1 The Proposed Method Callback Functions
Callback Function Start of Element
Input: Parsing stack S, the XML node e being processed

Callback Function End of Element.

1: initialization

gorithm 1 below. There are 3 main functions: Callback

Callback Function Start of Element:

When thestartelement(tag) is called, this function is invoked.

Allbits in the query bitmap are set to false by default. Then
startelement(tag) is processed against the single extended-

2: Push(sn) {create new stack entry}
3: Process e against extended-NFA
4: Add the newly active states to the stack
5: N := number of distinct terms in all queries being pro-

cessedNFA. Then all the newly-active states are checked one by

6: sn.query bitmap[0,…,N-1] :=false

one. If any of those states are accepting states, the query

7: while each newly active state do

IDs and the positions of bits in the query bitmap will beif sn.state is accepting state then9:p := get position of query bitmap
10:
q := get query ID of keyword matched11:
Add q to sn.used queries
12:sn.query bitmap[p] :=true
13:
end if
14: end whileobtained. The query IDs are put in the set of used queries
and the bits of the query bitmap are set to true at the obtained bit positions. If no accepting state exists, all bits inthe query bitmap remain false and the set of used queries isblank. Finally, the set of active states, query bitmap, and set

8:of used queries are inserted into an entry, which later pushes
into the stack.
Callback Function Text: When the character() event

Callback Function Text
Input: Parsing stack S, the XML node e being processedis called, textual content is split into tokens. Then each to-

1: initialization

ken is processed by the single extended-NFA. Following the

2: sn := *top(S) {sn points to the top entry in the stack}same procedure as mentioned in Callback Function Start

3: K := set of tokens in node eof Element, the information that is obtained from the accepting states are used to update the entry at the top of thestack (the entry of parent nodes in the stack). In Callback
Function Text, no new query bitmap nor new set of used
queries are created; and therefore, no new entry is pushed
into the stack.
Callback Function End of Element: When an endelement(tag) is called, the entry is popped out from the stack.
Then all query IDs in the set of used queries in the popped
entry are checked one by one. For each query ID being pro-4: while all k ∈ K do

Process k against extended-NFA
Add the newly active states to the stack
7:
while each newly active state do
8:
if sn.state is accepting state then9:p := get position of query bitmap of term l::k10:
q := get query ID of keyword matched11:
Add q to sn.used queries
sn.query bitmap[p] :=true
12:
13:
end if14:
end while
15: end while
5:

6:

cessed, all bits in the query bitmap of the corresponding
query are checked. If they are all true, the corresponding
query matches, and the results are returned. If not all bits

Callback Function End of Element
Input: Parsing stack S, the XML node e being processedof the corresponding query are true, then that corresponding

1: initialization

query IDs is added to the set of used queries of the top entry

2: sn := pop(S) {pops the top entry in the stack to sn}of the stack and all bits in the query bitmap of the popped

3: tn := *top(S) tn points to the top entry in the stack

entry are used to update the query bitmap of the top entry

4: while q ∈ sn.used queries doby using "OR" operator.
We show how our proposed method works by running thetwo queries below against the XML data shown in Figure 1.
The detail run is shown in Figure 9.
Q1: //book[ftcontains(author::Porter type::Novel)]
Q2: /bib/book/chapter[ftcontains(author::Porter War)]
These queries contain three unique keywords, so thequery bitmap will be of size 3 where t1 , t2 and t3 are theposition of each keyword in the query bitmap. By using theextended-NFA model, from the two queries, a single NFA isconstructed as shown in Figure 8.

let j1 ,…, jN be the positions of the bits corresponding to terms from query q in query bitmap
6:
COMPLETE := sn.query bitmap[j1 ] and... andsn.query bitmap[jN ]7:
if sn.state is accepting state then8:q.results := q.results ∪ sn
9:
else
10:
Add sn.used queries to tn.used queries
tn.query bitmap := sn.query bitmap or
11:
tn.query bitmap
12:
end if
13: end while5:

As shown in Figure 9, when new XML data, startDocument(), comes, the initial state is initialized and pushed into

5. Experimental Evaluation

the stack. When receiving an event startelement(tag), the5. 1 Setup

system follows the same rule as that in YFilter to get the

The algorithm is implemented using Java on the existingnext states and pushes into the stack. If the element is asso-

YFilter [5] and the SAX API from Xerces Java Parser in an

ciated with textual content, on receiving character() event,Intel Core 2.33GHz computer with 2GB of memory in Win-the system follows the same procedure to get the newly active

dows XP Service Pack 2. All data structures, query bitmaps

states. If none of the newly-active states are accepting states,and sets of used queries, are kept entirely in memory.

ablank query bitmap and set used query are created. If one

We use two types of datasets, synthetic data and real data.

or more newly-active states are accepting states, the posi-

Our synthetic data is generated by the xmlgen of XMark [3].

tions of the bitmap are obtained, and bitmaps of the newly-

Our real datasets are DBLP-biographic information on major

created query bitmap are set to true to the corresponding

computer science journals and proceedings, Mondial-world

obtained positions. The IDs of queries obtained from the ac-

geographic database integrated from the CIA World Fact-cepting states are added to the set used query. Then a newbook, the International Atlas, and the TERRA database.

entry is pushed into the stack.

Details of the datasets are presented in Table 1.
Table 1: All datasets used in the experiments
DatasetElement

Attributes

Max-depth Avg-depth

XMark

333 millions 333 millions

5

3

DBLP

3,332,130404,276

6

2.90

Mondial22,42347,4235

3.59

We generate XPath-based keyword search from the above
Fig. 8: A Single NFA

datasets. Since there is a performance impact when searching for diﬀerent kinds of keywords in our system, we separately generate sets of queries which contains only keywords
in the forms of l::, l, l::k, ::k and mixed of the four forms.
For example, we could generate: //regions[ftcontains(::begin::caius)], whose keywords are in the form of ::k from XMark
dataset. Moreover, since the same keywords can appear in
diﬀerent queries, we devide our sets of queries into two categories, sets of queries in which the same keywords can appear
in diﬀerent queries and sets of queries in which the same keywords cannot appear in diﬀerent queries.
We measure the elapsed time, average memory usage, andnumber of extended-NFA states for processing all XML dataon a given stream. This includes the time spent to create
the NFA, query bitmaps, and the set of used queries.
5. 2 Varying the Number of Queries

Fig. 9: A Running Example Proposed Method

We vary the number of queries from 1, 10, 100, 200, 400,

When receiving an event endelement(tag), the entry is

600, 800, and 1000 and investigate the impact on the per-popped of the stack. Then it checks the set used query offormance of our algorithm. We observe that as the number

the popped entry. If the used query is not empty, IDs ofof queries increases, the memory usage increases, and theeach query are used and it checks the bitmaps of the corre-

number of NFA states also increases while the throughputs

sponding queries in the query bitmap of the popped entry.

constantly decrease. As shown in Figures 10, 11, 12, 13, 14,

If all bitmaps of any queries are true, the respective queries

and 15. This is because the system needs to process eachmatch. Otherwise, they do not match. If none of queries

single query and output the result of each queries. Figure

match, all bitmaps of the query bitmap are sent and com-

10 shows that the number of NFA states increases when thebined with entry of the top stack by using "OR" operator.

number of queries increases from 1 to 100, but when the

The set used query of the popped entry is added up to that

number of queries increases from 100 to 1000, the number ofof the top entry.

NFA states becomes constant at 31 because same keywords

appear at diﬀerent queries very frequently and the numberof unique labels is only 31 in DBLP. Such cases also happen

7. Conclusion

to Mondial and XMark dataset as shown in Figures 11, andIn this paper, we have developed a filtering system that

12. We could not generate more than 100 queries in which

supports XPath-based keyword search over XML streams.

the same keyword appears only once in a particular query in

The NFA model is extended so that it supports XPath-based

the same set of queries. As a result, the increasse of memory

keyword search query. The above extended-NFA is used tousage and the decrease of throughputs do not change much

integrate the method in YFilter with that of CKStream.

when the number of queries increases.

We evaluate them by some experiments on both synthetic

5. 3 Varying the Number of Query Terms

and real datasets. The experimental results show that our

We investigate the impact on the performance of our algo-

proposed method works well with acceptable throughputs,

rithm when we increase the number of keywords from 2, 4,

less memory usage, and good eﬃciency and utility.

and 6. 6 keywords are a reasonable limit when one uses to

For our future work, we are going to apply our proposed

specify the query [8]. We randomly generate sets of queries

method, XPath-based keyword search, to multiple XML

whose same keywords can appear in more than one query.

streams, which useful information can be obtained when in-With these sets of queries, we observed that though theformations from diﬀerent sources are combined at real-time.

number of keywords increase, the memory usage, number ofextended-NFA states and throughputs do not change much

Acknowledgement

between 2, 4, and 6 keywords. These cause by the more

This work is partly supported by the collaborative researchfrequency that same keywords appear at diﬀerent queries as(Fujitsu Lab. Ltd., CPE25149), the Okawa Foundation re-shown in Figures 10, 11, and 12.

search grant, and JSPS KAKENHI (25330124).

Next we generate sets of queries in which the same key-

References

words appear at only one query in the same sets. Then

[1] Extensible markup language. www.w3.org/XML/, 2013.
[2] S. Amer-Yahia, E. Curtmola, and A. Deutsch. Flexible andeﬃcient xml search with complex full-text predicates. In
SIGMOD, pages 575–586, ACM New York, NY, USA, 2006.
[3] R. Busse, M. Carey, D. Florescu, M. Kersten, I. Manolescu,
A. Schmidt, and F. Wass. Xmark-an xml benchmark
project. http://www.xml-benchmark.org/, 2013.
[4] S. Cohen, J. Mamou, Y. Kanza, and Y. Sagiv. Xsearch:a semantic search engine for xml. In In Proc. Of VLDB,
volume 29, pages 45–56, 2003.
[5] Y. Diao and M. J. Franklin. High-performance xml filtering:
An overview of yfilter. In IEEE, pages 41–48, 2003.
[6] M. Gawinecki, F. Mandreoli, and G. Cabri. Keyword searchover xml streams: Addressing time-stamping and understanding results. pages 371–382, U. of Modena, 2008.
[7] V. Hristidis and N. Koudas. Keyword proximity search in
xml trees. IEEE Trans., 18:525–539, 2006.
[8] C. Hummel, S. da Silva, M. Moro, and Laender H.F. Multiple keyword-based queries over xml streams. In ACM, pages
1577–1582, ACM New York, NY, USA, 2011.
[9] A. Gupta J. Green and M. Onozuka. Processing xml stream
with deterministic automata and stream indexes. ACM,
29:752–788, 2004.
[10] F. Shao L. Guo, C. Botev, and J. S. Xrank: ranked keyword search over xml documents. In In Proc. Of SIGMOD
Conf., pages 16–27, ACM New York, NY, USA, 2003.
[11] Y. Li, C. Yu, and H. V. Jagadish. Schema-free xquery. In
VLDB, volume 30, pages 72–83, 2004.
[12] Z. Vagena, L. S. Colby, F. Ozcan, A. Balmin, and Q. Li. On
the Eﬀectiveness of Flexible Querying Heuristics for XML
Data, volume 4704. 2007.
[13] Z. Vagena and M. Moro. Semantic search over xml document streams. In DATAX, 2008.
[14] Y. Xu and Y. Papakonstantinou. Efcient keyword searchfor smallest lcas in xml databases. In In Proc. of SIGMOD
Conf., pages 527–538, ACM New York, NY, USA, 2005.
[15] C. Yu and L. Popa. Constraint-based xml query rewritingfor data integration. In In Proc. of SIGMOD Conf., pages
371–382, ACM New York, NY, USA, 2004.

we investigate the impact that the increase in unique keywords in the queries on the performance of the algorithm.
As expected, as the number of unique keywords increase,
the number of NFA states also increase. As a result, thememory usage increases and the thoughputs decrease significantly as shown in Figures 13, 14, and 15. Though memory
usage and throughputs of the algorithm have some degradation when the number of queries and the number of keyword
words increase, the algorithm scales well with such increase.

6. Related WorksXML Keyword Search: Using keywords to query XML
databases has been extensively studied. XSEarch [4] adopts
an intuitive concept of meaningfully related sets of nodes
based on the relationship of the nodes with its ancestors.
XRANK [10] presents an adaptation of Google’s PageRank
to XML data for computing a ranking score for the answer
trees. The work in [8] and [13] took the first steps towards
processing keyword-based queries over XML streams.
XML Streams: Recent research on XML streams (dissemination, ltering and routing) aims at building large-scale,
distributed systems [4, 5, 8, 9]. Most of those are concernedwith performance aspects and optimize the ltering process[9], the message delivering and the routing network. YFilter [5] uses NFA-based implementation to improve structure
matching and number of machine states are small. In orderto deal with multiple XML schemas, two approaches are very
common: to use query rewriting [15] and global schemas [11].

(a) Memory usage(b) Number of NFA states(c) Throughputs

Fig. 10: DBLP: Varying the number of queries and keywords of type l::(a) Memory usage(b) Number of NFA states(c) Throughputs

Fig. 11: Mondial: Varying the number of queries and keywords of type l::(a) Memory usage(b) Number of NFA states(c) Throughputs

Fig. 12: XMark: Varying the number of queries and keywords of type l::(a) Memory usage(b) Number of NFA states(c) Throughputs

Fig. 13: DBLP: Varying the number of queries and keywords of type ::k(a) Memory usage(b) Number of NFA states(c) Throughputs

Fig. 14: Mondial: Varying the number of queries and keywords of type ::k(a) Memory usage(b) Number of NFA states(c) Throughputs

Fig. 15: XMark: Varying the number of queries and keywords of type ::k