It is known that, when normalized by$n$as$n \rightarrow \infty$, the expected length of a longest common subsequence of$d$random strings of length$n$over an alphabet of size$\sigma$converges to a constant that depends only on$d$and$\sigma$. These values are known as the Chvátal-Sankoff constants, and determining their exact values is a major open problem. Building on previous algorithms for lower-bounding the constants, we implement parallelization, introduce significant runtime optimizations, and design an efficient recursive memory reading and writing scheme. With this, we obtain a new best lower bound of 0.792665992 for$\sigma=2, d=2$. We additionally improve upon almost all previously reported lower bounds for the Chvátal-Sankoff constants when either the size of alphabet, the number of strings, or both are larger than 2.

Correlation-based analytics of time series data is important for a wide range of applications from stock analysis to weather forecasting. Yet performing these analytics at the granularity of subsequences of time series is prohibitively costly for large data sets. Our proposed framework CORAL (CORrelation based AnaLytics) tackles this challenge by adopting a preprocess-once and query-many-times paradigm. In a preprocessing step, CORAL compresses time series data into compact clusters, each identified by a unique representative, taking advantage of the Euclidean distance triangle inequality property. Using a mapping between the metric Euclidean distance and non-metric Pearson correlation, we establish inter- and intra-cluster correlation bounds as foundation for CORAL processing. In the CORAL model, inter-cluster correlation relationships are captured as a compact overlay graph with representatives as nodes and the correlation between cluster representatives as edges. The two CORAL bounds support time series matching by realizing the comparison among the cluster representatives at the abstract level in the CORAL graph model in place of the underlying huge collection of raw time series. The resulting CORAL model effectively supports a rich set of analytics operations including retrieval of the best-correlated subsequence, self-correlation, and detection of groups of correlated subsequences. Our comprehensive experimental evaluation on 85 real benchmark datasets demonstrates that CORAL is many fold faster than state-of-the-art systems while returning highly accurate results.

Continuous growth in sensor data and other temporal sequence data necessitates efficient retrieval and similarity search support on these big time series datasets. However, finding exact similarity results, especially at the granularity of subsequences, is known to be prohibitively costly for large data sets. In this paper, we thus propose an efficient framework for solving this exact subsequence similarity match problem, called TINN (TIme series Nearest Neighbor search). Exploiting the range interval diversity properties of time series datasets, TINN captures similarity at two levels of abstraction, namely, relationships among subsequences within each long time series and relationships across distinct time series in the data set. These relationships are compactly organized in an augmented relationship graph model, with the former relationships encoded in similarity vectors at TINN nodes and the later captured by augmented edge types in the TINN Graph. Query processing strategy deploy novel pruning techniques on the TINN Graph, including node skipping, vertical and horizontal pruning, to significantly reduce the number of time series as well as subsequences to be explored. Comprehensive experiments on synthetic and real world time series data demonstrate that our TINN model consistently outperforms state-of-the-art approaches while still guaranteeing to retrieve exact matches.

Domain-specific distances preferred by analysts for exploring similarities among time series tend to be "point-to-point" distances. Unfortunately, this point-wise nature limits their ability to perform meaningful comparisons between sequences of different lengths and with temporal mis-alignments. Analysts instead need "elastic" alignment tools such as Dynamic Time Warping (DTW) to perform such flexible comparisons. However, the existing alignment tools are limited in that they do not incorporate diverse distances. To address this shortcoming, our work introduces the first conceptual framework called Generalized Dynamic Time Warping (GDTW) that supports now alignment (warping) of a large array of domain-specific distances in a uniform manner. While the classic DTW and its prior extensions focus on the Euclidean Distance, our GDTW is the first method that generalizes the ubiquitous DTW and "extends" its warping capabilities to a rich diversity of point-to-point distances. Based on our GDTW paradigm that preserves the efficiency of the dynamic programming paradigm of DTW, we design an abstraction that implemented by our GDTW Design Tool enables analysts to "warp" new distances with little programming effort. Through extensive evaluation studies on 85 real public domain benchmark datasets, we show that our newly warped distances offer higher classification accuracy than the previously available distances for the majority of these datasets. Further, our case study on heart arrhythmia data illustrates the utility of the new distances enabled by our GDTW warping methodology.

Modern applications in this digital age collect a staggering amount of time series data from economic growth rates to electrical household consumption habits. To make sense of it, domain analysts interactively sift through these time series collections in search of critical relationships between and recurring patterns within these time series. The ONEX (Online Exploration of Time Series) system supports effective exploratory analysis of time series collections composed of heterogeneous, variable-length and misaligned time series using robust alignment dynamic time warping (DTW) methods. To assure real-time responsiveness even for these complex and compute-intensive analytics, ONEX precomputes and then encodes time series relationships based on the inexpensive-to-compute Euclidean distance into the ONEX base. Thereafter, based on a solid formal foundation, ONEX uses DTW-enhanced analytics to correctly extract relevant time series matches on this Euclidean-prepared ONEX base. Our live interactive demonstration shows how our ONEX exploratory tool, supported by a rich array of visual interactions and expressive visualizations, enables efficient mining and interpretation of the MATTERS real data collection composed of economic, social, and education data trends across the fifty American states.

Finding similar trends among time series data is critical for applications ranging from financial planning to policy making. The detection of these multifaceted relationships, especially time warped matching of time series of different lengths and alignments is prohibitively expensive to compute. To achieve real time responsiveness on large time series datasets, we propose a novel paradigm called Online Exploration of Time Series (ONEX) employing a powerful one-time preprocessing step that encodes critical similarity relationships to support subsequent rapid data exploration. Since the encoding of a huge number of pairwise similarity relationships for all variable lengths time series segments is not feasible, our work rests on the important insight that clustering with inexpensive point-to-point distances such as the Euclidean Distance can support subsequent time warped matching. Our ONEX framework overcomes the prohibitive computational costs associated with a more robust elastic distance namely the DTW by applying it over the surprisingly compact knowledge base instead of the raw data. Our comparative study reveals that ONEX is up to 19% more accurate and several times faster than the state-of-the-art. Beyond being a highly accurate and fast domain independent solution, ONEX offers a truly interactive exploration experience supporting novel time series operations.