Abstract Neural networks are widely used in machine learning and data mining. Typically, these networks need to be trained, implying the adjustment of weights (parameters) within the network based on the input data. In this work, we propose a novel approach, RandomNet, that employs untrained deep neural networks to cluster time series. RandomNet uses different sets of random weights to extract diverse representations of time series and then ensembles the clustering relationships derived from these different representations to build the final clustering results. By extracting diverse representations, our model can effectively handle time series with different characteristics. Since all parameters are randomly generated, no training is required during the process. We provide a theoretical analysis of the effectiveness of the method. To validate its performance, we conduct extensive experiments on all of the 128 datasets in the well-known UCR time series archive and perform statistical analysis of the results. These datasets have different sizes, sequence lengths, and they are from diverse fields. The experimental results show that the proposed method is competitive compared with existing state-of-the-art methods.

With increasing powering of data storage and advances in data generation and collection technologies, large volumes of time series data become available and the content is changing rapidly. This requires the data mining methods to have low time complexity to handle the huge and fast-changing data. This paper presents a novel time series clustering algorithm that has linear time complexity. The proposed algorithm partitions the data by checking some randomly selected symbolic patterns in the time series. Theoretical analysis is provided to show that group structures in the data can be revealed from this process. We evaluate the proposed algorithm extensively on all 85 datasets from the well-known UCR time series archive, and compare with the state-of-the-art approaches with statistical analysis. The results show that the proposed method is faster, and achieves better accuracy compared with other rival methods.

The discovery of motifs (repeated patterns) is an important task in time series data mining. The task can be formulated as finding the most similar non-overlapping pair of subsequences in a given time series. Existing exact motif discovery methods have quadratic time complexities in the length of the time series. In this work, we present an algorithm that can find the exact motif of a given time series in a linear expected time complexity. The algorithm is further modified to find all pairs of subsequences whose distances are below a given threshold value. In practice, if true motifs exist in the data or the threshold is set to a small value, the algorithms are very fast. The proof of correctness and time complexity are detailed and experiments are conducted to verify the analysis. We applied the proposed method to analyze the real-world bird sound and electrical consumption data to demonstrate its effectiveness.

The mining of time series data has attracted much attention in the past two decades due to the ubiquity of time series in our daily lives. In particular, classification is perhaps one of the most well-studied topics for time series data. Many state-of-the-art classification techniques work by identifying and extracting patterns or characteristics from the training data, and then applying these patterns or characteristics to classify unlabeled time series. This paper presents a novel finding that sequences of values that are very different from the patterns in the labeled time series can be used as references to classify time series effectively. We propose an evolution process to generate these sequences of values, which we call separating references, from the training data. The proposed method is robust to over-fitting and is especially suitable for the situation where little labeled data is available. We demonstrate that the proposed approach is highly competitive on the well-known UCR time series classification benchmarks.

Time series classification has attracted much attention due to the ubiquity of time series. With the advance of technologies, the volume of available time series data becomes huge and the content is changing rapidly. This requires time series data mining methods to have low computational complexities. In this paper, we propose a parameter-free time series classification method that has a linear time complexity. The approach is evaluated on all the 85 datasets in the well-known UCR time series classification archive. The results show that the new method achieves better overall classification accuracy performance than the widely used benchmark, i.e. 1-nearest neighbor with dynamic time warping, while consuming orders of magnitude less running time. The proposed method is also applied on a large real-world bird sounds dataset to verify its effectiveness.

We propose a semi-Lagrangian method for multiphase interface tracking. In contrast to previous methods, our method maintains an explicit polygonal mesh, which is reconstructed from an unsigned distance function and an indicator function, to track the interface of arbitrary number of phases. The surface mesh is reconstructed at each step using an efficient multiphase polygonization procedure with precomputed stencils while the distance and indicator function are updated with an accurate semi-Lagrangian path tracing from the meshes of the last step. Furthermore, we provide an adaptive data structure, multiphase distance tree, to accelerate the updating of both the distance function and the indicator function. In addition, the adaptive structure also enables us to contour the distance tree accurately with simple bisection techniques. The major advantage of our method is that it can easily handle topological changes without ambiguities and preserve both the sharp features and the volume well. We will evaluate its efficiency, accuracy and robustness in the results part with several examples.

