The 2010 IEEE/RSJ International Conference onIntelligent Robots and Systems
October 18-22, 2010, Taipei, Taiwan

Detecting Repeated Patterns using
Partly Locality Sensitive Hashing
Koichi Ogawara and Yasufumi Tanabe and Ryo Kurazume and Tsutomu Hasegawa
Abstract— Repeated patterns are useful clues to learn previously unknown events in an unsupervised way. This paper
presents a novel method that detects relatively long variablelength unknown repeated patterns in a motion sequence efficiently.
The major contribution of the paper is two-fold: (1) Partly
Locality Sensitive Hashing (PLSH) [1] is employed to findrepeated patterns efficiently and (2) the problem of finding
consecutive time frames that have a large number of repeatedpatterns is formulated as a combinatorial optimization problem
which is solved via Dynamic Programming (DP) in polynomial
time O(N 1+1/α ) thanks to PLSH where N is the total amountof data. The proposed method was evaluated by detecting
repeated interactions between objects in everyday manipulation
tasks and outperformed previous methods in terms of accuracy
or computational time.

I. INTRODUCTION
Recognizing human activity is one of the fundamental
techniques in order to assist humans in everyday environment
using robotics technology. Many researchers have designed avariety of task-dependent recognizers that identify actions aswell as capture the necessary parameters to describe them[2], [3], [4]. However, there are huge variety of humanactivities in everyday life, it is not practical to prepare
recognizers for all of them. Thus, a mechanism to learn
new knowledge, new recognizers, in an unsupervised way
is required.
The goal of this study is to develop an efficient method that
detects previously unknown repeated patterns in an observation without task-dependent knowledge as a basis to realize
the above mentioned mechanism. The basic idea behind thisis if a particular pattern appears many times in a long-term
observation, this pattern must be meaningful to a user or
to a task. These patterns are good candidates for important
human actions and can be used to train recognizers, to learn
personal habits, to predict a user’s next action, etc.
The major contribution of the paper is two-fold. The
first contribution is that Partly Locality Sensitive Hashing(PLSH) [1] is employed to find repeated patterns efficiently
in a framework of approximate nearest neighbor search. The
second contribution is that the problem of finding variablelength repeated patterns is formulated as a combinatorial
optimization problem which is solved via a global optimization framework using Dynamic Programming (DP) in
K. Ogawara is with Institute for Advanced Study, Kyushu University,
Fukuoka, JAPAN ogawara@ait.kyushu-u.ac.jp
Y. Tanabe is with Department of Electrical Engineering and Computer
Science, Kyushu University, Fukuoka, JAPANR. Kurazume and T. Hasegawa are with Faculty of Information Scienceand Electrical Engineering, Kyushu University, Fukuoka, JAPAN

978-1-4244-6676-4/10/$25.00 ©2010 IEEE

TrajectoryT
Fig. 1.

Repeated patterns in a time series data.

polynomial time O(N 1+1/α ) thanks to PLSH where N is
the total amount of data.
The remainder of the paper is organized as follows. A
survey of the related research is given in Section II andan overview of the algorithm is presented in Section III.
PLSH is explained in Section IV and the global optimization
framework is explained in Section V. The experimental
results are presented in Section VI and this paper concludes
in Section VII.
II. R ELATED W ORK
While there has been a large body of work regarding
efficiently locating previously known patterns in a time series
data [5], [6], we focus on locating previously unknown
repeated patterns in this study as shown in Fig. 1. Finding
unknown repeated patterns, or motifs, has been a wellknown task in the bioinformatics community [7], in the data
mining community [8], [9], [10] and in the motion analysis
community [11], [12].
In contrast to finding known-length repeated patterns [7],[8], [10], several approaches based on Dynamic Programming (DP) have been proposed to deal with unknown-length
repeated patterns in quadratic time [11].
In our previous work [13], we proposed a method thatfinds repeated patterns in O(N log N ) time by counting thenumber of repeated patterns exactly using kD-tree, however
the hidden constant becomes linear with respect to N in theworst case that increases the computational time.
To reduce computational time, Meng et al. proposed amethod that finds K near neighbor data points using Locality
Sensitive Hashing (LSH) at each time frame and connects
them along time axis so as to find consistent repeated patternsin O(N 1+1/a ) time [12]. However, when the total amount ofdata becomes large, the number of data in each hash bucket
also becomes large. Thus, the actual computational time also
becomes large.
Tanabe et al. proposed Partly Locality Sensitive Hashing(PLSH), an extension to LSH, to find repeated patterns muchefficiently[1]. The proposed method extends [1] to work with
newly defined pattern density in order to deal with repeatedpatterns robustly.

