DEIM Forum 2016 A3-4

Eﬃcient Keyword Search over Relational Data 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†† Center for Computational Sciences, 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 Keyword search over relational streams plays an important role when enabling users to issue queries
without knowing the details about information sources as well as query languages. The state-of-the-art approaches
exploit Candidate Networks (CNs), which are high-level (or schema-level) representation of joining networks of tuples
containing all query keywords, to filter relational streams. However, in fact, the performance of these approaches
seriously degrades in particular when the maximum size of CNs (Tmax ) and/or the number of query keywords arelarge, due to the explosive increase in the number of CNs. To cope with this problem, this paper proposes a scalable
approach that consolidates all CNs in such a way that all common edges in the CNs can share processing, thereby
avoiding unnecessary evaluation of diﬀerent CNs as much as possible. The experimental results reveal that thequery execution time of the proposed approach greatly outperforms the comparative methods.
Key words Keyword Search, Relational Data Streams
they are merged to generate a query plan by which actual re-

1. Introduction

lational streams are processed. More precisely, in S-KWS [9],With the recent trends of Cyber Physical Systems [6, 11],a set of CNs are merged only if they share at least one leaf

Internet of Things [5,15], etc., the number of real-time infor-

node called root, and possible subtrees are merged to remove

mation sources has been explosively increasing. Besides, it

redundant processing as much as possible. In SS-KWS [13],has become common to extract information from various so-

common partial networks are merged more aggressively fromcial medias, such as Twitter, and Facebook, in real-time forevery leaf node of CNs, thereby generating more compact

making analysis of diverse social activities. Typically, eachquery plans.

data item generated at stream data sources can be modeled

However, it should be noted that the performance of S-

as structured records. For this reason, such data sources are

KWS and SS-KWS considerably degrades when the number

often called relational streams [3], where structured recordsof query keywords and/or network size (Tmax ) are increased.

that conform to some predefined relational schemas are con-

The increase of these two parameters causes rapid increase intinuously generated. Therefore, the importance of query pro-the number of CNs, which results in a lot of common partial

cessing over relational streams has been increasing.

networks remain unintegrated. To exemplify the problem, letProcessing keyword search over relational streams is con-us take TPC-H dataset [1] as an example. When the num-sidered to be a practical approach due to its user-friendliness,

ber of keywords and Tmax are increased from four to five, thewhich does not requires users to learn neither (potentially)

number of CNs increases from 3,600 to 85,803 [13]. Likewise,complicated query language, like CQL [3], nor the schemas

the total number of edges in the query execution plans expo-of streams being queried, which is also very complicatednentially increases from 4,276 to 73,596 in S-KWS and fromin many real applications.

So far, keyword search over

7,486 to 222,040 in SS-KWS. (More detailed discussion canpermanently-stored relational data [2, 7, 8, 10, 12] has been

be found in Section 5. 1.) Thus the performance of S-KWS

extensively studied, but only a few works have addressed

and SS-KWS would deteriorate in particular when dealing

keyword search over relational streams [9, 13].

with a lot of query keywords and/or large relational streams

In the works [9, 13], they employ candidate network-based

consisting of many relations.

approach for better performance. Specifically, all candidate

How can we cope with such exponential blow up of CNs

networks (CNs) that represent all possible combinations ofand the complication of query plans? If we consider the edges

keyword occurrences on join paths are enumerated. Then,in CNs, each of them actually represents primary/foreign-key—1—

relationships between two tables. For this reason, in the existing approaches, even though the number of edges grows at
an exponential rate, most of them, which are created fromsmaller number of primary/foreign-key relationships in the(a) Schema.

original schema, are actually redundant. With the same example above when the number of keywords and Tmax are
increased from four to five, the total number of unique edges
in all CNs grows linearly from 1,088 to 3,536. Under thisobservation, to cope with the problem of CN’s exponential
blow up, it is possible to consolidate the edges sharing thesame primary/foreign-key relationship into one edge when(b) Instances.

Figure 1 A sample e-commerce application.

generating a query plan, which leads to great performance
improvement.
This paper proposes a novel approach to processing keyword search over relational streams by taking into accountthe above idea. Specifically, an MX-structure is proposed
to consolidate common edges in diﬀerent CNs as much as
possible. The experimental results prove that the proposed
approach can process relational streams about 40 to 70 times

