DEIM Forum 2014 D3-3

305-0001
E-mail:1-1-1

305-0001
1-1-1
m1_nisimura@kde.cs.tsukuba.ac.jp,
kawashima@cs.tsukuba.jp()
AIS
PATTERN

1.
WITHIN

FROM

WHERE

4PATTERN
FROM
WHERE
WITHIN<event pattern><input stream><filtering conditions><window>

PATTERN

FROM
SASE[15][8]
15[1 2 3WHERE

7]PATTERNWITHINSASE[15]

Cayuga[6]ZStream[2]

RFID
SASE
SASE
(Nondeterministic Finite
Automaton NFA)PATTERN
FROM
WHERE
WITHIN

SEQ(AB)

SEQ (A, B)
PacketStream
A.dstport = 80 AND B.dstport != 80
500 events

AB
A

NFA

B
FROM

PacketStream

AIS(Active Instance Stack)

IP

NFA
AIS

IP

NFA
AIS

PacketStream
IP
WHERE
dstportA.dstport = 80 AND B.dstport != 80

180
80
WITHIN 500 events
[8]

CQL

[ROWS500]
GigaScope[14]ATT

XStream[13]uCosminexus Stream Data Platform[19], Microsoft
SQL Server StreamInsight[15, 18]
SASE

2Oracle CEP[16]EsperTech[17] System S[20]
SASE

SASE
SASE

[24]

FLA(Forward Link Aggregation)
FLA

SASE[1FLA

5]

Cayuga[6]ZStream[2]

4.1
[22]
PRC(Partial Result[23]Caching)[23]2SASE

122006NFA

ZStream[2]

NFA

3

SASE
45

3. FLA (Forward Link Aggregation)[24]
FLA(Forward Link Aggregation)

2.

FLA
SASE[1]

1
FLA

[4]

STREAM[8]Aurora[11] Borealis[12] NiagaraCQ[10] TelegraphCQ[9]

4

FLA

準備

3.1.

most Recent Instance in the Subsequence stack)
9SEQ(AB

D)

a1

FLA

d9

AIS
2

a1

d9
2

a1, c2, b3, a4, d5, b6, d7, a8, d9

a1b3b3d5
12c2

C
2
[1 5]

1

skip till next match<a1b3d5>

c2
2: RIS
FLA

STEP3

AIS

FLA123.2.

FLA の 手 続 き

3.2

FLA

STEP42

3.14

RIS
a1b6

STEP1

SEQ(A1NFA

B

1D)
*[1]

b6d9
<a1b3

<a4b6d7>

b6d9>

7

STEP5

FLAd5><a1<a1b3b3d7><a1b6d7>

d9><a1b6d9>

<a4

NFA
NFA

NFA

AIS
d5d7d9

3

1:
STEP2

NFA

NFA

AIS(ActiveInstance Stack)

AIS
NFA
3:

AIS

AIS

FLA
STEP6
1AIS

a1
a1

a4b3b3RIS(theRIS
4Result Caching)
FLA

4:

a1b3

PRC
1FLA

STEP6

STEP2a4

AIS

FLA
d12
AIS5AISd12
4.3.

PRC の 処 理 手 順
SEQ(ABD)9
PRC
a1, c2, b3, a4, d5, b6, d7, a8, d9, b10, d11, d12, b13
5:

d12

STEP1
AIS

4.
4.1.

PRC

FLA の 問 題 点

3AIS
RIS

FLA
RIS

21

RIS

1

12
AIS

a1d9
3.2d11
2d7>

STEP3<a4NFA2b6d11><a4b6<a4 b6 d11>

STEP2

<a4b6>(a4STEP3b6)

NFA

AIS
22

FLA

STEP4-1
RIS

FLA
RIS
34.2.
4.1

