Abstract Dynamic Time Warping (DTW) is a well-known similarity measure for time series. The standard dynamic programming approach to compute the DTW distance of two length-n time series, however, requires $$O(n^2)$$ O ( n 2 ) time, which is often too slow for real-world applications. Therefore, many heuristics have been proposed to speed up the DTW computation. These are often based on lower bounding techniques, approximating the DTW distance, or considering special input data such as binary or piecewise constant time series. In this paper, we present a first exact algorithm to compute the DTW distance of two run-length encoded time series whose running time only depends on the encoding lengths of the inputs. The worst-case running time is cubic in the encoding length. In experiments we show that our algorithm is indeed fast for time series with short encoding lengths.

Abstract Computing a sample mean of time series under dynamic time warping is NP-hard. Consequently, there is an ongoing research effort to devise efficient heuristics. The majority of heuristics have been developed for the constrained sample mean problem that assumes a solution of predefined length. In contrast, research on the unconstrained sample mean problem is underdeveloped. In this article, we propose a generic average-compress (AC) algorithm to address the unconstrained problem. The algorithm alternates between averaging (A-step) and compression (C-step). The A-step takes an initial guess as input and returns an approximation of a sample mean. Then the C-step reduces the length of the approximate solution. The compressed approximation serves as initial guess of the A-step in the next iteration. The purpose of the C-step is to direct the algorithm to more promising solutions of shorter length. The proposed algorithm is generic in the sense that any averaging and any compression method can be used. Experimental results show that the AC algorithm substantially outperforms current state-of-the-art algorithms for time series averaging.

Averaging time series under dynamic time warping is an important tool for improving nearest-neighbor classifiers and formulating centroid-based clustering. The most promising approach poses time series averaging as the problem of minimizing a Fréchet function. Minimizing the Fréchet function is NP-hard and so far solved by several heuristics and inexact strategies. Our contributions are as follows: we first discuss some inaccuracies in the literature on exact mean computation in dynamic time warping spaces. Then we propose an exponential-time dynamic program for computing a global minimum of the Fréchet function. The proposed algorithm is useful for benchmarking and evaluating known heuristics. In addition, we present an exact polynomial-time algorithm for the special case of binary time series. Based on the proposed exponential-time dynamic program, we empirically study properties like uniqueness and length of a mean, which are of interest for devising better heuristics. Experimental evaluations indicate substantial deficits of state-of-the-art heuristics in terms of their output quality.

This contribution extends linear classifiers to sub-linear classifiers for graphs and analyzes their properties. The results are (i) a geometric interpretation of sub linear classifiers, (ii) a generic learning rule based on the principle of empirical risk minimization, (iii) a convergence theorem for the margin perceptron in the separable case, and (iv) the VC-dimension of sub linear functions. Empirical results on graph data show that the perceptron and margin perceptron algorithm on graphs have similar properties as their vectorial counterparts.

Collaborative filtering recommender systems often use nearest neighbor methods to identify candidate items. In this paper we present an inverted neighborhood model, k-Furthest Neighbors, to identify less ordinary neighborhoods for the purpose of creating more diverse recommendations. The approach is evaluated two-fold, once in a traditional information retrieval evaluation setting where the model is trained and validated on a split train/test set, and once through an online user study (N=132) to identify users' perceived quality of the recommender. A standard k-nearest neighbor recommender is used as a baseline in both evaluation settings. Our evaluation shows that even though the proposed furthest neighbor model is outperformed in the traditional evaluation setting, the perceived usefulness of the algorithm shows no significant difference in the results of the user study.

Collaborative Filtering Recommender Systems come in a wide variety of variants. In this paper we present a system for visualizing and comparing recommendations provided by different collaborative recommendation algorithms. The system utilizes a set of context-aware, hybrid, and other collaborative filtering solutions in order to generate various recommendations from which its users can pick those corresponding best to their current situation (i.e. context). All user interaction is fed back to the system in order to additionally improve the quality of the recommendations. Additionally, users can explicitly ask the system to treat certain recommenders as more important than others, or disregard them completely if the list of recommended movies is not to their liking.

Recommender systems are commonly evaluated by trying to predict known, withheld, ratings for a set of users. Measures such as the Root-Mean-Square Error are used to estimate the quality of the recommender algorithms. This process does however not acknowledge the inherent rating inconsistencies of users. In this paper we present the first results from a noise measurement user study for estimating the magic barrier of recommender systems conducted on a commercial movie recommendation community. The magic barrier is the expected squared error of the optimal recommendation algorithm, or, the lowest error we can expect from any recommendation algorithm. Our results show that the barrier can be estimated by collecting the opinions of users on already rated items.

The median and mean graph are basic building blocks for statistical graph analysis and unsupervised pattern recognition methods such as central clustering and graph quantization. This contribution provides sufficient conditions for consistent estimators of true but unknown central points of a distribution on graphs.

Bimal, a fast method for approximately solving the maximum contact map overlap (maxCMO) problem is introduced. The method is based on an approximate model of the maxCMO-problem using the generic bipartite graph matching framework, which is then optimally solved by double dynamic programming. The performance of Bimal has been evaluated in an empirical comparative study including clustering of protein structures according to the SCOP fold's level. Solving about 800 pairwise alignments of medium-sized proteins takes less than 1 min on a 1.7 GHz machine and yields good results for similar protein structures. Bimal accurately classified proteins in agreement with the SCOP classification. In particular, for similar proteins, Bimal provides a good tradeoff between computation speed and solution quality and is because of its high speed useful for solving large-scaled maxCMO applications.

We show that multiple structure alignment (MStA) using contact maps is equivalent to the problem of finding a sample mean of contact maps. From this result, we derive a subgradient method for solving the MStA method. Experiments show that the proposed algorithm is a flexible alignment method that provides an excellent tradeoff between accuracy and speed.

We present an analytic and geometric view of the sample mean of graphs. The theoretical framework yields efficient subgradient methods for approximating a structural mean and a simple plug-in mechanism to extend existing central clustering algorithms to graphs. Experiments in clustering protein structures show the benefits of the proposed theory.

We propose a multi-layer perceptron for learning on data represented in terms of attributed graphs. The approach is based on the idea to associate each simple perceptron with an attributed weight graph and to provide a concept similar to the inner product of vectors in the domain of graphs. This is achieved by the Schur-Hadamard inner product of graphs. To provide a supervised learning mechanism we customize the feed-forward pass, the error-back-propagation algorithm, and the error correcting rule. In first experiments, the proposed algorithm is successfully applied to function the regression and classification tasks. The results show better performance than support vector and nearest neighbor classifiers.

We develop a new mathematical framework, which embeds weighted graphs into quasi metric spaces. This concept establishes a theoretical basis to apply neural learning machines for structured data. To exemplarily illustrate the applicability of metric graph spaces, we propose and analyze a perceptron learning algorithm for graphs in its primal and dual form.