1353

III. OVERVIEW OF THE ALGORITHM
Fig. 1 shows an example of the problem of interest. Givena long time series data of d dimensions, the task is to findunknown repeated patterns efficiently where minor variationof shape and length is allowed.
Fig. 2 shows a 2D slice of a time series data. If a data
point o(t) at time t belongs to a set of repeated patterns,
many similar shaped patterns exist at around the data point.
So, a sequence of data points that have many other data
points in their neighborhood can be considered as a goodcandidate for a repeated pattern.
To find candidate repeated patterns, neighborhood is defined as the inside of a hyper sphere of radius R in ddimensional space and pattern density, the length of thesegments in the sphere, is defined as
D(t)

X

=

ko(i) − o(i + 1)k(1)i∈S(t)

where S(t) = {i; ko(i) − o(t)k ≤ R}.
St = 1
Ed = tb1

St = tc1
Ed = td1

St = te1
Ed = !1

tc1

td1

St = 1
Ed = tb2

St = te2
Ed = !2

tc2

td2

R

o(t )

o(t )
t=1

tb2

tb1

te1

!1

!2

te2

(a) Ini"aliza"on of Linked List.
St = 1
Ed = td3

St = tc2
Ed = td2(b) Update of segments.
St = 1
Ed = td4

St = te3
Ed = !3

St = te4
Ed = !4

St = tg4
Ed = th4

td4

th4

td3
o(t )

o(t )

tg4

te4
!3

!4

(c) Integra"on of segments.

(d) Addi"on of new segments.

te3

St = 1
Ed = tb5

td5

St = tc5
Ed = td5

o(t )

tc5
tb5

From time t = 2 to t = N , the linked list is updatedby shifting the endpoints of each segment so that they lie
exactly on the boundary of the sphere as in Fig. 2 (b). We
can expect that the amount of shift between frames is verysmall, 0 or 1 in most cases, so the time to update the linked
list can be considered as a constant. When a segment goesoutside the sphere, it is removed from the linked list. Whentwo segments are connected together, the two corresponding
elements in the linked list are merged as in Fig. 2 (c).
When a new segment enters into the sphere, we have todetect it and add it to the linked list as in Fig. 2 (d). For
this, if we check all N data points, it takes quadratic timein total. Instead, we randomly sample data points around thecurrent data point, and add them to the linked list if they are
inside the sphere and are not yet included in the linked list.
Here, a new segment is not necessarily detected when it justenters into the sphere, because we can expect that it will be
detected in the subsequent steps anyway if it is sufficiently
similar to the current segment. When a segment is detected
later, the pattern density in the past is modified at that time.
To sample data points inside the sphere efficiently, Partly
Locality Sensitive Hashing (PLSH) is proposed as explainedin the next section.
A segment in the sphere can be divided into two segments
as in Fig. 2 (e). Since only the endpoints of segments
are stored in the linked list, division cannot be detected
immediately. To solve this problem, we randomly sample
data points around the past data point o(t − Tdelay ) by
PLSH. If a sampled data point is outside the sphere but
is included in the linked list, that means the corresponding
segment is divided and the linked list should be modified.
A divided segment is not necessarily detected when it justbegins to leave the sphere, because we can expect that it will
be detected in the subsequent steps anyway if it leaves thesphere. When a divided segment is detected later, the patterndensity in the past is modified at that time.
The difference from [13], [1] is that they calculate thenumber of nearby segments which is sensitive to outlier
segments found at the boundary of the sphere, while wecalculate the density of segments which is much stable,
Furthermore, they only consider addition of a new segment,
while we also consider a divided segment, thus the accumulated error in calculating pattern density becomes small.
Finally, repeated patterns are estimated via global optimization framework using Dynamic Programming (DP) as
explained in Section V.
IV. PARTLY L OCALITY S ENSITIVE H ASHING(e) Division of segments.

