Sequence similarity computation aims to quantify how similar two sequences are by assigning a similarity score. In this study, we focus on the problem of identifying sequences that are similar to a given query sequence provided by a user. Measuring this similarity is important in several applications, such as in mobility field, where analyzing users’ travel patterns can help improve traffic management. Other examples include the classification of similar users and the recommendation of points/sequences. In those examples, the size of the sequences is rarely over ten points. Existing methods predominantly rely on applying a similarity function to each candidate sequence to identify those that are sufficiently similar. However, this approach becomes computationally expensive when dealing with large-scale datasets. To mitigate this challenge, we propose SISIS, an efficient method that uses sequence indexing to quickly retrieve similar sequences that share common points with the query sequence in the same order. Furthermore, to account for scenarios where points in sequences may not exactly match but are contextually similar, we introduce SISIS*, a variant of SISIS that incorporates point embeddings. This extension allows for more comprehensive retrieval of similar sequences by considering semantics similarities between points, beyond mere exact matches. Extensive experimental evaluations show that the proposed approach significantly outperforms a baseline method based on the well-known Longest Common SubSequence (LCSS) measure for all reasonable query sizes up to 17, i.e. sequences containing 17 points, yielding substantial performance improvements across various real-world datasets.