We study the problem of online similarity search in sequences of temporal intervals; given a standing query and a time-evolving sequence of event-intervals, we want to assess the existence of the query in the sequence over time. Since indexing is inapplicable to our problem, the goal is to reduce runtime without sacrificing retrieval accuracy. We present three lower-bounding and two early-abandon methods for speeding up search, while guaranteeing no false dismissals. We present a framework for combining lower bounds with early abandoning, called ABIDE. Empirical evaluation on eight real datasets and two synthetic datasets suggests that ABIDE provides speedups of at least an order of magnitude and up to 6977 times on average, compared to existing approaches and a baseline. We conclude that ABIDE is more powerful than existing methods, while we can attain the same pruning power with less CPU computations.