Welcome to the LB_Keogh homepage!
What is LB_Keogh? LB_Keogh is tool for lower bounding various time series distance measures. It was introduced in 2002 as the first non trivial lower bound for Dynamic Time Warping (DTW), and it is still the fastest known technique for indexing DTW (see [9]). It can also be used to index under uniform scaling, various other distortions, and it can be used for efficient processing of streaming time series [8] and for indexing shapes [12]. To the right is a visual intuition of LB_Keogh, a protective envelope is built around the red time series, the Euclidean distance between the blue time series and the closest part of the protective envelope is a (tight) lower bound to the DTW. For indexing under uniform scaling or processing of streaming time series etc, the definition of the envelope differs, but the LB_Keogh definition is unchanged. Note that LB_Keogh takes one line of code in matlab! Suppose you have a query Q and you have created U and L according to the problem you are interested in (DTW, uniform scaling etc). U = (eq 6 of VLDB02 paper for DTW, eq 6 of VLDB04 paper for uniform scaling, or..) Then LB_Keogh can be expressed in the following single line of matlab... LB_Keogh = sqrt(sum([[Q > U].* [QU]; [Q < L].* [LQ]].^2)); 

Videos of LB_Keogh for uniform scaling (in motion capture data) Video of LB_Keogh for DTW (in motion capture data) Images of LB_Keogh for shape indexing Note that the entire development of LB_Keogh was made possible by funding from an NSF Career Award 0237918.