Figure 2 Some CNs created from schema in Figure 1(a) for query{k1 , k2 , k3 }.

faster than the state-of-the-art approaches when the numberof keywords and Tmax are increased to five.
This paper is organized as follow. We introduce related
works in Section 2.. Section 3. introduces existing worksof keyword search over relational streams, and the proposed
approach is in Section 4.. Experiments and conclusion are in(a) Cluster #1.

(b) Cluster #2.

(Combine the first two CNs.)(Only CN 3 is included.)

Section 5. and 6. respectively.
Figure 3 Operator mesh for CNs in Figure 2.

2. Related Works
So far, many proposals have been done to enable keyword

3. Keyword Search over Relational Streams

search on permanently-stored-relational data [2,4,7,8,12] andfew proposals on relational streams [9, 13].

3. 1 Problem Definition

DISCOVER [8] and DBXPLORER [2] are the CN-based

In this section we shall introduce keyword search on rela-

keyword search on (static) relational data. In DISCOVER

tional streams. First, we start our discussion from keyword[8], first all CNs are generated from the given keyword searchsearch on relational databases.

and relational data’s schema. Then, a plan is built for eﬃ-

As a common basis, graph representation of relational

cient evaluation of all CNs by reusing some common edges

database is used to define the semantics of keywordof CNs.

DBXPLORER-II [7] adopts IR-style document-

search [14]. In a data graph, each node represents a tu-

relevance ranking technique to keyword search over relationalple and an edge represents a primary/foreign-key reference

data. Since the total number of CNs can be very big, andbetween two tuples. Now, let us assume a relational schema

evaluation of all CNs is costly, [12] proposes an algorithm

and a database that conforms to the schema. Given a set

to rank all CNs, and only top-k CNs are chosen to evaluate

of user-specified query keywords, {k1 , k2 , . . . , kn }, keyword

against relational data.

search on the database is to find all minimal total joining

S-KWS [9] is the first work to enable keyword search over

networks of tuples (MTJNT) [8], each of which contains all

It is also a candidate network based

query keywords. More precisely, total means that all key-

approach, which makes use of common edge attached towords are contained in each network, and minimal meansroot nodes to elevate query searching. And the most recent

that removing any tuple from a network of tuples leads towork to enable keyword search on relational streams is SS-

loss of eligibility for query results. Notice that the maximum

KWS [13], which is proved to outperform S-KWS [9] whensize of data graphs is bounded by parameter Tmax .

relational streams.

most tuples from the relational data streams mostly match
CNs that have common edges at leaf-nodes.

In contrast to conventional relational data, relational
streams [3] can be modeled as possibly unbounded sequences—2—

of relational tuples. In other words, each tuple in a streamthat share the same root into a cluster. In fact, a CN can be

can be represented by a pair of 1) a relational tuple and 2)

converted into a corresponding operator tree, where the leaf

a time instant of a discrete and ordered time domain, e.g.,

nodes represent selection operators, in which their selection

integer. Thus tuples are regarded that they are arrived ac-

conditions may be null, and the internal nodes represent joincording to their timestamps. Figure 1 (a) and (b) illustrate

operators. By combining multiple CNs in a cluster, they con-a sample schema and its instances.

struct a data structure called operator mesh. Figure 3 shows

When dealing with (relational) streams, we often use slid-

two clusters of operator mesh created from the three CNs ining windows to convert an infinite stream of tuples to a re-Figure 2. It is important to notice that, for shared subtrees

lation of finite tuples. There are two types of sliding win-in the operator mesh, its process should be shared among

dows, namely, time- and tuple-based sliding windows. Givendiﬀerent CNs, thereby reducing the cost of query processing.

a window size either in term of time interval (e.g., 1 hour) or

When processing relational streams, all partial results arenumber of tuples (e.g., 100 tuples), it generates relations bycached in each operator’s buﬀer. Hence, in the case when

capturing the latest tuples within the window while sliding

some matches are detected in some CNs at the same time,

the window over the stream. In such window semantics, two

all matched tuples can be eﬃciently catched from the opera-

tuples can be joined only if both tuples are valid.

tor’s buﬀer. However, in fact, the idea of caching all partial