In this paper, a new surface tension formulation is presented for Smoothed Particle Hydrodynamics in fluid simulation, especially small-scale detailed fluid animation. The surface tension formulation is decomposed into three processes: (1) mesh smoothing exploited a Lagrangian operator in a volume-preserved way, (2) surface tension computation between the original mesh and smoothed mesh, (3) surface tension transfer from mesh vertices onto their neighbor particles. Experimental results show that the proposed surface tension formulation is effective and efficient for realistic simulations.

We introduce an adaptive hybrid level set surface tracking for fluid simulation in this paper. To improve the accuracy of the convectional level set method, we propose a method that combines the higher accuracy interpolation and octree grid to improve the accuracy while still maintain good efficiency. Adaptive gradient-augmented level set is adopted for higher accuracy interpolation and two strategies are proposed to guide the building of the octree structure. We demonstrate our method with several level set tests, and couple it to several existing fluid simulators. The results show that our method facilitates significant improvements in accuracy and efficiency, and is effective for free surface fluid simulation in capturing fluid details.

We present an efficient interactive system for dressing a naked bird with feathers. In our system, a skeleton associated with guide feathers is used to describe the distribution of the body feathers. The special skeleton can be easily built by the user, given a 3D bird model as input. To address the problem of interpenetrations among feathers, the growth priority between the feather roots is defined, with which we obtain the growth order from a greedily constructed directed acyclic graph. Each feather is then adjusted in that order by a height field based collision resolution process. The height field not only provides an efficient way to detect the collision but also enables us to finely control the degree of collision during feather adjustments. The results show that our approach is capable of resolving the collisions among thousands of feathers in a few seconds. If model animation is desired, the feathers can be adjusted on the fly at interactive framerates. Details of our implementation are provided with several examples to demonstrate the effectiveness of our system.

We introduce a novel framework for tracking multiphase interfaces with explicit contouring technique. In our framework, an unsigned distance function and an additional indicator function are used to represent the multiphase system. Our method maintains the explicit polygonal meshes that define the multiphase interfaces. At each step, distance function and indicator function are updated via semi-Lagrangian path tracing from the meshes of the last step. Interface surfaces are then reconstructed by polygonization procedures with precomputed stencils and further smoothed with a feature-preserving non-manifold smoothing algorithm to stay in good quality. Our method is easy to be implemented and incorporated into multiphase simulation, such as immiscible fluids, crystal grain growth and geometric flows. We demonstrate our method with several level set tests, including advection, propagation, etc., and couple it to some existing fluid simulators. The results show that our approach is stable, flexible, and effective for tracking multiphase interfaces.

ABSTRACT This paper presents a novel approach for simulating the dynamic coupling between a tree and raindrops based on physical deformation and fluid simulation. By the approach, tree animation in the rain can be simulated in a two‐resolution way: branch motion and leaf motion. The branch is represented by the Euler–Bernoulli beam model, and the leaf petiole is represented by the three‐prism elastic model. Interaction coupling liquid motion on the hydrophilic surface with a flexible petiole is well implemented by a special design. To simplify the computation process, instead of the computation‐intensive three‐dimensional Navier–Stokes equations, shallow water equations are used to simulate the water dynamics together with the whole leaf deformation. Simulation has been also made to various phenomena incurred from the interactive coupling. These include, among others, part of impacting raindrops splashing into the air with the remaining flowing along the slant of the leaf and merging into larger ones or hanging on the blade boundary, with the leaf rebounding and vibrating after the drops fall off the leaf. A level‐of‐detail approach is exploited to accelerate rendering in views of different distances. The experimental results illustrate that the approach can be applied to efficiently generate realistic details of the interactive coupling between a tree and raindrops. Copyright © 2012 John Wiley & Sons, Ltd.