Many applications on time series data require solving the subse- quence search problem, which has been extensively studied in the database and data mining communities. These applications are computation bound rather than disk I/O bound. In this work, we further propose effective and cheap lower-bounds to reduce the computation cost of the subsequence search problem. Experimen- tal studies show that the proposed lower-bounds can boost the per- formance of the state-of-the-art solution by up to an order of mag- nitude.