The S²-Tree: An index structure for subsequence matching of spatial objects

Abstract

We present the S2-Tree, an indexing method for subsequence matching of spatial objects. The S2-Tree locates subsequences within a collection of spatial sequences, i.e., sequences made up of spatial objects, such that the subsequences match a given query pattern within a speci-fied tolerance. Our method is based on (i) the string-searching techniques that locate substrings within a string of symbols drawn from a discrete alphabet (e.g., ASCII characters) and (ii) the spatial access methods that index (unsequenced) spatial objects. Particularly, the S2-Tree can be ap- plied to solve problems such as subsequence matching of time-series data, where features of subsequences are often extracted and mapped into spa- tial objects. Moreover, it supports queries such as "what is the longest common pattern of the two time series?", which previous subsequence matching algorithms find difficult to solve efficiently.