Fig. 2.

Partly Locality Sensitive Hashing (PLSH) is an extension
to Locality Sensitive Hashing (LSH) scheme [14] which isan approximate nearest neighbor search algorithm.

Calculation of pattern density.

Then, the task to find sequences of data points that havelarge pattern density is solved efficiently as follows.
At time t = 1, the linked list is initialized by checking
all N data points so that the elements in the list stores theendpoints, i.e. the start time (st) and the end time (ed), of all
the segments inside the sphere as in Fig. 2 (a).

A. Locality Sensitive Hashing
In LSH framework, L hash functions gl (p) (1 ≤ l ≤ L)
that calculate K dimensional hash values are defined as1354

gl (p) =< hl1 (p), hl2 (p), . . . , hlK (p) >(2)

projecon vector

where p is a d dimensional input value.
h(p) can be any hash function h : Rd → U that preserves
locality of input values, i.e. the probability of collision of two
closer input values in a hash bucket is high. In a projectionbased LSH, the following function can be used:h(p) = b(a · p + b)/wc

Locality sensive hash funconwi

hs k (p)
ws

r
as

(3)

where a, b are randomly chosen to satisfy a ∈ Rd , ||a|| =1, 0 ≤ b < w for each hash function h(p). w controls thesize of a hash bucket.
Given an input query p, L hash buckets are determinedby gl (p). Then, the data points stored in these buckets are
examined whether they are sufficiently close to the query.
LSH solves an approximate nearest neighbor search problem
in O(N 1/α ) where α(> 1) is an approximation factor
determined by the parameters of LSH.

Locality insensive hash funconh i k (p)raiFig. 3.

Partly Locality Sensitive Hashing.

T
Trajectory

B. Partly Locality Sensitive Hashing

Object 1

In PLSH framework, L hash functions gl (p) (1 ≤ l ≤L) that calculate K dimensional hash values are similarly
defined by combining locality sensitive hash functions andlocality insensitive hash functions asT

Object 2

T

ConflictObject 3

gl (p) =< hsl,1 (p), . . . , hsl,Ks (p), hil,1 (p), . . . , hil,Ki (p) >(4)where hs(p) is a locality sensitive hash function and hi(p)is a locality insensitive hash function.
hs(p), or hi(p), can be any hash function h : Rd → U that
preserves, or does not preserve, locality of input values. In
the projection-based scheme, these functions can be defined
as
hs(p)

=

b(a · p + b)/ws c,

hi(p)

=

b(a · p + b)c mod wi(5)where hs(p) is exactly the same as in Eq.(3), while hi(p)calculates discretized residual. a, b are randomly chosen tosatisfy a ∈ Rd , ||a|| = 1, 0 ≤ b < w for each hash function.
Given an input query p, L hash buckets are determinedfrom gl (p). Then, the data points stored in these buckets are
examined as in the case of LSH.
Fig. 3 shows how PLSH works.
C. Sparse sampling using PLSH
To sample data points from the entire sphere centered ato(t), the width of a hash bucket is fixed to R. If we use
LSH to sample data points as in [12], it takes time to sample
sufficient number of data points when N increases because
the number of data points in a hash bucket also increases.
PLSH is effective in this case. We represent each data
point by d + 1 dimensional vector (p1 , . . . , pd , t)T where thefirst d elements represent a data point and the last 1 element
represents the time frame.
To design gl (p), we choose Ks locality sensitive hashfunctions hsl,k (p) where the last value of a is always 0
and ws is R. We also choose one locality insensitive hashT

