A geometrical solution to time series searching invariant to shifting and scaling

The technique of searching for similar patterns among time series data is very useful in many applications. The problem becomes difficult when shifting and scaling are considered. We find that we can treat the problem geometrically and the major contribution of this paper is that a uniform geometrical model that can analyze the existing related methods is proposed. Based on the analysis, we conclude that the angle between two vectors after the Shift-Eliminated Transformation is a more intrinsical similarity measure invariant to shifting and scaling. We then enhance the original conical index to adapt to the geometrical properties of the problem and compare its performance with that of sequential search and R^*-tree. Experimental results show that the enhanced conical index achieves larger improvement on R^*-tree and sequential search in high dimension. It can also keep a steady performance as the selectivity increases. Part of the result related to the geometrical model has been published in the Proceedings of the 18th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp 237–248. Mi Zhou was born in China. He received his BS and MS degrees in computer science from the Northeastern University, China, in 1999 and 2002, respectively. He is currently pursuing the Ph D degree in the Computer Science and Engineering Department, The Chinese University of Hong Kong. His research interests include indexing of time series data, high-dimensional index, and sensor network. Man-Hon Wong received his BSc and MPhil degrees from The Chinese University of Hong Kong in 1987 and 1989 respectively. He then went to University of California at Santa Barbara where he got the PhD degree in 1993. Dr. Wong joined The Chinese University of Hong Kong in August 1993 as an assistant professor. He was promoted to associate professor in 1998. His research interests include transaction management, mobile databases, data replication, distributed systems, and computer and network security. Kam-Wing Chu was born in Hong Kong. He received his BS and MPhil degrees in computer science and engineering from The Chinese University of Hong Kong. When he was in Hong Kong, his research interests included database indexing of high dimensional data, and data mining. He later went to United States and received his MS degree in computer science from University of Maryland at College Park. While he was in Maryland, he focused on high performance implementation and algorithm design of advanced database systems. He is currently a senior software engineer in Server Performance group at Actuate Corporation. His expertise is in enterprise software development and software performance optimization.