Welcome to the LB

LB_Keogh makes retrieval of time-warped time series feasible even for large data sets. Muller et. al. SIGGRAPH 05.
LB_Keogh is fast, because it cleverly exploits global constraints that appear in dynamic programming. Christos Faloutsos et al. PODS 2005
LB_Keogh, the best-so-far known method to lower bound DTW.. Capitani and Ciaccia SEBD05.
The powerful lower-bounding method LB Keogh for efficient time series matching... Papapetrou et al TODS 2011
Due to its ease of implementation and relative computational efficiency (when optimized) we chose to use DTW. For more information on the particular methods used in MAGIC, see (LB_Keogh) Ashbrook and Starner CHI 2010
The best lowerbounding method for constrained DTW distance and ﬁxed-length time series so far is considered LB Keogh. Bartos & Skopal 2012
(LB_Keogh) makes DTW indexable by approximating time series with bounding envelopes. Lian et. al. TKDE 2009
The sliding window approach is speeded up by the LB Keogh lower-bounding method, often by orders of magnitude. Lijfﬁjt et al PETRA 2010
Although DTW has a time complexity of O(n²), (LB_Keogh) bounding can effectively make DTW run in O(n). Smith and Craven csb2008
The standard DTW algorithm has a quadratic time and space complexity. For performance reason we implemented a FastDTW based on the ideas of LB_Keogh..and therefore the algorithm performs nearly in linear time. Juffinger, Granitzer and Lex WWW 2009
The LB_Keogh method speeds up the sliding window approach, often by orders of magnitude, by computing an efficient lower bound of the matching cost.. Panagiotis Papapetrou 2009.
LB_Keogh can significantly speed up DTW. Suzuki et al. ICML 2003.
We use LB_Keogh to speed up the algorithm.. Xu et al. 2011
In order to speed-up the calculations, we used the LB Keogh lowerbounding technique. Buza et al PAKDD 2011
Keogh et al. and showed that their tight lower bound LB_Keogh could also be used in rotation-invariant image matching and provided a novel solution for the DTW distance as well as the Euclidean distance. Yang-Sae Moon et al 2010
(for) the problem of searching for similar acoustic data over unstructured decentralised P2P networks LB_Keogh can be effectively used for pruning, resulting in considerably less number of DTW computations. Karydis et. al. ICEIS05
Thus in this paper we use anenvelope-based lower bound proposed by Keogh (LB_Keogh) to improve the performance of rotation-invariant image matching. Kim et al DEXA 2011
by exploiting recent results on metric access structures and LB_Keogh, we can still guarantee the indexability of DFT coefficients extracted from large data sets. Bartolini et. al. IEEE PAMI.
LB_Keogh is preferred (for motion capture) since it offers the tightest lower bounds, is readily indexible with MBRs. Marc Cardle University of Cambridge Thesis
Keogh has pioneered many of the recent ideas in the indexing of dynamic time warping". Cole, Shasha, and Zhao SIGKDD 2005.
LB_Keogh performs uniformly the best. Chen and Ng. VLDB 2005.
Among the existing lower bound functions, LB_Keogh is the best in terms of the tightness of the lower bound. Zhou, M. and Wong, Information Sciences 2005
Despite the fact that DTW distance still does not satisfy the triangle inequality, LB_Keogh exactly index(s) the DTW distance. Wang, Z.
LB_Keogh has provided a convincing lower bound that can be tuned to provide high tightness to the actual DTW distance. Toni Rath
We exploit (LB_Keogh) in the context of reverse engineering of dynamic feature behavior to detect similarities between feature traces. This technique is ideally suited to handling large amounts of data. Kuhn and Greevy
Recently, Keogh et al. presented an algorithm, based on the LB_Keogh function, which dramatically reduced the time complexity of the calculation of the Euclidean Distance measure. This speed up was further achieved by allowing indexing. Frentzos et al. ICDE 2007
Exact indexing of DTW has been proposed in the literature,.. the LB_Keogh. Employing the indexing method allows us to reduce the computation (needed for query by humming). Roger Jang, PCM 2006.
To reduce the computational time and (quadratic) complexity inherent in dynamic time warping, we use (LB_)Keogh minimum bounds to quickly determine candidates for the set of nearest neighbors. Dalal and Olson. SPECTS07
(we use) LB_Keogh for efficient similarity range query processing in music databases. Ruxanda & Jensen 2006
LB_Keogh.. has become a popular solution for indexing DTW because of its performance. Zhou &Wong ICDE 2007
To speed up computations we could utilize spatiotemporal access methods similar to LB_Keogh" Zeinalipour Yazti , Lin and Gunopulos CIKM 2006
EDR incurs huge computational cost due to the lack of pruning techniques such as LB_Keogh lower bound Chen et al. ICDE07.
Since DTW is relatively slow to calculate... We therefore use (LB_)Keogh minimum bounds. Dalal, Musicant, Olson, McMenamy, Benzaid, Kazez and Bolan. icc2007.
Because DTW is not a metric, we use LB_Keogh to make indexing possible (for our query by humming system) Leung Tat-wan. 2005.
In order to use the SBR representation in a multidimensional index, we must have a distance function that lower bounds the distance between a query object and a group of time series data. Therefore we can use LB_Keogh.. Li, Lopez and Moon TKDE 2004
Keogh proposed LB Keogh and LB PAA, tight lower bounds under time-warping ... our solutions exploit these two lower bounds.. Han et al VLDB 2007
(LB_Keogh) significantly speeds up the DTW (for music similarity). Joan Serra 2007. Master Thesis UPF. Barcelona
For fault diagnosis (LB_keogh) substantially reduce the computational expense required. Rajshekhar, et. al 2007
(we use) the tightest existing lower bound.. (for) exact indexing of Dynamic Time Warping, LBKeogh. Assent, Krieger, Afschari and Seidl EDBT 2008
(LB_Keogh) has significantly increased the accuracy of time series classification while reducing the computational expense required. Kumar, Gupta, Jayaraman & Kulkarni 2008
Exact indexing of DTW has been proposed in the literature.. using LB_Keogh.. Employing the indexing method allows us to reduce the computation (of query by humming). Jang and Lee 2008
the best lowerbound function in terms of tightness is the LB_Keogh... It cleverly exploits the warping window.. Zhou and Wong ICDE08
we describe how to further reduce matching time using a lower bound function based on LB_Keogh. Yoon-Sik Tak and Eenjun Hwang 2008
we use LB Keogh to obtain of two orders of magnitude over the brute force algorithm when doing fast correlation analysis.. Nguyen and Shiri CIKM 08
showed that their tight lower bound LB Keogh could also be used in rotation-invariant image matching and provided a novel solution for the DTW distance. Their solution is excellent.. Kim et all DEXA08
The disadvantage of DTW is its quadratic time complexity but we address this issue by using (LB_Keogh) lower bound based pruning that provides approximately linear time complexity. Chandola, Cheboli, and Vipin Kumar 2009
the whole process of finding the nearest neighbours can be sped up by using a lower-bounding function called LB Keogh that can be computed in linear time. T. Knorr et al. 2009.
LB_Keogh substantially reduce the computational expense required. Rajshekhar et al 2007
To reduce the computational time and (quadratic) complexity inherent in DTW, we apply Keogh minimum bounds, to quickly determine candidates for the set of nearest neighbors. Dalal , Kawaler, and Tucker 2009
a simple but nearly optimal way to compute a lower bound to the DTW between any two times series, called LB_Keogh.. Daniel Lemire 2008
Since we use the DTW as our matching method, we can use the LB_Keogh distance.. Kim & Tak & Hwang 2009
(for )handling complex video histograms (we us) LBKeogh, a DTW filter technique. Assent, Kremer, Seidl . DASFAA 2010
We used the LB_Keogh function as in [10] as it has been proven to guarantee no false dismissals and returns results close to the real distance function. IJCAI09 Heras et al
The tightest lower bound of DTW, between a query envelope E(Q) and a data sequence S, is known as LBKeogh Han et al SIGMOD 2011
To our best knowledge, LB_Keogh is the best lower bounding technique for DTW approaches.. Volny, Novak and Zezul 2011.
we hierarchically used several low bound functions, such as Fourier_Dist, MINDIST and LB_Keogh (to reterive 3D shapes). Tak and Hwang MMEDIA 2011
More advanced scaling techniques include lower-bounding, like LB Keogh. Buza,et al. Healthcare Informatics, Imaging and Systems Biology 2011
However, the computation of the MSE becomes efficient for large databases of shape descriptors using the lower bound and early abandon criteria suggested by Keogh. Huber-Mork et al. MVA 2011
We chose LBKeogh as the basis of our MultiDTW.. Kremer, Gunnemann, Ivanescu, Assent and Seidl. SSDBM 2011

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..)
L = (eq 7 of VLDB03 paper for DTW, eq 7 of VLDB04 paper for uniform scaling, or..)
Q = (any time series query)

Then LB_Keogh can be expressed in the following single line of matlab...

LB_Keogh = sqrt(sum([[Q > U].* [Q-U]; [Q < L].* [L-Q]].^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.

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 mulit-dimensional 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!

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 User-Perceived 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