Having defined relational streams and sliding windows,

results in buﬀers causes a performance bottleneck due to its

keyword search over relational streams can be defined ashigh memory cost.

follows. Given a set of query keywords {k1 , k2 , . . . , kn }, a3. 3. 2 SS-KWS

maximum network size Tmax , and a window specification

SS-KWS [13] is a successor of S-KWS, and it can be re-

W , it continuously reports 1) new MTJNTs when new tu-

garded as the state-of-the-art approach. The novel idea ofples are delivered and 2) invalidation of existing MTJNTs

SS-KWS is to aggressively merge more sub-networks in CNs

due to deletion or aging of tuples.

not only at single leaf, but also at all leaves. Unlike S-KWS,

3. 2 Existing Worksthe root is the center node of the CNs. Besides, instead of

As mentioned in Section 1., S-KWS [9] and SS-KWS [13]operator mesh, a lattice is created by combining all CNs so

are the predecessors of this work. In this section, we briefly

that the query processing cost is reduced by sharing common

overview these works.

subtrees except for the root nodes in CNs as much as possi-

3. 3 Overview

ble. For example, the lattice structure for the three CNs in

In S-KWS and SS-KWS the process of keyword search on

Figure 2 is shown in Figure 4. In this example, nodes marked

relational streams comprises two main steps: preprocessing

with double lines are root nodes; black colored nodes are leafand evaluating steps.

nodes; and the rests are other non-leaf nodes.

•

In preprocessing step, given a schema, a set of query

SS-KWS proposes selection/semi-join approach to fully re-

keywords, and Tmax , all Candidate Networks (CNs) [9, 13]duce all partial results. The concept of semi-join approach(both linear and tree) are generated. Each node in a CN

works as follows. First, each node’s buﬀer is divided into

represents a relation, and the edges represent relational join

three sub-buﬀers: N (not joinable), W (waiting), and R

operation. Notice that all CNs must conform to the concept(ready). Figure 4 shows the lattice structure and all sub-of MTJNT [9]. Figure 2 shows three examples of linear CNs

buﬀers of node P . Probing sequence is clearly defined:from the schema in Figure 1(a).
••In non-leaf nodes, for each incoming tuple, all tuples

In evaluation step, keyword search over relationalin sub-buﬀers W or R of their child nodes are checked. If it

streams is actually processed by evaluating all CNs. Whenis not joinable with any tuple, the incoming tuple is stored

new MTJNTs are detected due to arrivals of new tuples, theyin sub-buﬀer N of its corresponding node, and the probing

are reported. On the other hand, expired tuples are removed

is finished. Else, the incoming tuple is stored in sub-buﬀer

by using either eager or lazy approaches [9].

W of its corresponding node, and the probing continues for3. 3. 1 S-KWS

the connected parent nodes. In leaf nodes, it immediately

S-KWS [9] is one of the pioneering works that addressedprobes parent nodes.

the problem of keyword search on relational streams using•

Similarly, in root nodes, for each incoming tuple, allCNs. In their work, for each CN, the root node is determined

tuples in sub-buﬀers W and R in the child nodes are checked,

such that 1) it is a leaf containing one chosen query keyword

and the incoming tuple is stored in the respective sub-buﬀers

and 2) the keyword has a higher selectivity in the streams

as explained above. If all branches are joinable, the detected

than other leaf nodes.

joining network of tuples (JNT) is emitted as a result, andTo improve performance, they propose to group all CNs

all tuples in the JNT are moved to sub-buﬀers R of the re—3—

scheme also exploits CN-based approach, but tries to improve the performance by the following ideas: 1) given a setof CNs, we generate a maximal sharing structure called MXstructure by consolidating all shared edges in CNs regardlessof their positions in CNs (i.e., root or leaf); and 2) we try
to avoid duplications of tuples in buﬀers in MX-structure.
More precisely, the former is achieved by maintaining inforFigure 4 Lattice for CNs in Figure 2.

mation about the edges and their corresponding CNs using
tables called edge-mapping table. The latter is achieved byintroducing a new data organization in each node buﬀer. To
operate with sliding windows, lazy approach [9] is used todeal with dead tuples.
4. 2 MX-StructureFirst, we introduce the proposed MX-structure. In eachCN, the root (and the output node as well) is determined(a) MX-structure.