Some papers by Keogh and collaborators that use LB_Keogh. (in random order)
In [1] I introduced LB_Keogh and showed how it could be used for exact indexing of DTW. In [2] I showed how LB_Keogh could be used for exact indexing of uniform scaling. In [3] we consider both DTW and uniform scaling at the same time. In [4] we showed how to use LB_Keogh on a bit level represention of time series. Paper [5] extends LB_Keogh to mulitdimensional time series. In [6] we consider applications to motion capture problems. In [7] we show how use LB_Keogh to improve classification accuracy. In paper [7] we see the first paper on using LB_Keogh for processing streams. Many people have tried to beat LB_Keogh, in paper [7] we show with 8 billion experiments that this is not possible. Paper [10] considers the importance of uniform scaling in motion capture problems, and shows how LB_Keogh can efficiently address the problem. Paper [11] shows how to do fast classification of time series using numerosity reduction, we use LB_Keogh to make this idea tractable. Paper [12] shows that LB_Keogh can be used to index shapes!
Keogh, E. (2002). Exact indexing of dynamic time warping. In 28^{th} International Conference on Very Large Data Bases. Hong Kong. pp 406417. [Conference version pdf , Journal version pdf , slides ]. Also a KAIS journal paper.
Keogh, E. (2003). Efficiently Finding Arbitrarily Scaled Patterns in Massive Time Series Databases. PKDD 2003: 253265
Ada Waichee Fu, Eamonn Keogh, Leo Yung Hang Lau and Chotirat Ann Ratanamahatana (2005). Scaling and Time Warping in Time Series Querying. VLDB 2005. [pdf]
Ratanamahatana, C., Keogh, E., Bagnall, T. and Lonardi, S. (2005). A Novel Bit Level Time Series Representation with Implications for Similarity Search and Clustering. PAKDD 05. [pdf ]
Vlachos, M., Hadjieleftheriou, M., Gunopulos, D. & Keogh. E. (2003). Indexing MultiDimensional TimeSeries with Support for Multiple Distance Measures. In the 9^{th} ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. August 24  27, 2003. Washington, DC, USA. pp 216225. [ pdf]
M. Cardle, M. Vlachos, S. Brooks, E. Keogh, D. Gunopulos (2003). Fast Motion Capture Matching with Replicated Motion Editing. In Proc. of SIGGRAPH 2003, San Diego, Technical Sketches & Applications July 2731, 2003. San Diego, CA. USA. [ pdf]
Ratanamahatana, C. A. and Keogh. E. (2004). Making Timeseries Classification More Accurate Using Learned Constraints. In proceedings of SIAM International Conference on Data Mining (SDM '04), Lake Buena Vista, Florida, April 2224, 2004. pp. 1122. [pdf, slides]
L. Wei, E. Keogh, H. Van Herle, and A. MafraNeto (2005). Atomic Wedgie: Efficient Query Filtering for Streaming Time Series. In Proc. of the 5th IEEE International Conference on Data Mining (ICDM 2005), pp. 490497, Houston, Texas, Nov 2730, 2005. [pdf] [slides].
Ratanamahatana, C. A. and Keogh. E. (2005). Three Myths about Dynamic Time Warping. In proceedings of SIAM International Conference on Data Mining (SDM '05), Newport Beach, CA, April 2123, pp. 506510 [pdf , slides]. Also appeared as a workshop paper with the following unlikely title...Ratanamahatana, C. A. and Keogh. E. (2004). Everything you know about Dynamic Time Warping is Wrong. Third Workshop on Mining Temporal and Sequential Data, in conjunction with the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD2004), August 2225, 2004  Seattle, WA. [pdf , slides]
Keogh, E., Palpanas, T., Zordan, V., Gunopulos, D. and Cardle, M. (2004) Indexing Large HumanMotion Databases. In proceedings of the 30th International Conference on Very Large Data Bases, Toronto, Canada. [pdf, slides ]
Xiaopeng Xi, Eamonn Keogh, Christian Shelton, Li Wei & Chotirat Ann Ratanamahatana (2006). Fast Time Series Classification Using Numerosity Reduction. ICML. [pdf]
Eamonn Keogh, Li Wei, Xiaopeng Xi, SangHee Lee and Michail Vlachos (2006) LB_Keogh Supports Exact Indexing of Shapes under Rotation Invariance with Arbitrary Representations and Distance Measures. VLDB 2006 [pdf]
Hui Ding, Goce Trajcevski, Peter Scheuermann, Xiaoyue Wang and Eamonn Keogh (2008) Querying and Mining of Time Series Data: Experimental Comparison of Representations and Distance Measures VLDB 2008 [pdf]
Xiaoyue Wang, Abdullah Mueen, Hui Ding, Goce Trajcevski, Peter Scheuermann and Eamonn Keogh (2012) Experimental comparison of representation methods and distance measures for time series data. DATA MINING AND KNOWLEDGE DISCOVERY
Thanawin Rakthanmanon, Bilson Campana, Abdullah Mueen, Gustavo Batista, Brandon Westover, Qiang Zhu, Jesin Zakaria, Eamonn Keogh (2012). Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping SIGKDD 2012. Best paper award
Some papers by other researchers that use LB_Keogh. (in no particular order) (I have stopped maintaining this section of the page, it is too hard to keep up)
In [A][C] LB_Keogh is used for handwriting
retrieval. In [B] LB_Keogh
is used for music retrieval. In [D] LB_Keogh is used for subsequence
matching.
In [E] LB_Keogh is used for indexing under Euclidean distance. Paper
[F] considers
LB_Keogh for rotation invariance indexing. Paper [G] uses APCA and
LB_Keogh for
DTW (but see [9] above). Paper [H] uses LB_Keogh for indexing images.
Paper [I]
uses LB_Keogh for oil well mining (in both senses of "mining").
Paper [J] [L] uses LB_Keogh for peer to peer music retrieval . Paper
[K] also
uses APCA and LB_Keogh for DTW (but see [9] above). Paper [M] is yet
another
work that uses APCA and LB_Keogh for DTW (but see [9] above). In
paper [N] the authors adapt
LB_Keogh for monitoring streams. Paper [O] uses DTW to index 3D
shapes and
note "..an advantage of this model
is
that has been proved that Dynamic Time Warping technique can be indexed
with
LB_Keogh". Paper [P] uses LB_Keogh to index dance notation. Paper
[Q] uses LB_Keogh to explore software traces. [R] uses a modified LB_Keogh for
music indexing. Paper[S] also uses a modified LB_Keogh for
music indexing. Paper [T] uses the LB_Keogh for indexing shapes. Paper [U] uses
the notation of nested wedges (see Atomic
Wedgie) to index XML doucuments!
Paper [V] is yet another paper that uses LB_Keogh for indexing music. Papers [W]
and [X] use the LB_Keogh for Predicting UserPerceived Quality Ratings from
Streaming Media Data. Paper [y]
uses LB_Keogh to do something (I am honestly not sure what!) Paper [z] uses
LB_Keogh to support range queries in time series. Paper [AA] uses LB_keogh for
online fault diagnosis .Paper [AB] uses LB_Keogh for shape indexing. Paper [AC]
uses the LB_Keogh to make a medical data mining task tractable. Paper [AE]
uses LB_Keogh for predicting video stream quality from partial stream
information. Paper [AF] uses LB_Keogh for indexing 3D shapes. Paper [AG] uses
LB_Keogh for Speeding up Complex Video Copy Detection Queries. Paper [AH] uses
LB_Keogh for Fast Detection of Suspicious Stream Patterns. Paper [HI] uses
LB_Keogh for gesture recognition. Paper [AJ] uses LB_Keogh for shape indexing.
Paper [AK] uses LB_Keogh for anomaly detection. Paper [AL] uses LB_Keogh to
support fast approximate searching. Paper [KM] has an interesting twist on
LB_Keogh, they only use the upper envelope. They note "To prove that L(Q, S) ≤
DTW(Q, S) for posteriorgram sequences Q and S, we follow the strategies that are
used in (Keogh)". Paper [AN] does something similar to Atomic Wedgie.
Paper [AO] used LB_Keogh and LB_PAA to do something. [AP] use LB_Keogh for
speech indexing