Data LabelN N N A A N N C C N A A N N C C N N N N

Fig. 4.

Finding consistent repeated patterns.

function hil (p) where the first d values of a is always 0.
Because time frame is a discretized value, we design a andwi in hil (p) so that the width of a hash bucket is exactly
1 time frame and consecutive data points never collide in asame hash bucket.
In so doing, nearby data points along time axis accesses
independent hash spaces in which no data point is shared
when calculating pattern density. Thus, the computationaltime to examine the data points in a hash bucket decreases
because the number of data points in a hash bucket decreases
while the possibility of detecting a new data point, or adividing data point, is the same as that of LSH.
V. D ETECTION OF R EPEATED PATTERNS
A. Target problem
In this study, interrelated multiple continuous time series
data is dealt with. Fig. 4 shows an example of the problem.
The input is trajectories of multiple objects, 3 in this case,and the algorithm is required to output the patterns thatappear many times in the input trajectories. If the multiple
trajectories are independent of each other, then the algorithm
has only to be applied to each trajectory separately. However,if the trajectories are interrelated with each other, the algorithm has to find the consistent repeated patterns among the
trajectories.
This is the case when repeated interactions between objects are of interest. In Fig. 4, there are 3 possible interactions
between: (A) Obj.1 and Obj.2, (B) Obj.1 and Obj.3, (C)1355ed (O, xt )Object 1

䞉䞉䞉
Object 1

es ( xt , xt +1 )Es (X) is a term regarding the prior distribution of X.
It penalizes different consecutive data labels to reject shortpatterns. It is defined as

Object 2A䞉䞉䞉A

Object 3
䞉䞉䞉

B

䞉䞉䞉

Es (X) =Find the shortest PATH
Non 䞉䞉䞉

䞉䞉䞉where Csmooth is a constant and T (s) = 1 iff s =true, otherwise T (s) = 0.
Because all the terms in Eq.(6) satisfies the first orderMarkov property, the energy minimization problem can beanalytically solved by Dynamic Programming as shown in
Fig. 5.

N means “Non”

Fig. 5.

T (xt 6= xt+1 ) · Csmootht

N N N A A N N A A B N N N A C C N N N N

Data LabelX

Estimation of data labels via dynamic programming.

Obj.2 and Obj.3. If two of them are detected at the sametime, this means a conflicting situation.
In the proposed method, we assume that there occurs asingle significant interaction at most at a certain moment.
This assumption is not necessarily true when there are 4 ormore objects, or a motion is composed of more than two
objects, but it will be satisfied in most cases.
Then, the problem is formulated as a combinatorial optimization problem in that a data label x ∈ {A, B, C, N on} isassigned to each time frame as shown in the bottom of Fig.
4. A, B, C mean there occurs a repeated interaction between
the respective object pairs, while N on means there is norepeated pattern at that time.
Please note that this formulation includes the case where
repeated patterns are to be detected from a single timeseries data in that we have only two labels: repeated andnot-repeated.

C. Clustering of patterns
An agglomerative clustering technique is applied to thedetected patterns of the same label to divide them into
different types of patterns. In this study, for each pair ofdetected patterns, we calculate the ratio of the number ofcorrespondences whose distance is below the radius R of thehyper sphere. If the ratio is above the threshold Cmutual , thepair of patterns are regarded as to belong to the same typeof pattern.
In order to calculate the ratio efficiently, we use themiddle point tj of each segment in the linked list as thecorrespondence to time t and merge two patterns together if
Eq.(7) is satisfied. If no segment corresponding to the current
pattern is found at time t, the numerator of Eq.(7) becomes
0 at this particular time.
tj −tsjt−ts
t=ts 1 − | te −ts +1 − tej −tsj +1 |Pte