(b) Edge-mapping (c) Sub-space in nodeas the center of the CN. Then, all CNs are merged in suchtable.

a way that all edges are unique; i.e., edges in MX-structure

PS{}.

Figure 5 MX-structure for CNs in Figure 2.

are created only for diﬀerent combinations of nodes regardless of the node’s position (root or leaf). Such information

spective nodes.

needs to be maintained as well. (In the sequel discussion, we

3. 4 Scalability Issues in Existing Approaches

denote by () a leaf node and by [] a root node.) We also

We discuss the scalability issues of these approaches. As

maintain in the edge-mapping table the information of edge

a common problem, the number of CNs grows exponentiallyas the number of keywords and/or Tmax increase. This gives
a significant impact on both time and space.

occurrences in diﬀerent CNs.
Due to the space limitation, we cannot show the algorithm,
but it can be constructed in the following way. Basically, all

In S-KWS, partial results are maintained in the buﬀers in

CNs are processed and added to an MX-structure one by one.

an operator mesh. Due to the low sharing rate of common

When adding a new CN, we take each edge, and check its

subtrees in CNs; i.e., in an operator mesh, we can find a lot

existence; we only add one only if it has not been added yet.

of common edges shared by diﬀerent CNs but are not con-

Next, we insert the ID of the edge’s CN to the edge-mapping

solidated, because they are either in diﬀerent clusters or dotable. The information about each CN’s root and leaf nodes

not have same root node. Consequently, in query processing,is also maintained.

a lot of partial results need to be duplicated in buﬀers andneed also to be processed independently.

Figure 5(a) illustrates an example of MX-structure for theCNs in Figure 2. Nodes marked with double lines show root

In SS-KWS, the problem of the low sharing rate of com-nodes, and black nodes are leaf nodes. The label on eachmon subtrees is mitigated by sharing common subtrees inedge represents the set of corresponding CNs in term of IDs.

all possible subtrees. However, there still exists a restriction

Table 5(b) is its edge-mapping tables.

that it is impossible to consolidate common paths in inter-

4. 3 Query Evaluation in MX-Structure

nal nodes, because 1) sharing is only allowed for common

4. 3. 1 Node Buﬀers

subtrees; and 2) root nodes are not allowed to be shared.

To enable eﬃcient query evaluation using MX-structure,

Therefore, the number of common paths that are not consol-

we propose a novel data organization in each node buﬀer.

idated in lattice grows rapidly as the number of CNs grows.

Our idea is based on the sub-buﬀer proposed in SS-KWS [13].

For the same reason discussed above, such duplicated paths

In an MX-structure, each node is associated with a buﬀer,

cause high memory consumption in internal buﬀers and also

which is further divided into two sub-buﬀers, N and WR.

cause high computational cost for possibly useless processing

Sub-buﬀer N is for storing tuples that are not joinable withof (duplicated) intermediate results.

tuples in child nodes, while sub-buﬀer WR is for storing tu-

4. Proposed Approach

ples that are partially matched (not part of the completed
query results yet) or fully matched (as part of the completed

4. 1 Overview

query results) in some JNTs. Moreover, sub-buﬀer WR of

In this section, we propose a novel approach to process-each node is further divided into sub-spaces for each CN anding keyword search over relational streams. The proposed

for all possible combinations of all CNs containing that node.
—4—

We use ∼n to denote fully matched to in CN n. If there isprobed. Since tuple t1 can be joined with t5, a new sub-spaceno ∼ (i.e., n), it means it is partially matched in CN n. Fig-

cnepsubspace is computed by Equations (1) and (2). Then, weure 5(c) shows the buﬀer of node P S{} in the MX-structure.

get cnedge = {1, 2}, cnleaf = {1, 2}, and cnecsubspace = {}.

As shown in the figure, node P S{} appears in CNs 1, 2, andAs a result, we get cnactive = {1, 2}. So, we create new

3. Therefore, sub-spaces for these CNs are created in sub-sub-spaces cnepsubspace = {1, 2} in sub-buﬀers WR of nodes

buﬀer WR. Sub-space {1, 2} is for storing tuples that are

C{k1} and P S{} (Figure 6(b)). Thus, t1 and t5 are moved

