Publication
PAKDD 2001
Conference paper

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

View publication

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.

Date

Publication

PAKDD 2001

Authors

Topics

Share