bSAX: A Novel Sketch for Efficient Data Series Similarity Search

In contemporary applications of data analysis, data series similarity search holds great significance. A substantial body of research design data series indices for exact similarity search. The iSAX family, employing iSAX sketch to represent a SAX collection, stands as a pivotal research direction. However, we find a critical flaw in the iSAX sketch that its representation of SAX collections leads to a significant deterioration in the lower bound distance, thereby impacting the pruning efficiency and search performance of the index. To address the limitation, we propose a novel sketch, called bSAX. bSAX, by leveraging boundary information from SAX summarizations, offers a tighter lower bound distance than iSAX. Moreover, we design a novel index for data series, with a cost model involving compressed information loss. Conducting comprehensive experimental comparisons, we validate the superior performance of bSAX in the similarity search.