University	  of	  Tsukuba	  	  | Center	  for	  Computational	  SciencesDatabase	  GroupArchitecture	  for	  Stream	  OLAP	  Exploiting	  SPE	  and	  OLAP	  Engine
Explosive increase of real-­‐time data streams gives highly demands for real-­‐time analysis over the streams. However,developing tailor-­‐made systems for such applications is not always desirable due to high developing costs. To cope with thisproblem, we propose a novel architecture for online analytical processing (OLAP) over streams exploiting off-­‐the-­‐shelfstream processing engine (SPE) combined with OLAP engine. It allows users to perform OLAP analysis over streams for thelatest time period, called Interval of Interest (IoI). The system in the meantime processes multiple continuous querylanguage (CQL) queries corresponding to different aggregation levels in cube lattice. To cover arbitrary aggregation levels
using limited system's memory, we propose to partially deploy CQL queries for those with higher reference frequencies,
whereas the results are dynamically calculated using existing aggregation results with the help of OLAP engine. For optimal
CQL query deployment, we propose a cost-­‐based optimization method that maximizes the performance. The experimental
results show that the proposed system significantly outperforms other comparative methods.

FemaleFig.	  1:	  Architecture	  of	  Stream	  OLAP	  system

Age:	  1 0≤	  n	  <15Fig.	  2:	  Stream	  OLAP	  system	  analyzing	  “People	  Flow	  Data”

Parallel	  Canopy	  Clustering	  on	  GPUs

Canopy clustering is a preprocessing method for standard clustering algorithms such as k-­‐means and hierarchicalagglomerative clustering. Canopy clustering can greatly reduce the computational cost of clustering algorithms. However,canopy clustering itself may also take a vast amount of time for handling massive data, if we naively implement it. To
address this problem, we present efficient algorithms and implementations of canopy clustering on GPUs, which have
evolved recently as general-­‐purpose many-­‐core processors. We not only accelerate the computation of original canopy
clustering, but also propose an algorithm using grid index. This algorithm partitions the data into cells to reduce redundant
computations and, at the same time, to exploit the parallelism of GPUs. Experiments showParallelthat Canopy
the proposedClustering on GPUs
implementations on the GPU is 2 times faster on average than multi-­‐threaded, SIMD implementations
onCanopy
twoocta-­‐core
Parallel!
" Clustering on GP
G0,0 = {x2 }, N G0,0 = {G1,0 , G1,1 }(0, 2)(1, 2)(2, 2)
CPUs.
!
"x9!G0,2 "= {G1,19, G1,2 }ParallelCanopy
ClusteringonGPUsGN
0,2 = {x1 },x6 2)
G0,0 = {x2 }, N G0,0 ! = {G(0, 2)(2," 1,0 , G1,1 }(0, 1) (1, 2) (1, 1)(2, 1)
x9x8
G1,0 = {x3 , x5 , x!7 }, N "G1,0 = {G0,0 , G1,1 ,x1!
"G0,2 = {x1 }, N G0,2 = {G1,1 , G1,2 }x4=x6{x2 }, N G0,0 =G1,1{x4 },G{G=1,0,G(0, 2)(1, 2)(2,2)!
"
0,01,1 }(0, 1)(1, 1)(2, 1)!
"!
"
x9
G1,0 ={xx70,0}, , G
N0,2G=1,2{G,, G
3 , x=
5 , {G
1,00,0xN
G,G,G,GG8T
1,11,02,1x11G
0,2 = {x1 }, N G0,2 = {G1,1 , G1,2 }!
"x6!
"(2, 0)
GG(0, 1)(1, 1)(2, 1) (0, 0) x4 (1, 0)={x{x46 }, N G1,2 = {G0,2 , G1,1 , G2,1 , G
1,1
1,2=
G1,0 = {x3 , x5 , x7 }, N G1,0! = {G" , G2,1 }" 0,0!, G1,1x8
G2,1N= G{x1,1N {GG2,1=G{G,G,G
G1,2G8 }, =1,0
1,1
1,2,, G,,G,xT
0,00,2
1,031x4!!
""
G1,1 = {x4 },x0)x20)
G2,2=={x{x9 },}, N
GG
7"2,2 = {G1,1 , G1,2 , G2,1 }!
(0, 0)(1,(2,GNx51,26
1,2 = {G0,2 , G1,1 , G2
N G1,1 = {G0,0 , G0,2 , G1,0 , G1,2 , !G2,1 , "G2,2 }T1! example	  "G2,1 o=f	  g{x},NG
GFig.	  4:	  An	  rid	  
i
ndex
(a)
Partitioned
data
space.
2,1 = {G1,0 ,cells.
1,1 , G1xG
(0, 0)(1, 0)(2, 0)
3 1,2 = {x6 }, N G1,2 = {G0,2 , 8(b)Corresponding
grid
G1,1 , G!2,1 , G"2,2 }!
"G2,2 = {x9 }, N G2,2 = {G1,1 , G1,2 , G2x7x2
Gx2,1G2,1 = {G1,0 , G1,1 , G1,2 , G2,2 }x3
5 = {x8 }, N
Fig.
! 4: An" example of grid index.
x7
x2
G2,2 = {x9 }, N G2,2 = {G1,1 , G1,2 , G2,1 }(a)Partitioned
data space.
x5(b) Corresponding grid cells.
accomplished by computing the distances only between data points in a ce(a) Partitioned data space. its neighbor cells. A
is called a neighborof another cell if each dime(b)cell
Corresponding
grid cells.
(1)Divide	  while	  loop	  into	  Fig.
4:
An
exampleofgridindex.
of the cell coordinates does not diﬀer more than one, and the informat
3kernel	  functionsneighborsis also associatedgrid cells. The other cells do not need to be(2)Run	  the	  functions	  on	  GPUs
Fig.
4: An example
of grid toindex.
into considerationin canopy
because,two cells data
are notneighboraccomplishedby computingthecreation
distancesonlyifbetween
pointsindistance
between
twopoints
ineachcell
must
begreater
thanT.
1Fig.	  3:	  Canopy	  Clustering	  Algorithm	  oaccomplishedn	  GPUs
its neighborcellisbetween
called(𝒅:	  adata
ofinanothercellFig.	  5:	  distances
Ocells.
verall	  Aperformances	  dneighborimensionality,	  𝑻cell:	  grid	  size)if each
𝟏by computing
theonlypoints
aand
Figure 4 shows an exampleof partitioned data space and the correspo!
"
theiscell
coordinates
does
not
diﬀer
more
than
one,
andtheinfor
its neighbor cells. Aofcell
calledaneighborof
anothercell
if
eachdimension
grid cells. In Fig. 4(b), N G means a set of neighbors of G. By using thneighbors
iswe
also
to gridTheothercells doneedto
http://www.ccs.tsukuba.ac.jp/
index,
canassociatedcreatecanopyas cells.
follows:Let
us consider
that
pointof the cell coordinates
does
not
diﬀer
more athan
one,
and theinformation
ofnotthecontact	  address:	  {kitagawa,	  amagasa,	  shiokawa}@cs.tsukuba.ac.jp
into considerationinThecanopycreation
twocells
notneigselecteda center.
Since
thispoint
belongs
toifthecell
G1,0are, thedistancneighbors is also associatedto gridascells.
othercells
dobecause,
not need
tobe
taken
x1