B. Formulationte − ts + 1

The problem is formulated as a combinatorial optimization
problem regarding the data labels X = (x1 , · · · xN ), xt ∈{A, B, · · · , N on} as shown in Fig. 4. There are M =m(m − 1)/2 data labels where m is the number of objects
in the scene and oi (t) represents relative position between
i-th object pairs at time t.
Givenmultipletime-seriesdataO=(o1 (1), · · · , o1 (N ), · · · , oM (1), · · · , oM (N )), we want tofind X that minimizes the energy function
E(O, X) = Ed (O, X) + Es (X).

≥ Cmutual(7)

where ts , te and tsj , tej are the start and the end time of
two patterns. The absolute difference between the normalized
time t and tj is used to realize nonlinear elastic matching.
D. Computational complexity
It requires O(N 1+1/α ) for building PLSH tables andcalculating pattern density for all the time frames, andO(M 2 N ) for DP. Assuming M << N , the total averagecomputational time is O(N 1+1/α ).
VI. E XPERIMENTAL RESULTS(6)

A. Experimental setup
Note that the formulation is slightly different from ourprevious work [13], [1] in that the energy function has athird term that penalizes small velocity.
Ed (O, X) is a term regarding pattern density (Eq.(1)) andit penalizes data points with small density. It is defined as

Ed (O, X) =Xt− log(1 − exp(−

Dxt (t)))< Dxt (t) >where Dxt (t) is the pattern density at time t on the relative
trajectory corresponding to xt , and < Dxt (t) > is the meanvalue of Dxt (t).

4 different manipulation tasks were performed by a subject
and were used to evaluate the proposed method. There
were 4 objects in the scene and an electromagnetic motion
tracking system (Polhemus FASTRAK) was used to observe
the trajectory of each object at 30Hz during demonstrations.
As shown in Fig. 6, 6 actions are defined. A subject
was instructed to perform a task following a scenario madeby combining 6 actions. To emulate the change in theenvironment during a long-term observation, the subject was
instructed to relocate the objects on the table several times
so that the relative relationship between stationary objects
was changed.

1356

TABLE I
E VALUATION OF DATASET 1 [896 FRAMES ].
ActionPresented #kD-tree
LSH
PLSH

A1
4
4.00
3.60
3.90

False
positive
0.00
1.00
0.00

False
negative
0.00
0.40
0.10

Precision
ratio
1.00
0.78
1.00

Recall
ratio
1.00
0.90
0.98

TABLE IIE VALUATION OF DATASET 2 [1428 FRAMES ].
ActionPresented #kD-tree
LSH
PLSH

A1
3
3.00
3.00
3.00

A2
3
3.00
1.80
3.00

False
Positive
0.00
0.30
0.00

False
Negative
0.00
1.20
0.00

Precision
ratio
1.00
0.94
1.00

Recall
ratio
1.00
0.80
1.00

TABLE IIIE VALUATION OF DATASET 3 [3737 FRAMES ].
ActionPresented #kD-tree
LSH
PLSH

A1
5
5.00
4.70
5.00

B1
7
7.00
5.60
7.00

C1
6
6.00
5.50
6.00

False
Positive
0.00
0.00
0.00

False
Negative
1.00
3.20
1.00

Precision
ratio
1.00
1.00
1.00

Recall
ratio
0.95
0.83
0.95

Precision
ratio
1.00
0.96
1.00

Recall
ratio
0.50
0.41
0.48

TABLE IVE VALUATION OF DATASET 4 [5177 FRAMES ].
ActionPresented #kD-tree
LSH
PLSH

A1

A2

B1
7
7.00
6.40
7.00

B1

C1

C1
5
3.00
3.60
3.00

C2

C2
10
6.00
3.60
5.30

D1
10
0.00
0.00
0.00

D1

False
Negative
16.00
19.00
16.70