部分的パタンオカレンスのキャッシュ構築
PRC(Partial

STEP4-2

STEP4RISNFA
66ASTEP4-19:

STEP4-2

a1

STEP6

STEP1a4AIS
d12
AIS

10d12AISSTEP26:

STEP5NFA

AIS
NFA
RIS

b6d5a4d7

AIS
2b3d9

a110:

d12

RIS
7

STEP2’
3AIS

10d11d12b62<a47: NFA

AIS

b6d11 >

<a4b6

AIS
1

STEP6(NFA
a1AIS)
a1<a1<a1 b3>

b6>

a1

AIS

8

STEP3’

NFA

10

a4

AIS

9RIS

a8

RIS
1

a4118:a1

AIS

a8d12 >

SEQ

11:

a4a8

STEP4-1’4< a8>b10< a4d11 >b10< a8b10d12 >< a4b10d11d12 >STEP4-2’
NFA12
STEP4-1

STEP4-2

12:
STEP5’NFAAISb10a8d11d12a4

RIS

STEP6’

NFA(a4AIS)
a4b6>
PRC

<a4<a4b10>

STEP1

STEP6FLASTEP211PRC
55.

FLA

PRC

[1] Eugene
Wu,
Yanlei
Diao,
ShariqRizvi,“High-Performance Complex Event Processing overStreams”, Proceedings of the 2006 ACM SIGMODInternational Conference on Management of Data,
Illinois, USA, pp.407 -418, June. 2006.
[2] Yuan Mei, Samuel Madden, “ZStream: A Cost -based
Query Processor for Adaptively Detecting Composite
Event”, Proceedings of the 2009 ACM SIGMODInternational Conference on Management of Data,
Rhode Island, USA, pp.193 -206, June-July. 2009.
[3] Xin Li, Hideyuki Kawashima, Hiroyuki Kitagawa,“Complex Event Processing over Uncertain Data
Streams”, The 70th National Convention of IPSJ,Ibaraki, Japan, March. 2010.
[4] H. Garcia-Molina, J.D. Ullman, and J. Widom,“Database S ystems - The Complete Book Secondedition”, Prentice Hall Press Upper Saddle River,USA, June. 2008.
[5] Yanlei Diao, Neil Immerman, Daniel Gyllstorm,“SASE+: An Agile Language for Kleene Closure overEvent Streams”, UMass Technical report 07 -03,
University of Massachusetts, Amherst, March. 2007.
[6] Alan Demers et al, “Cayuga: A General Purpose
EventMonitoring
S ystem”,
ProceedingsofConference on Innovative Data Systems Research
2007, Asilomar, CA, pp.412 -422, January. 2007.
[7] Zhitao Shen, Hideyuki Kawashima and Hiroyuki
Kitagawa, “Efficient Probabilistic Event Stream
Processingwith
LineageandKleene -plus”,
International Journal of Communication Networks
and Distributed Systems, Vol. 2, No.4 pp.355 -374,June. 2009.
[8] Arasu, A., Babu, S., and Widom, J. 2004. “The CQL
Continuous Query Language: Semantic Foundations
and Query Execution”, The VLDB Journal, vol.15,no.2, pp.121-142, June. 2006.
[9] Chandrasekaran, S., Cooper, O., Deshpande, A.,Franklin, M. J., Hellerstein, J. M., Hong, W.,
Krishnamurthy, S., Madden, S. R., Reiss, F., andShah, M. A. 2003. “TelegraphCQ: ContinuousDataflow Processing”, Proceedings of the 2003 ACM
SIGMOD International Conference on Managementof Data, San Diego, CA, pp.668 -668, June. 2003.
[10] Chen, J., DeWitt, D. J., Tian, F., and Wang, Y.
“NiagaraCQ: a Scalable Continuous Query System
for Internet Databases”, Proceedings of the 2000
ACM
SIGMOD international
conferenceonManagement of data, Dallas, TX, pp.379 -390, June.
2000.
[11] Balakrishnan, H., Balazinska, M., Carney, D.,Çetintemel, U., Cherniack, M., Convey, C., Galvez,
E., Salz, J., Stonebraker, M., Tatbul, N., Tibbetts, R.,
and Zdonik, S. 2004. “Retrospective on Aurora”. The
VLDB Journal, vol.13, no.4, pp.370 -383, December.
2004.
[12] Daniel J. Abadi, Yanif Ahmad, Magdalena Balazinska,
Ugur Cetintemel, Mitch Cherniack, Jeong -Hyon
Hwang, Wolfgang Lindner, Anurag S. Maskey,Alexander Rasin, Esther Ryvkina, Nesime Tatbul,

Ying Xing, and Stan Zdonik, “The Design of theBorealis Stream Processing Engine”, Proceedings ofConference on Innovative Data Systems Research
2005, Asilomar, CA, pp.277 -289, January. 2005.
[13] Girod, L., Mei, Y., Newton, R., Rost, S., Thiagarajan,A., Balakrishnan, H., and Madden, S. “XStream: aSignal-Oriented Data Stream Management System”,
Proceedings of 24th IEEE International Conferenceon Data Engineering, Cancun, Mexico, pp.1180 -1189,April. 2008.
[14] Cranor, C., Johnson, T., Spataschek, O., andShkapen yuk, V. “Gigascope: a Stream Database for
Network Applications”, Proceedings of the 2003
ACM SIGMOD International Conference on
Management of Data, San Diego, CA, pp.647 -651,
June. 2003.
[15] Microsoft, “Microsoft SQL Server StreamInSight”,
http://www.microsoft.com/sqlserver/2008/en/us/r2 -c
omplex-event.aspx, accessed August. 2013.
[16] Oracle,“OracleCEP”,
http://www.oracle.com/us/technologies/soa/service -oriented-architecture-066455.html, accessed August.
2013.
[17] EsperTech
Inc.,“EsperTech”,
http://www.espertech.com/, accessed August. 2013.
[18] Chandramouli, B., Goldstein, J., and Maier, D.
“On-the-fly Progress Detection in Iterative StreamQueries”, Proceedings of VLDB Endowment, vol.2,no.1, pp.241-252, August. 2009.
[19] Hitachi,Ltd., “Real -Time Log Analysis Using HitachiuCosminexus
Stream
DataPlatform”,
http://www.hitachi.com/products/it/software/prod/ cosminexus/index.html, accessed August. 2013.
[20] Gedik, B., Andrade, H., Wu, K., Yu, P. S., and Doo,
M. 2008. “SPADE: The System S Declarative Stream
Processing Engine”, Proceedings of the 2008 ACM
SIGMOD international conference on Management ofdata, Vancouver, BC, pp.1123-1134, June. 2008.
[21] Barzan Mozafari, Kai Zeng, and Carlo Zaniolo,“High-performance Complex Event Processing overXML streams”, Proceedings of 2012 ACM SIGMODInternational Conference on Management of Data,
Arizona, USA, pp.253-264, May. 2012.
[22] Thanh T. L. Tran, Liping Peng, Yanlei Diao, Andrew
McGregor, Anna Liu, “CLARO: Modeling andProcessing Uncertain Data Streams”, The VLDB
Journal, vol. 21, no. 5, pp. 651 -676, October. 2012.
[23] Medhabi Ra y , Elke A. Rundensteiner , Mo Liu ,Chetan Gupta , Song Wang , Ismail Ari,
“High-performance Complex Event Processing usin gContinuous Sliding Views”, Proceedings of 16th
International Conference on Extending Database
Technology, Genoa, Italy, pp. 525 -536. March. 2013.
[24] Naotaka
Nishimura,
Hideyuki
Kawashima,
Accelerating CEP with Link Aggregation and Bulk
Evaluation,
IPSJ
Transaction
onDatabase.(Conditional Acceptance)