partially matched for CNs 1 and 2. Sub-space {∼1, ∼2, 3}

to sub-space {1, 2} of sub-buﬀer WR of nodes C{k1} andis for storing tuples that are fully matched for CNs 1 and 2,

P S{}, respectively. Since the coming tuple t5 is joinable

and partially matched for CN 3.

with tuple in child node, it continues to probe parent nodes.
Before probing parent nodes, P {} and C{}, the set of

4. 3. 2 Probing Sequence
Probing sequence in MX-structure is explained as fol-

active CNs are computed by Equation (1) as follows. For

lows. Suppose a tuple arrives to a non-leaf node in an MX-

edge P S{} − P {}, we get cnedge = {1, 2}, cnleaf = {},structure. First, all tuples in sub-buﬀers N and WR of theand cnecsubspace = {1, 2}.

child nodes are probed if the child nodes are at the leaf level;

cnactive = {1, 2} is not empty, the parent node P {} will beotherwise, only tuples in sub-buﬀers WR are probed. Sec-probed, while, for edge P S{} − C{}, we have cnedge = {3},ond, if there exist some tuples that are joinable, all sub-cnleaf = {}, and cnecsubspace = {1, 2}.

buﬀers of the parent nodes are probed. If a new tuple arrives

cnactive = {}. Because cnactive is empty, the parent nodeat one of the leaf nodes, the parent nodes are immediately

C{} will not be probed. Since t2 can be joined with t5, andprobed. Unlike SS-KWS, probing is only performed to par-node P {} is the root node for both CNs in cnactive (= {1, 2}),

ent nodes that belong to set of active CNs, which are the CNs

a couple of branch maps (branch map) are created for boththat have joinable tuples from their respective leaf nodes up

CNs, and the first bit is set to 1 in both maps. A branch map

to the node of the probing tuple (being used to probe tuples

is to maintain the status of the CN whether the branches up

at parent nodes).

to the root is connected or not (Figure 6(b)).

So, cnactive = {1, 2}.

Since

Then, we get

Active CNs are identified by 1) the IDs assigned to a con-Same procedures are performed when t6 arrives (Fig-nected edge (cnedge ) being traversed, 2) the IDs assigned to

ure Figure 6(c)), which results in the match of anothera leaf node (cnleaf ) if the child node is a leaf, and 3) the IDs

branch in CN 2. Since all bits of CN 2 are set, CN 2 isof non-empty sub-spaces (cnecsubspace ) in the child node, anddetected as matched. Therefore, all matched tuples are re-is calculated by the following formula:turned as a query result. Then, they are moved to appro-

cnactive = cnedge ∩ (cnleaf ∪ cnecsubspace )(1)

Having finished probing tuples in child/parent nodes, thepriate sub-spaces as shown in Figure 6(d) for subsequent
processing.
4. 4 Algorithm Details

probed tuple may be moved to appropriate sub-spaces ac-

The proposed algorithm is shown in Algorithm 1. This

cording to matching status. In fact, in our approach, sub-algorithm works as follows. If the newly-arrived tuple, t0 ,spaces are dynamically created in an on-demand manner; i.e.,

belongs to a leaf node, it probes the parent nodes (Line 5)

if there exists an appropriate sub-space, we just use it; oth-by calling function Probe_parent_nodes. For each parent

erwise, we create a new sub-space according to the following

node, cnactive is calculated by Equation (1). If cnactive is notformula:empty, it continues to check sub-buﬀers N and W R (Linescnnpsubspace = cnepsubspace ∪ cnactive(2)2–3). For each sub-space in sub-buﬀer W R, cnnpsubspace iscalculated by Equation (2) (Line 4). If one or more tuples

where cnnpsubspace and cnepsubspace are respectively the new

in the sub-space can be joined with t0 , we create a new sub-sub-space and the existing sub-space marked by IDs of CNs

space cnnpsubspace if necessary (Lines 5–6).
Then it checks if any CN in cnactive is fully matched byfor the probed tuples at parent nodes.
Note that, if cnepsubspace is not empty, all tuples incalling function Match_CN (Line 7). This function checks eachcnepsubspace are already used to probe the parent nodes. In

CN in cnactive to update the branch map. It is the map, at-this case, probing parent nodes again can be performed eﬃ-