by LSH and PLSH depends on the randomly determinedparameters of the hash functions, thus each experiment wasevaluated 10 times and the average is shown.
The following parameters are used in all the experiments.
The number of hash functions L = 8 and the number of
locality sensitive hash functions Ks = 3. ws = 0.25 whichis equal to the radius R of the hyper sphere. wi was chosenrandomly from 50 to 100. We terminate the sampling process
after Csearch data points are sampled in LSH and PLSH. As
suggested in [14], Csearch = 3L for both LSH and PLSH.
TABLE I, II, III, IV show the results of detecting repeatedpatterns using 3 different methods. All the experiments were
performed on a Xeon 3.0GHz PC with 2G memory.
As an error measure, Precision and Recall ratio are calculated from True Positive (TP), False Positive (FP) and False
Negative (FN) as:

A1: Pour from a container to a cup from the le
A2: Pour from a container to a cup from the right
B1: Pour from a teapot to a cup
C1: Mix inside a cup with a spoon
C2: Put into a cup with a spoon
D1: Put from a container with a spoon
Fig. 6.

False
Positive
0.00
0.60
0.00

6 manipulation actions.

B. Evaluation
1) Different tasks: Because calculation of pattern density
requires the highest computational complexity, 3 different
methods of calculating pattern density, including exact searchmethod by kD-tree, approximate search method by LSH
and approximate search method by PLSH, were evaluatedin terms of accuracy in detecting frequent patterns as wellas in terms of computational time. Please note that the exact
search method by kD-tree should give the best result in termsof accuracy. While the accuracy of the approximate searchPrecision =TP
TP, Recall =.
TP + FPTP + FN

The precision and recall ratio of the proposed method was
almost identical to the ones of kD-tree, while that of LSH ismuch worse.
The reason why action D1 was never detected in TABLE
IV was that C2 always followed just after D1 and these twoconsecutive actions were detected as a single action whichwere labelled as C2.

1357

0.55

This is the strong advantage of the proposed method when
dealing with a huge amount of observations.

0.5
0.45

.V 

Recall

0.4
0.35
0.3
0.25
0.2
0.15
0.1
5000

PLSH (3L)
LSH (3L)
LSH (10L)
kD-tree

10000 15000 20000 25000 30000 35000 40000 45000 50000 55000
Amount of data [frame]

Fig. 7.

ACKNOWLEDGMENTS
This study was supported in part by Program for Improvement of Research Environment for Young Researchers fromSpecial Coordination Funds for Promoting Science and Technology (SCF) commissioned by the MEXT of Japan, and inpart by Grant-in-Aid for Young Scientists (B)(21700224).

Evaluation of recall ratio v.s. amount of data.

180
160

VII. C ONCLUSIONSThis paper presents a method that detects consistent repeated patterns from multiple observations in O(N 1+1/α )time where N is the total amount of data.
Partly Locality Sensitive Hashing (PLSH) is proposed
to find candidate repeated patterns efficiently by sparsely
sampling nearby patterns in subquadratic computational time.
The proposed method was evaluated by detecting repeatedinteractions between objects in everyday manipulation tasks.
The proposed method outperformed the method based on kDtree and LSH in terms of accuracy or computational time.

PLSH (3L)
LSH (3L)
LSH (10L)
kD-tree140
120Time [s]R EFERENCES
100
80
60
40
20
0
5000

10000 15000 20000 25000 30000 35000 40000 45000 50000 55000
Amount of data [frame]

Fig. 8.

Evaluation of computational time v.s. amount of data.

