A Novel Parallel Scheme for Fast Similarity Search in Large Time Series

The similarity search is one of the fundamental components in time series data mining,e.g.clustering,classification,association rules mining.Many methods have been proposed to measure the similarity between time series,including Euclidean distance,Manhattan distance,and dynamic time warping(DTW).In contrast,DTW has been suggested to allow more robust similarity measure and be able to find the optimal alignment in time series.However,due to its quadratic time and space complexity,DTW is not suitable for large time series datasets.Many improving algorithms have been proposed for DTW search in large databases,such as approximate search or exact indexed search.Unlike the previous modified algorithm,this paper presents a novel parallel scheme for fast similarity search based on DTW,which is called MRDTW(MapRedcuebased DTW).The experimental results show that our approach not only retained the original accuracy as DTW,but also greatly improved the efficiency of similarity measure in large time series.

Surface crack imaging based on delayed temperature difference at symmetric points by laser spot thermography

Laser spot thermography is a novel technique for the detection of surface cracks with a laser to heat sample locally and with an IR camera to record the surface temperature distribution. Common methods to characterize cracks are only suitable for the situation that the laser scanning path is vertical to the crack. But due to the randomness of cracks,when the scanning path is parallel to the crack,surface cracks cannot be detected by these methods. To tackle this problem,a method is presented which is suitable for the situation that the scanning path is parallel to crack. The main idea is to evaluate the crack-caused asymmetries of the surface temperature distribution. The effect of temperature gradient and the maximum scanning interval are analyzed by a 2D simulation. A new crack imaging technique is presented that is based on delayed temperature difference at symmetric points to characterize the crack in the thermal image. Compared well with those obtained by the spatial first derivative method,experimental results are shown to efficiently prove this method.

A new synchronization in parallel shortest paths analysis for massive road networks

To effectively solve the single-source shortest path(SSSP)problem for massive road networks in geographical information systems,a new synchronization method is proposed in the implementations of parallel SSSP algorithm.It applies spinlock by inline assembly language for the sake of small overheads of controlling the interaction of multiple threads.The performance of our method is compared with widely used Pthreads application programming interfaces and the powerful sequential solution given by DIMACS.The experimental platform is a shared address space workstation with two processors(i.e.eight cores)at a clock speed of 3 GHz.Problem instances for experiments contain a directed road networks of the USA with more than 23 million vertices and 57 million edges,and its 11 subnetworks of variant sizes.This method answers the SSSP of the USA road network in 1231 ms,while Pthreads costs 1808 ms and DIMACS sequential solution takes 4856 ms.It achieves a speedup of 3.95,which is 47%faster than Pthreads with the speedup of 2.69.When the size of instance is larger,our method achieves a better performance.

Parallel Critical Path Tracing——A Fault Simulation Algorithm for Combinational Circuits

Critical path tracing,a fault simulation method for gate-level combinational circuits,is extended to theparallel critical path tracing for functional block-level combinational circuits.If the word length of the hostcomputer is m,then the parallel critical path tracing will be approximately m times faster than the originalone.

Hochschild cohomology of Beilinson algebra of exterior algebra

Let An be the Beilinson algebra of exterior algebra of an n-dimensional vector space, which is derived equivalent to the endomorphism algebra Endox （T） of a tilting complex T = II^ni=0^Ox （i） of coherent COx-modules over a projective scheme X = P^nk. In this paper we first construct a minimal projective bimodule resolution of An, and then apply it to calculate k-dimensions of the Hochsehild cohomology groups of An in terms of parallel paths. Finally, we give an explicit description of the cup product and obtain a Gabriel presentation of Hochschild cohomology ring of An. As a consequence, we provide a class of algebras of finite global dimension whose Hochschild cohomology rings have non-trivial multiplicative structures.