tached to each tuple in the nodes with more than one child

ciently, because only tuples in cnepsubspace need to be probed.

nodes for the same CN (Line 2). If the parent node is theFirst,

root node of the CN, and if all bits in the branch map forwhen tuple t5, which belongs to node P S{}, arrives (Fig-the CN are set to 1, the CN is detected to be fully matchedure 6(a)), its child nodes (leaf nodes C{k1} and P {k1}) are(Line 4). Hence, all related fully-matched tuples are out-probed. Since node P {k1} is empty, only node C{k1} isput as query results (Line 5). In addition, new sub-space

Let us take a look at Figure 6 as an example.

—5—

Algorithm 1 Candidate Networks (CN) Evaluation
Input: Tuple t0 just from streams, MX-structure M X(a) Read t5.

(b) Create branch map for CNs
1 and 2.

(c) Update branch map for CN (d) Select matched tuples for CN
2.

2.

Figure 6 Query processing using MX-structure. Let tuples t1,
t2, t3, and t4 are currently maintained in Figure 6(a),and let all tuples joinable together, except t4.

for each selected tuples is created if necessary by copying its
current sub-space and updating CN to ∼CN (Line 6) to indicate that the new sub-space is for storing the tuples thatare fully matched to the CN. Then, it moves the matchedtuples into respective new sub-spaces (Line 7). At the sametime, cnnpsubspace for the parent node needs also to be updated from CN to ∼CN (Line 9). After the call of function
Match_CN, we go back to function Probe_parent_nodes, store
t in sub-space cnnpsubspace , and t1 is put in the set sjtp for

1: put t0 in set joint tuples
2: if t0 from leaf nodes then3:
while 1 do
4:
while each t in set joint tuples do
5:sjtp = Probe parent nodes (t, sjtp, M X)
6:
end while7:
if sjtp is empty then8:
break;
9:else
10:
set joint tuples = sjtp
11:
clear sjtp
12:
end if13:
end while
14: else
while each t in set joint tuples do
15:
16:
Probe child nodes (t, M X)
17:
if t joinable then18:
while 1 do
19:
while each t in set joint tuples do
20:
sjtp = Probe parent nodes (t, sjtp, M X)
21:
end while22:
if sjtp is empty then23:
break;
24:else
25:
set joint tuples = sjtp
26:
clear sjtp
27:
end if28:
end while29:
end ifend while30:
31: end if

Function: Probe child nodes (t, sjtp, M X)
1: while Each child nodes do
2:joinable = false3:
if cnactive not empty then4:
while Each sub-space in W R do
5:
Calculate cnnpsubspace
if tuple t1 joinable then6:7:joinable = true
8:
Matched CN (CN , cnactive , cnnpsubspace , branch map,

node of t, MX)
9:
Put t in cnnpsubspace10:
put t1 in sjtp
11:
end ifend while
12:
13:
end if14:
if joinable == true then15:
Update branch map for CN s in cnactive
16:
end if
17: end while
18: Return sjtp

subsequent probing to parent nodes.
Back to the main algorithm (Line 5), Probe_parent_nodes
returns sjtp.

If sjtp is not empty, it will call function

Probe_parent_nodes again for probing subsequent parent
nodes; otherwise, the loop is finished (Lines 7–12).
If the new tuple t0 does not belong to leaf nodes (Line 14),
it will call function Probe_child_nodes by following similar
procedure above (Lines 14–31).
4. 5 Discussion
In this section we elaborate the reason why the proposed
scheme is advantageous to the existing approaches. As we observed, the number of CNs exponentially increases as query
keywords and/or the size of CNs grows. Consequently, eventhough S-KWS and SS-KWS try to merge the CNs by finding common sub-networks, the size of query plans rapidly

grows, which leads to poor performance.
In MX-structure, we attempt to integrate diﬀerent CNs
more aggressively by consolidating edges according to thenodes at the both ends. Thus we can avoid the exponential
blow up in query plans.
Readers may think that the complication is just migrated
to the management of edge-mapping tables and complicated sub-buﬀers. This is partly true, but the point is thatthe number of CNs that are actually activated against real
streams is far smaller than the possible combinations due tothe locality in real data. Therefore, the cost for maintainingedge-mapping table and sub-buﬀers is expected to be modest. We confirm this in the following experiment.