2) Different amount of data: In the second experiment.
the 3 methods were evaluated against different amount ofdata. 10 datasets of different length were generated by simply
concatenating the dataset in TABLE IV with Gaussian noise
added.
Fig. 7 shows the Recall ratio obtained from the different
methods. As the amount of data increases, recall ratio
decreases. This is because the number of data points in ahash bucket increases as well. The result of kD-tree is thebest. PLSH is far better than LSH with the same parameters.
We also tested the case where Csearch = 10L for LSH toincrease the number of buckets and to decrease the numberof data points in a bucket, but PLSH is still better.
If we increase Ks , the number of locality sensitive hashfunctions, recall ratio is dramatically improved with a slightincrease of computational time. If we set Ks = 4, thecomputational time is increased by 10 %, while recall ratioof the 10-th dataset becomes 0.43 as shown in Fig. 7.
Precision ratio achieves almost always 1.00 for all themethods, thus we omitted the evaluation of precision ratio.
Fig. 8 shows the computational time obtained from the different methods. The time of kD-tree increases quadratically,
while the time of LSH and PLSH increases almost linearly.

[1] Y. Tanabe, K. Ogawara, R. Kurazume, and T. Hasegawa, “Detecting
frequent actions using partly locality sensitive hashing,” in Proc. The
Fourth Joint Workshop on Machine Perception and Robotics (MPR),
2009.
[2] K. Ikeuchi and T. Suehiro, “Toward an assembly plan from observation
part i: Task recognition with polyhedral objects,” IEEE Trans. Robotics
and Automation, vol. 10, no. 3, pp. 368–384, 1994.
[3] Y. Kuniyoshi, M. Inaba, and H. Inoue, “Learning by watching,” IEEE
Trans. Robotics and Automation, vol. 10, no. 6, pp. 799–822, 1994.
[4] K. Bernardin, K. Ogawara, K. Ikeuchi, and R. Dillmann, “A sensor
fusion approach for recognizing continuous human grasping sequencesusing hidden markov models,” IEEE Transactions on Robotics, vol. 21,
no. 1, pp. 47–57, 2005.
[5] R. Agrawal, C. Faloutsos, and A. Swami, “Efficient similarity searchin sequence databases,” in Proc. of 4th International Conference onFoundations of Data Organization and Algorithms, 1993, pp. 69–84.
[6] C.-S. Perng, H. Wang, S. R. Zhang, and D. S. Parker, “Landmarks:
A new model for similarity-based pattern querying in time series
databases,” in 16th International Conference on Data Engineering(ICDE’00), 2000, pp. 33–42.
[7] R. Staden, “Methods for discovering novel motifs in nucleic acidsequences,” Computer Applications in the Biosciences, vol. 5, no. 5,
pp. 293–298, 1989.
[8] J. Lin, E. Keogh, S. Lonardi, and P. Patel, “Finding motifs in timeseries,” in Proc. of the 2nd Workshop on Temporal Data Mining, 2002,
pp. 53–68.
[9] D. Yankov, E. Keogh, J. Medina, B. Chiu, and V. Zordan, “Detecting
time series motifs under uniform scaling,” in Proc. of the 13th ACM
KDD Intl. Conf. on Knowledge Discovery and Data Mining, 2007, pp.
844–853.
[10] A. Mueen, E. Keogh, Q. Zhu, S. Cash, and B. Westover, “Exact
discovery of time series motifs,” in Proc. of 2009 SIAM International
Conference on Data Mining: SDM, 2009, pp. 1–12.
[11] S. Uchida, A. Mori, R. Kurazume, R. Taniguchi, and T. Hasegawa,“Logical dp matching for detecting similar subsequence,” in Proc. of
Asian Conference of Computer Vision, 2007.
[12] J. Meng, J. Yuan, M. Hans, and Y. Wu, “Mining motifs from humanmotion,” in Proc. of EUROGRAPHICS’08, 2008.
[13] K. Ogawara, Y. Tanabe, R. Kurazume, and T. Hasegawa, “Detecting
repeated motion patterns via dynamic programming using motion
density,” in Proc. 2009 IEEE Int. Conf. on Robotics and Automation(ICRA), 2009, pp. 1743–1749.
[14] M. Datar, N. Immorlica, P. Indyk, and V. Mirrokni, “Locality-sensitive
hashing scheme based on p-stable distributions,” in Proc. of thetwentieth annual Symposium on Computational Geometry, 2004, pp.
253–262.

1358