—6—

Function: Probe parent nodes (t, sjtp, M X)
1: while Each parent nodes do2:
if cnactive not empty then3:
while N and each sub-space in W R do
4:
Calculate cnnpsubspace
5:
if tuple t1 joinable then6:
Create cnnpsubspace if not exist

5. 1 Edge CountFirst, we compared the number of edges in the query plansof all approaches, which significantly aﬀects the performance.
As can be seen in Figure 7, when the number of query
keywords and Tmax increased, the total number of edges

Matched CN (CN , cnactive , cnnpsubspace , branch map,in S-KWS and SS-KWS was exponentially increased, which
node of t, M X)
was caused by the explosion of number of CNs whose edges
8:
Put t in cnnpsubspace9:
put t1 in sjtp
could not be consolidated in their query plans. However, the10:
end ifgrowth rate of the proposed scheme was linearly increased11:
end while
12:
end ifbecause it consolidated unique edges into one, and the total
13: end while
14: Return sjtp
number of unique edges, which were the primary/foreign7:

Function: Matched CN (CN , cnactive , cnnpsubspace , branch map,node, M X)
1: while Each CN in cnactive do
2:Update branch map of that CN
3:
if Parent node is root node then4:
if All bits in branch map set to 1 then5:
Select all matched tuples
6:
Copy sub-space of matched tuple, and update CN

increased as the number of CNs increased.

to ∼CN .

Create that new sub-space if not exist, and move
matched tuple in it.
8:
Return all matched tuples as result
Update CN to ∼CN in cnnpsubspace
9:10:
end if11:
end if
12: end while
13: Return (cnnpsubspace , branch map, All buﬀers in MX)
7:

key relationships between two tables, in all CNs was slightly(a) # keywords = 2.

(b) # keywords = 3.

(c) # keywords = 4.

(d) # keywords = 5.

Table 1 Parameters used in the experiments.
Parameter

Range and default

Window size (mn)

10, 20, 30, 40, 50

Keyword frequency (%) 0.003, 0.007, 0.01, 0.013# of keywords

2, 3, 4, 5

Tmax

2, 3, 4, 5

Figure 7 Comparison of number of edges.

5. 2 Performance Comparison
We compared CPU running time and memory usage. No-

5. Experiments

tice that this dataset is specially prepared to favor SS-KWS
to S-KWS.

In this section we report the experimental results toFirst, we measured the CPU running time and memory

demonstrate the performance of the proposed scheme. As

usage when varying the number of keywords (Figures 8(a)comparative methods, we implemented full mesh (FM) andand 8(b), respectively). As can be seen, CPU running time

partial mesh (PM) of S-KWS [9], SS-KWS [13], and the pro-and memory usage in FM/PM and SS-KWS were increased

posed approach in C++ language.

exponentially, whereas the proposed scheme was not. ThisTo generate relational streams, we read datasets from theis due to the reason as developed above that an explosive

disk, and fed them in the implement systems. All experi-increase in number of edges in the query plan of S-KWS

ments were performed using 8-way Intel Core i7 CPU 870

and SS-KWS causes an exponensial increase in number of(2.93 GHz) with 31.4 GiB memory running Ubuntu 13.10.

probings in FM/PM and SS-KWS. Similar tendency can be

We used both synthetic and real datasets. Due to lack ofobserved when varying Tmax from 2 to 5 (Figure 9).

space, only the result of synthetic dataset is presented. For

Next, we increased the size of window from 10 min to 50

synthetic dataset, we used TPC-H [1], which deals with ad-

min. As expected, when the size of window was increased,

hoc decision support system in business environment. In thisthe CPU running time and memory usage also increased asdataset, there are eight tables with 61 attributes.

shown in Figure 10. This was because fewer tuples in the

Parameters used in the experiments are shown in Table 1.

buﬀers of all approaches were expired and deleted as a re-

We varied these parameters and compared the performance

sult of the increase in size of window. Nevertheless, the to-of the proposed algorithm, S-KWS and SS-KWS. The default

tal number of CNs did not increase when increasing window

parameters are written in bold.

size, which caused little impact on the performance of all—7—

We had conducted several experiments by varying typesof datasets of both real and synthetic datasets and experimental parameters. The experimental results prove that the
proposed algorithm can handle the processing of keyword
search over relational streams much better than all state(a) CPU running times.

(b) Memory usage.

Figure 8 Varying # of keywords.

of-the-art approaches both CPU running times and memory
usage. The proposed algorithm can process keyword searchover relational streams in average about 40 to 70 times fasterthan the state-of-the-art approaches when the number ofquery keywords or Tmax are increased up to five.

Acknowledgement
This work was supported by JSPS KAKENHI Grant Num(a) CPU running times.

(b) Memory usage.

Figure 9 Varying Tmax .

(a) CPU running times.

(b) Memory usage.

Figure 10 Varying window size.

(a) CPU running times.

(b) Memory usage.

Figure 11 Varying keyword frequency.

approaches.
Figure 11 shows the impact on the performance of all
approaches when varying keyword frequency in the dataset
from 0.003%, 0.007%, 0.01% to 0.013%. When keyword frequency was increased, there were more tuples containing the
keywords of the query. As a result, there were more tuples
that need to be joint. Moreover, increasing keyword frequency did not cause any increase in total number of CNs.
As a result, the increase in keyword frequency did not havemuch impact on the performance of all approaches.

6. Conclusion
In this paper, we had proposed a novel approach to eﬃciently process keyword search over relational streams. We
had proposed a compact maximal sharing structure, MXstructure, which enables the sharing of any common edges
among all CNs. We had also proposed a very eﬃcient algo-ber 26280037.
References[1] Tpc-h benchmark dataset. http://www.tpc.org/tpch/, 2015.
[2] S. Agrawal, S. Chaudhuri, and G. Das. Dbxplorer: A system for keyword-based search over relational databases. In
ICDE, 2002.
[3] A. Arasu, B. Babcock, S. Babu, J. Cieslewicz, M. Datar,
K. Ito, U. Srivastava, and J. Widom. STREAM: The Stanford data stream management system. Technical Report,
Stanford InfoLab, http://ilpubs.stanford.edu:8090/641/,
2004.
[4] A. Arasu, S. Babu, and J. Widom. Cql: A language for continuous queries over streams and relations. In Workshop,
DBPL 2003, Potsdam, Germany, 2003.
[5] M. Dyk, A. Najgebauer, and D. Pierzchala. Agent-based msof smart sensors for knowledge acquisition inside the internet of things and sensor networks. ACIIDS, 9012:224–234,
2015.
[6] L. Edward. Cyber physical systems: Design challenges.
University of California, Berkeley Technical Report No.
UCB/EECS-2008-8. Retrieved 2008-06-07, 2008.
[7] V. Hristidis, L. Gravano, and Y. Papakonstantinou. Eﬃcient ir-style keyword search over relational databases. In
VLDB, 2003.
[8] V. Hristidis and Y. Papakonstantinou. Discover: Keyword search in relational databases. In VLDB, Hong Kong,
China, 2002.
[9] A. Markowetz, Y. Yang, and D. Papadias. Keyword searchon relational data streams. In SIGMOD, Beijing, China,
2007.
[10] K. Mehdi, A. Aijun, C. Nick, G. Parke, S. Jaroslaw,
and Y. Xiaohui. Meaningful keyword search in relational
databases with large and complex schema. In ICDE, Seoul,
Korea, 2015.
[11] O. Niggermann and V. Lohweg. On the diagnosis of cyberphysical production systems. In AAAI, Texas, USA, 2015.
[12] O. Pericles, S. Altigran, and M. Edleno. Ranking candidate networks of relations to improve keyword search overrelational databases. In ICDE, Seoul, Korea, 2015.
[13] L. Qin, J. Xu Yu, and L. Chang. Scalable keyword searchon large data streams. In VLDB Journal, 2011.
[14] D. Shaul, E. Gadi, G. Shai, and P. Eran. DTL’s DataSpot:
Database exploration using plain language. In VLDB, San
Francisco, CA, USA, 1998.
[15] H. Zhang, C. Sanin, and E. Szczerbicki. Experience-oriented
enhancement of smartness for internet of things. ACIIDS,
9012:506–515, 2015.

rithm to process MX-structure over relational streams.

—8—