# SISIS: Sequence Indexing for Similarity Search

Sara Jarrad, Hubert Naacke, Stéphane Gançarski

► To cite this version:

Sara Jarrad, Hubert Naacke, Stéphane Gançarski. SISIS: Sequence Indexing for Similarity Search. Transactions on Large-Scale Data- and Knowledge-Centered Systems LIX: Special Issue on Data Management - Principles, Technologies, and Applications, 16240, Springer Berlin Heidelberg, pp.32-60, 2025, Lecture Notes in Computer Science, 978-3-662-72449-1. 10.1007/978-3-662-72449-1_2. hal-05502339

HAL Id: hal-05502339

https://hal.science/hal-05502339v1

Submitted on 10 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# SISIS: Sequence Indexing for Similarity Search

Sara Jarrad[0009-0004-1794-956X], Hubert Naacke[0000-0003-0559-9908], and Stéphane Gançarski[0000-0002-5252-5314]

LIP6, Sorbonne University, Paris, France

`{sara.jarrad, hubert.naacke, stephane.gancarski}@lip6.fr`

<figure><img src="image_2.png" /></figure>

**Abstract.** 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 Sub-Sequence (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.

**Keywords:** Sequence · Similarity search · Sequence indexing.

## 1 Introduction and motivation

The amount of information published on the web has been steadily increasing over the years. Among this vast amount of data, geolocalized information shared by users on social networking platforms—through photos, tags, comments, and other interactions—plays a crucial role in describing mobility behavior. This data is particularly valuable as it enables the reconstruction of user trajectories, which are defined as sequences of points (locations) visited by a user in chronological order.
Measuring sequence similarity is a core task in many applications, as it quantifies how alike two sequences are. This capability is particularly useful for retrieving sequences that are similar to a given query sequence *q*, typically of reasonable length—containing fewer than five or six points. In the context of mobility, it can support tasks such as user classification or the recommendation of locations/sequences, among others.

Our goal is to develop a similarity measure that is both accurate and efficient. However, this task is inherently challenging, and numerous approaches have been proposed to tackle it, each with its own strengths and limitations. Choosing the right similarity measure ultimately depends on the specific needs and constraints of the application.

Many research studies have focused on quantifying the similarity between two sequences using established measures such Edit Distance on Real Sequence (EDR) [7], and Edit Distance with Real Penalty (ERP) [6]. These measures are designed on edit operations to handle noise-related issues, gaps, or local misalignments among sequences. However, they have a major limitation which is their high computational cost, especially when they are used on large datasets.

Dynamic Time Warping (DTW) [2,29] constitutes another extensively used measure. It aligns time series by minimizing the cumulative distance between their points through a flexible time warping path. While DTW is computationally outperforming exhaustive edit-based measures, it relies fundamentally on pointwise distance computations, most commonly the Euclidean distance. However, it is not applicable to our case, as we do not consider euclidean distances between points. Our focus is solely on the sequential nature of the data, while disregarding its spatio-temporal dimension. This choice allows us to generalize an appropriate approach to various types of sequences beyond mobility sequences. Longest Common SubSequence (LCSS) [12, 13, 20], is a measure that can be applied to sequential only data. It is the length of the longest common subsequence of points within two sequences, where two compared points are considered to match only if they are identical.

<figure><img src="image_3.png" /><figcaption>Fig. 1: Use case of LCSS on mobility sequences</figcaption></figure>
Figure 1 illustrates a simplified map of Paris city, highlighting its most renowned locations. An illustrative example of a user sequence is depicted by the sequence of points [2, 6, 8, 3, 4, 7], represented by a grey dotted path. This sequence corresponds to a user starting their visit at the Orsay Museum, identified by ID 2, followed by the Eiffel Tower (ID 6), then the Louvre Museum (ID 8), and so forth. The objective is to retrieve sequences similar to a given query sequence [6, 8, 3], shown as a red path. One potential solution to address this problem is the use of the Longest Common Subsequence (LCSS) measure.

LCSS-based similarity is widely regarded as one of the most effective measures
due to its robustness against various transformations that may be applied to sequences,
such as re-sampling (adding points to sequences) and handling data noise (introducing
outliers in the sequences) [16,23,27].

Despite these advantages, computing the LCSS-based similarity can be computa-
tionally expensive when applied to large datasets of sequences. In a naive approach
(baseline) for identifying sequences similar to a given query sequence *q*, the LCSS be-
tween *q* and each candidate sequence is calculated exhaustively. This inefficiency in
processing time represents a significant challenge, and is one of the primary issues we
address in this work.

To address it, we propose *SISIS* (Sequence Indexing for Similarity Search). SISIS is an efficient method that employs a sequence indexing approach to accelerate the search for similar sequences. This approach achieves the same results as the LCSS-based baseline method (see Algorithm 2), while significantly improving search speed. Moreover, SISIS allows users to specify a desired similarity threshold, defined as the number of points in common with the query, in the same sequential order.

A second issue we tackle is that exact matching based on point identification can
be overly restrictive, potentially resulting in very few or no matching sequences. In
many practical scenarios, users may not require exact point matches but instead seek
sequences whose points are contextually similar to those in the query.

In order to meet this challenge, we introduce SISIS*, a variant of SISIS that lever-
ages point embeddings generated by the Word2Vec (W2V) language model [17], to
enhance the retrieval of similar sequences, even when their points do not exactly match
but are contextually similar. SISIS* enables a broader set of results compared to the
exact matching performed by the original SISIS method.

The remainder of the paper is structured as follows. Sections 2 and 3 provide back-
ground on LCSS and review related work. Section 4 describes the exact sequence in-
dexing approach, while Section 5 explores an alternative indexing method using point
embeddings. Section 6 reports the experimental results and performance comparisons.
Finally, Section 7 concludes the paper.

## 2 Background

The algorithm described in Algorithm 1 has been detailed in [12]. It computes the size
of the longest common subsequence between two sequences. This size is later used to
compute the similarity between sequences. We extend the original version by adding
the point matching function as a parameter.
## 2.2 LCSS-based baseline

As mentioned before, to determine the sequences that are similar to a given query $q$, the LCSS between $q$ and all other sequences is calculated (Algorithm 2). Thus, the LCSS function defined in Algorithm 1 is invoked $|T|$ times.

<caption>**Algorithm 2 LCSS-based search**</caption>

S
**Require:** $q$: query sequence, $S$: threshold, $match$: point matching function
1: **function** LCSS_SEARCH($q, S, match$)
2:     $result \leftarrow \emptyset$, $cs \leftarrow [|q| \times S]$  
3:     **for** $t$ in $T$ **do**
4:         **if** LCSS($q, t, match$) $\ge$ $cs$ **then**
5:             $result \leftarrow t$
6:         **end if**
7:     **end for**
8:     **return** $result$
9: **end function**

On lines 4 and 5 of Algorithm 2 we apply the LCSS to all dataset sequences, and select one if it shares at least `cs` points with `q`. This process incurs a significant computational overhead, particularly when the dataset is very large, and we are looking to reduce it. We use Algorithm 2 as the main baseline for comparison throughout the paper. Our goal is to develop a new method, called SISIS, that retrieves similar sequences faster than this baseline.

The notations frequently used throughout this paper are summarised in Table 1.

## 3 Related work

There are several studies that address the problem of finding similar sequences, especially in the field of mobility. For instance [16] categorizes different similarity measures, discussing their respective strengths and weaknesses with regard to noise sensitivity, time shift (when an element of one sequence is shifted in time to match an element of another sequence) and sequence length. These measures are classified according to whether they are spatial *i.e.* ignoring the temporal aspect, or spatio-temporal, taking into account both the spatial and temporal dimensions of motion. Spatial measures include Euclidean, Hausdroff, and Fréchet distances. The first does not allow to compare sequences of different sizes and is not robust to noise. The second and third are based solely on the geographical shape of the sequences being compared, and are not robust to data noise or time shifts. There are other similarity measures, such as DTW, EDR and ERP, which are among the most well-known, but neither are they robust to noise.

In [16], LCSS is considered one of the best measures because it is robust to almost all transformations compared to the other measures.
<table><caption>Table 1: Notations used for similarity search</caption><thead><tr><th>Notation</th><th>Description</th></tr></thead><tbody><tr><td>q</td><td>A query sequence</td></tr><tr><td>cs</td><td>Combination size</td></tr><tr><td>T</td><td>Set of sequences</td></tr><tr><td>T'(q)</td><td>Set of all sequences that are similar to the query q</td></tr><tr><td>q ≈<sub>s</sub> t</td><td>a sequence t is similar to q for a given threshold S</td></tr><tr><td>pos(p<sub>i</sub>, t)</td><td>The position of the point p<sub>i</sub> in a sequence t</td></tr><tr><td>C<sub>|q|,cs</sub></td><td>the set of C<sub>cs</sub><sup>|q|</sup> combinations of size cs in the query q</td></tr><tr><td>p̄<sub>i</sub></td><td>An index that associates each element p<sub>i</sub> with the sequences that contain it</td></tr><tr><td>p̄<sub>i</sub>p̄<sub>j</sub></td><td>An index that associates each pair of elements p<sub>i</sub>p<sub>j</sub> with the sequences that contain it</td></tr><tr><td>sim<sub>ε</sub>(p<sub>i</sub>, p<sub>j</sub>)</td><td>p<sub>i</sub> and p<sub>j</sub> are ε-similar</td></tr><tr><td>p̄<sub>i</sub></td><td>An index that associates each point p<sub>i</sub> with the set of sequences that pass through a point p<sub>j</sub> ε-similar to p<sub>i</sub></td></tr></tbody></table>

[23,27] compare the same measures, but categorizes them differently depending on whether they are spatio-temporal or sequence-only measures, and whether they are discrete or continuous. To evaluate the robustness of each measure, transformations such as adding/removing sample points, altering the sampling rate, injecting noise (outliers), and shifting sequences were applied to the data. The authors then assessed how well each measure handled these modifications. They concluded that DTW, LCSS, and ERP were the most effective across various transformation types. Table 2 summarizes these findings. Each checkmark (✓) in the table indicates that the corresponding measure performs well under the given transformation scenario.

<table><caption>Table 2: Comparative study of similarity measures from [23,27]</caption><thead><tr><th rowspan="2">Distance Measure</th><th colspan="6">Transformation</th></tr><tr><th>Adding sample points</th><th>Deleting sample points</th><th>Different sampling rate</th><th>Spatial stretch and suppress</th><th>Adding noise</th><th>Mixed transformations</th></tr></thead><tbody><tr><td>ED</td><td></td><td></td><td></td><td></td><td></td><td>✓</td></tr><tr><td>DTW</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td></td><td>✓</td></tr><tr><td>LCSS</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>EDR</td><td></td><td></td><td></td><td></td><td>✓</td><td></td></tr><tr><td>ERP</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td></td></tr></tbody></table>

The DTW and ERP measure demonstrates the ability to handle at least four types of transformations, with LCSS standing out as the most effective in managing all transformations.

A comparative study has also been proposed by [25], which examines the four similarity measures LCSS, Fréchet, DTW and EDR. This paper highlights the differences between these four measures using real data and also shows some popular applications of these measures.
Apart from the mobility field, LCSS is used in biology for DNA alignment. Other methods which have the same purpose as LCSS are, local alignment [21,9], global alignment [18,22], multiple alignment [19], and BLAST [1]. Local alignment identifies common elements between two sequences, even if they do not overlap over their entire length. As for the global alignment, the objective is to maximize the overall similarity through the sequence alignment by taking into consideration the gaps between elements, while preserving the order of these elements. Multiple alignment aligns multiple sequences simultaneously to find common motifs among them all. Finally, Blast is used to find regions of similarity between biological sequences based on local alignment. All of these measures are effective, but they are all complex on a large scale.

In summary, there are a variety of methods, using different approaches to solve sequence similarity search problem, and the works cited explore the differences between them. All methods have advantages and disadvantages. However, according to the experimental validation used in [16,23,27], LCSS remains one of the most robust to various mentioned transformations. Thus we base our work on this measure.

The issue of those cited works is that they do not address the cost problem. In fact, these methods are effective when applied to a small dataset. Once scaled up, they become very costly and time consuming.

[5] uses efficient algorithms for finding a longest common increasing subsequence among *m* sequences. However, the authors assume that the sequences of points they use are increasing, i.e. the points are ordered by increasing values. In our case, we represent a point by its id, so, if the points were ordered by their values, the order of the point visits would be lost. Therefore, the solution is not applicable to our problem.

[11] uses a dual-match method for matching sub-sequences. Their aim is to find all the subsequences (from a very large data sequence) that are similar to a given input query. The authors of [11] propose a complex solution, by slicing the data sequence and the query into windows, then representing it in the form of multi-dimensional vectors, then applying the LCSS using a parameter to match intervals in the time dimension. They apply their method to time series data: their index is based on the data value and the elapsed time between two consecutive points, which is not the case for us.

Some other recent works such as [10,4] have proposed solutions to approximate LCSS in linear time (instead of quadratic time as for Algorithm 1) with respect to the size of sequences. This makes the computation time of LCSS faster. However, the problem with these approaches is that they do not give the exact results provided by LCSS, but rather an approximation using probability to make a tradeoff between accuracy and efficiency.

Whereas these works compute LCSS whatever the size of the longest common sub-sequence, we study a different problem where the minimal size of the sub-sequence to retrieve is specified by the user.

# 4 Exact sequence indexing

This section introduces the main contribution of this work: an indexing method designed for the efficient retrieval of similar sequences.
Let $T = \{t_1, \dots, t_n\}$ represent a set of sequences, and let $T'(t, S)$ denote the subset of sequences in $T$ that are sufficiently similar to a given sequence $t$, based on a specified similarity threshold $S$, as formally defined in Section 2.1. The proposed method employs sequence indexing to efficiently compute $T'(t, S)$.

The key advantage of this indexing approach, compared to the baseline method outlined in Algorithm 2, which performs pairwise comparisons of each sequence in $T$ with $t$, is its ability to reduce the number of candidate sequences. By narrowing down the search space, the indexing method is expected to significantly improve retrieval speed for queries of a reasonable size.

## 4.1 Definition of sequence index

**Definition 1 (Single point index).** The sequence index 1P : $p_i \mapsto \bar{p}_i$ associates each point $p_i$ with the set $\bar{p}_i$, which consists of all sequences that pass through $p_i$. This set is formally defined as:

$$ \bar{p}_i = \{t \in T \mid p_i \in t\} $$

**Definition 2 (Point pair index).** The sequence index 2P : $(p_i, p_j) \mapsto \overline{p_i p_j}$ associates a pair of points $(p_i, p_j)$ with the set $\overline{p_i p_j}$ of sequences that pass through $p_i$ then through $p_j$ (i.e. $p_i$ precedes $p_j$) and defined by:

$$ \overline{p_i p_j} = \{t \in T \mid p_i, p_j \in t \text{ and } \text{pos}(p_i, t) < \text{pos}(p_j, t)\} $$

where $\text{pos}(p, t)$ is the position of the point $p$ in sequence $t$.

The index structure is implemented as a dictionary, where each point or pair of points is mapped to the set of corresponding sequences.

## 4.2 Index-based similarity search

We first retrieve the $\bar{p}_i$ sequences for each point in the query $q$. Since the $S$ threshold indicates that the user expects to obtain sequences that share at least $cs = \lceil|q| \times S\rceil$ points with $q$, we generate all the sub-sequences of $q$ of size $cs$. For each sub-sequence, we obtain candidate results by computing the intersection of the sets $\bar{p}_i$ corresponding to the points in that sub-sequence. Finally, we verify whether the points in the sub-sequence appear in the right order in the candidate sequence, otherwise the candidate is filtered out.

We provide a detailed explanation of Algorithm 3 which retrieves similar sequences. The algorithm takes as input a query $q$, a similarity threshold $S$, the created index $I_1$, and the point matching function match.
<caption>**Algorithm 3 Find similar sequences**</caption>

**Require:** $q$: query sequence, $S$: threshold, $I_1$: single point index, $match$: point matching function

1: **function** SIMILAR_SEQUENCES($q, S, I_1, match$)
2:     result ← $\emptyset$, cs ← $\lceil|q| \times S\rceil$
3:     $C_{|q|,cs}$ ← the set of $C_{cs}^{|q|}$ combinations of size cs in q
4:     **for** combi ∈ $C_{|q|,cs}$ **do**
5:         candidates ← $\bigcap_{p_i \in combi} \bar{p}_i$ // use of $I_1$ index
6:         **for** c ∈ candidates **do**
7:             **if** c ∉ result and same_order(c, combi, match) **then**
8:                 result ← result ∪ {c}
9:             **end if**
10:         **end for**
11:     **end for**
12:     **return** result
13: **end function**

On line 2, the minimum number of points, $cs$, is computed from the user's threshold $S$. On line 3, we generate the set of $C_{cs}^{|q|}$ combinations of size $cs$ from the query sequence $q$. For each combination, denoted as *combi*, we compute the set of candidate sequences that contain all the points in *combi* by intersecting the sets $\bar{p}_i$ for which $p_i \in combi$. Finally on lines 7-9, we verify that the order of the points in each candidate sequence matches the order in *combi* (as detailed in Algorithm 4).

Algorithm 4 takes as input a candidate sequence *c*, a combination *combi*, and a point matching function (with point equality by default). The algorithm iterates over the points in *c* and *combi*, comparing them consecutively: if the points at the current positions *i* in *c* and *j* in *combi* are equal, the match count is incremented, and the algorithm proceeds to compare the points at positions *i* + 1 and *j* + 1. Otherwise, *i.e.* if the points do not match, the next point of the candidate sequence (at position *i* + 1) is compared with the current point of *combi* (at position *j*). After going through all the points in *combi*, the algorithm returns *True* if all the points of *combi* were matched, *i.e.* if the number of matches *m* equals the size of *combi*.

To ensure reproducibility, the code implementing our solution is available at<fnref n="1" />

## 4.3 Indexing sequences by pairs of points

To enhance the performance (*i.e.* reduce the response time) of similar sequence retrieval, we extend the above indexing method to access sequences containing not just a single point, but pairs of points. Since a point pair index (2P index, see Definition 2) is more selective than a single point index (1P index), we expect to get a performance benefit at the price of a larger index that is longer to build. However, the index creation

<footnote n="1">¹ https://gitlab.lip6.fr/jarrad/tisis</footnote>
**Algorithm 4** Check identical points order

**Require:** c: candidate sequence, combi: sub-sequence, match: point matching function

1: **function** SAME_ORDER(c, combi, match)

2: $i \leftarrow 0, \quad j \leftarrow 0, \quad m \leftarrow 0$

3: **while** $i < |c|$ **and** $j < |combi|$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp;**if** match(c[i], combi[j]) **then**

5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;increment j, increment m

6: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

7: &nbsp;&nbsp;&nbsp;&nbsp;increment i

8: &nbsp;&nbsp;&nbsp;&nbsp;**end while**

9: &nbsp;&nbsp;&nbsp;&nbsp;**return** $(m = |combi|)$

10: **end function**

time is amortized along the index usage period, thus this solution is considered benefi-
cial as long as it improves sequence retrieval time. Information on the 1P and 2P index
sizes, construction times, and memory usage can be found in Section 6.4, specifically
in Table 5.

Assuming a 2P index, we can access the set $\overline{p_i p_j}$ of sequences that pass through $p_i$
followed by $p_j$ (i.e. $p_i$ precedes $p_j$). We adapt Algorithm 3 to access sequences by the
point pair index. Specifically, on line 5, the index is probed for every pair of consecutive
points in *combi*. Algorithm 5 is an adaptation of Algorithm 3.

**Algorithm 5** Find similar sequences using 2P index

**Require:** q: query sequence, S: threshold, I₂: Pair of points index

1: **function** SIMILAR_SEQUENCES_2P(q, S, I₂)

2: $result \leftarrow \emptyset, \quad cs \leftarrow [q] \times S$

3: $C_{|q|,cs} \leftarrow$ the set of $C_{cs}^{|q|}$ combinations of size cs in q

4: **for** combi ∈ $C_{|q|,cs}$ **do**

5: &nbsp;&nbsp;&nbsp;&nbsp;candidates $\leftarrow \bigcap_{p_i, p_j \in combi, \text{pos}(p_j, combi) = \text{pos}(p_i, combi) + 1} \overline{p_i p_j}$ // use of I₂ index

6: $result \leftarrow result \cup candidates$

7: **end for**

8: **return** result

9: **end function**

**4.4 Theoretical costs**

In this section, we analyze the estimated theoretical cost of two approaches :

- SISIS, which refers to the execution of Algorithm 3, and whose cost depends on five key parameters: the query size $|q|$, the combination size $cs$, the average intersection computation time $iat$, the average filtering time $fat$, and the average size of candidate sequences as
- The baseline, which refers to the call to Algorithm 2, and whose estimated cost is determined by the following parameters: the average size of sequences in the dataset $t_{as}$, the average time to compute similarity between 2 points $a_t$, and $m$ the total number of sequences to be compared with the query $q$.

All the mentioned parameters that are used in this analysis are shown in Table 3.

<table><caption>Table 3: Notations used for theoretical cost formulas</caption><thead><tr><td>Notation</td><td>Description</td></tr></thead><tbody><tr><td>|q|</td><td>Query size</td></tr><tr><td>cs</td><td>Combination size</td></tr><tr><td>iat</td><td>Intersection average computation time</td></tr><tr><td>fat</td><td>Filtering average computation time</td></tr><tr><td>as</td><td>Average size of candidate sequences</td></tr><tr><td>t<sub>as</sub></td><td>Average size of sequences in the dataset</td></tr><tr><td>a<sub>t</sub></td><td>Average time to compute similarity between 2 points</td></tr><tr><td>n</td><td>Total number of sequences to be compared with q</td></tr></tbody></table>

**Theoretical costs of an index-based similarity search** The proposed index-based approach follows these steps:

1. **Sequence similarity search:** This part consists of the following sub-steps:

(a) **Generating point combinations:** We generate the set of $C_{cs}^{|q|}$ combinations of size $cs$ from the query sequence $q$. (line 3 of Algorithm 3). The cost of generating combinations is negligible.

(b) **Index access:** For each combination $combi$, we retrieve the sets $\bar{p}_i$ for all $p_i \in combi$ (lines 4–5 of Algorithm 3). Each retrieval is done in constant time, thanks to the pre-constructed index. Since each combination has $cs$ elements and there are $C_{cs}^{|q|}$ such combinations, this results in a cost $AC = cs \cdot C_{cs}^{|q|} \cdot \text{probe}$ for index accesses, where probe is the constant index access time.

(c) **Computing intersections:** For each combination, denoted as $combi$ containing $cs$ elements, we compute the set of candidate sequences that contain all the points of $combi$, by intersecting the sets $\bar{p}_i$ for which $p_i \in combi$, retrieved in the previous sub-step (line 4-5 of Algorithm 3). In total, we calculate $cs - 1$ intersections. The cost of an intersection between two sets of size $s1$ and $s2$ is $O(s1 * s2)$. However, in our case we can't estimate the exact sizes of $\bar{p}_i$. We choose to measure the run time of intersections and use the average cost $iat$ as an approximation of the intersection cost.

The cost of computing intersections is therefore: $iat \times (cs - 1)$.

The total cost of the sequence similarity search is:

$$SC = (cs - 1) * C_{cs}^{|q|} * iat$$
2. **Sequence filtering:** The final step involves filtering sequences, as described in lines 7-9 of Algorithm 3 (for more details, see Algorithm 4). Given a set of candidate sequences *candidates*, we check whether the order of points in each sequence matches the order in *combi*. The size of *candidates* varies depending on the combination, so we compute the average size (*as*). For each sequence in *candidates*, we measure the filter time (*ft*). We then calculate the average(*fat*) from all the calculated durations. Thus, the filtering cost would be:

$$FC = fat * as * C_{cs}^{|q|}$$

As a result, the estimated total cost of SISIS is:

$$ 
\begin{aligned}
TC(SISIS) &= AC + SC + FC \\
&= (cs * C_{cs}^{|q|} * probe) + ((cs - 1) * C_{cs}^{|q|} * iat) + (fat * as * C_{cs}^{|q|}) \\
&= C_{cs}^{|q|} * ((cs * probe) + ((cs - 1) * iat) + (fat * as))
\end{aligned}
\quad (1) $$

When $C_{cs}^{|q|}$ is maximized, i.e. $cs = |q|/2$, we have $C_{cs}^{|q|} \approx \frac{2^{|q|}}{\sqrt{|q|}}$. Then, the SISIS cost is $O(2^{|q|})$ according to Equation (1).

**Theoretical costs of the baseline** We also analyze the estimated theoretical cost of the LCSS-based baseline. When a user gives a query *q* as input, and wants to retrieve similar sequences, the baseline compares the similarity between *q* and all other sequences in the dataset, and then keeps the similar ones within a certain threshold set by the user.

The baseline first compares the query *q* of size *|q|* with a sequence *t* of average size *t*<sub>as</sub>. Since all points in both sequences are compared, the computational cost of this operation is *|q|* × *t*<sub>as</sub> × *a*<sub>t</sub>, where *a*<sub>t</sub> represents the average time required to compute the similarity between two points. This operation is performed *n* times, where *n* denotes *|T|* i.e. the total number of sequences to be compared with *q* in the dataset. Consequently, the estimated total cost is given by:

$$TC(Baseline) = |q| * t_{as} * a_{t} * n \quad (2)$$

According to Equation (2), the LCSS-based baseline has a theoretical cost of $O(|q|)$ for a fixed dataset, meaning that the cost increases linearly with the query size. This assumes that the number of sequences to be compared (*n*) and the average sequence size (*t*<sub>as</sub>) remain constant.

While this linear complexity appears favorable in theory, experimental results (see Section 6.4) show that SISIS can be more efficient for moderate query sizes, typically when *|q|* is less than 17 or 18, which is the case for all mobility based applications. This conclusion is supported by applying the cost models from Equation (1) and Equation (2), using the parameter values listed in Table 3, derived from empirical measurements.
# 5 Sequence indexing based on point embeddings

As discussed in Section 1, both the LCSS-based baseline and SISIS are effective in finding similar sequences, but they rely on exact point matching. In some cases, this constraint can be too restrictive, leading to a small or even empty result set, particularly for large queries.

To relax this constraint, and assuming that the only available contextual information about points is the sequences that contain them, we propose a method based on point embeddings generated using Word2Vec (W2V) [17]. The principle of W2V is that words that appear in similar contexts tend to have similar vector representations. The model learns this by predicting surrounding words of a target word (or the reverse), leading to similar vectors for words that are used in similar ways.

In our scenario, we can think of the words as being the points and the sentences as being the sequences containing these points. We argue that two sequences are similar not only when their points match, but also when their points have similar embeddings.

Based on this approach, we introduce SISIS*, an extension of SISIS that leverages embeddings. This variant takes into account a relaxation threshold specified by the user, and compares sequences by exploiting contextual similarity. This method provides more results than SISIS. Those additional sequences do not necessarily pass through the query points but through points that are close to them in the embeddings space, i.e. they are contextually close.

## 5.1 Contextual similarity and sequence index

Let $p_i$ and $p_j$ two points, and $e'_i$ and $e'_j$ their respective embedding obtained by W2V [17].

**Definition 3 (Point $\epsilon$-similarity).** We say that $p_i$ and $p_j$ are $\epsilon$-similar if the cosine between $e_i$ and $e_j$ is above a similarity threshold $\epsilon \in [0, 1]$ given by the user. We define $sim_{\epsilon}$ as :

$$sim_{\epsilon}(p_i, p_j) \equiv \cosine(e_i, e_j) \geq \epsilon$$

Specifically for $\epsilon = 1$, $p_i$ and $p_j$ are the same point, and thus they are similar.

The similarity between two sequences is defined in Section 2.1, but considering a contextual version of LCSS, denoted LCSS($q, t, sim_{\epsilon}$), where two points match if they are $\epsilon$-similar. We now generalize the definition of the index.

**Definition 4 (Contextual sequence index).** The contextual sequence index CSI: $p_i \mapsto \bar{p}_i$ associates each point $p_i$ with the set $\bar{p}_i$ of sequences that pass through a point $p_j$ $\epsilon$-similar to $p_i$ and defined by :

$$\bar{p}_i = \{t \in T | \exists p_j \in t, \text{ s.t. } sim_{\epsilon}(p_i, p_j)\}$$

## 5.2 Sequence search based on point embeddings

This section details the method we designed to integrate point embeddings in sequence search.
We trained W2V using all the sequences as input and obtained as output vector representations for each point, called point embeddings. These embeddings are used to create the contextual sequence index $\bar{p}_i$ and to identify similar sequences as outlined in Algorithm 3. The adaptation made is in Algorithm 6, provided that line 5 becomes

$$ \text{candidates} \leftarrow \bigcap_{i \in \text{combi}} \bar{p}_i $$

**Algorithm 6 Find similar sequences**

**Require:** $q$: query sequence, $S$: threshold, $sim_e$: point matching function, $CSI$: contextual sequence index

1: **function** SIMILAR_SEQUENCES($q$, $S$, $CSI$, $sim_e$)

2: result $\leftarrow \emptyset$, $cs \leftarrow [|q| \times S]$

3: $C_{|q|,cs}$ ← the set of $C_{cs}^{|q|}$ combinations of size $cs$ in $q$

4: **for** combi $\in C_{|q|,cs}$ **do**

5: candidates $\leftarrow \bigcap_{i \in \text{combi}} \bar{p}_i$ // use of CSI

6: **for** $c \in$ candidates **do**

7: **if** $c \notin$ result and same_order($c$, combi, $sim_e$) **then**

8: result $\leftarrow$ result $\cup$ $\{c\}$

9: **end if**

10: **end for**

11: **end for**

12: **return** result

13: **end function**

The step to create combinations of $cs$ points (line 3 of Algorithm 3) remains the same. On line 7, the point order check takes into account $\epsilon$-similarity point matching by invoking same_order with $sim_e$ as the point matching function. It is important to note that the size of $\bar{p}_i$ set introduced in Definition 4 depends on the selected $\epsilon$ similarity threshold. The lower the threshold, the more similar sequences will be retrieved. Our experiments will investigate the impact of $\epsilon$ on the result size, specifically the number of additional sequences.

## 6 Experimental validation

This section reports on the experimental evaluation of our method and its comparison with the baseline. We start by describing the datasets used and outlining the experimental methodology for both exact sequence indexing and indexing based on point embeddings. Subsequently, we analyze and discuss the results obtained. All experiments were conducted on a Dell PowerEdge R440 server running Linux, equipped with 370 GB of RAM, and the implementation was carried out in Python. The index structure
was implemented using a dictionary that maps each point (or pair of points) to a set of
sequences.

For the embedding-based solution, we additionally rely on the multidimensional
index provided by the W2V model, which retrieves points similar to a given point in a
10-dimensional vector space.

**6.1 Data preparation**

We conduct our experiments on three datasets: Foursquare[28] and Gowalla[8] on New York city, and YFCC[24] on France. The aim is to demonstrate the effectiveness of our method across different datasets. Foursquare and Gowalla come with predefined points. YFCC is a larger dataset that contains geo-located check-ins but no POI information. To infer POIs from geolocations, we applied a grid-based partitioning of the space: each 100 square meter cell that contains some check-ins is considered as a POI, as proposed in [14].

In this study, we only consider points that have been visited more than 15 times. Points with low visit frequencies are excluded because they appear too rarely in the dataset. Consequently, sequences containing such rare points often lack sufficiently similar counterparts, preventing meaningful similarity comparisons. Our goal is to build sequences from frequently visited points in order to identify relevant neighbors that share common subsequences.

After selecting the points, we construct user sequences on a daily basis (from 0:00 am to 11:59 pm). Then, we keep only sequences with a realistic size, i.e. in [3,20]. More specifically, a sequence of two points is too short, However, our approach can be generalized since each point requires at least two neighboring points (before and after) to provide context. Therefore, we retain only sequences of length three or more. Sequences longer than 20 points are considered outliers that may introduce noise into the dataset and are thus excluded. Thus, we have 10,071 sequences with Foursquare, 23,145 sequences with YFCC, and 5,129 sequences with Gowalla.

We analyse the distribution of sequences sizes for the three datasets in Figure 2, 3, and 4. The average sequence size is 5 for Foursquare, 6 for Gowalla, and 5 for YFCC. While our experiments are conducted on mobility datasets, the proposed method is applicable to other sequential data with moderate-length sequences.

<figure><img src="image_4.png" /><figcaption>Fig. 2: Foursquare</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 3: Gowalla</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Fig. 4: YFCC</figcaption></figure>

## 6.2 Exact sequence indexing: experimental methodology

For our experiments, we use the three datasets described in section 6.1, and compare our proposed solution with the LCSS-based baseline. We use the sequences in the dataset as queries. For each query, we retrieve all the similar sequences, with various similarity thresholds ranging from 0.1 to 1, as well as the time taken to compute them. We focus on the effect of query size on response time, and report the average response times for each query size.

As outlined in Section 4.2, SISIS relies on the calculation of $C_{cs}^{|q|}$ combinations of cs points from q. As the number of combinations gets larger, SISIS performs slower. Therefore, we investigate the worst-case scenario where $C_{cs}^{|q|}$ is maximized, i.e. cs = |q|/2. Accordingly, we set the threshold S to 0.5 in all the following experiments.

The experimental methodology described here applies to indexing sequences by a single point (described in Section 4.2), and also to indexing sequences by pairs of points (described in Section 4.3). We carry out this experiment on Foursquare dataset in the Section 6.4, and subsequently compare the results with those obtained with the Gowalla and YFCC datasets in Section 6.4.

## 6.3 Sequence indexing based on point embeddings: experimental methodology

In this section, we perform experiments using the Foursquare dataset and compare the results with those obtained using SISIS (exact method) on the same dataset. The aim is to demonstrate that SISIS* which is based on embeddings produces more interesting results than SISIS, thanks to the contextual similarity. We trained W2V with the following parameters: vector_size=10, epochs = 5, window=5, and left all other parameters at their default values. The user threshold is still S = 0.5 and ε is in {0.65, 0.7, 0.75, 0.8, 0.85, 0.9, 0.95, 1}.

We selected a 10-dimensional vector space for training the Word2Vec model in SIS* to strike a balance between semantic expressiveness and computational efficiency. A lower dimensional space (e.g., 10) is generally sufficient to capture basic contextual similarities between points, especially when the dataset is not extremely large or complex like ours. It also ensures that the computation of similarity and the construction of the embedding-based index remain fast.
Increasing the number of dimensions could, in principle, capture more nuanced relationships between points. However, this comes at the cost of higher memory usage, longer training time, and potentially more expensive similarity computations. Therefore, we opted for 10 dimensions as a reasonable compromise.

## 6.4 Experimental Results and Analysis

In this section, we report on the results obtained with exact indexing (using 1 and 2 points), and embedding-based indexing, following the experimental protocol described in section 6.

### SISIS exact indexing using single points

*Impact of query size on SISIS execution time.* For exact indexing with a single point, we analyse the average execution time as a function of the query size specified by the user. Since the distribution of sequence sizes in the datasets is uneven (see Section 6.1), the number of queries per size also varies. We compute average response times for each query size, but do not normalize by the number of queries, which may affect the interpretation of the results for less frequent sizes, as their average execution time may be more sensitive to outliers.

This is one of the reasons why we choose in Section 6.1) to exclude infrequent sequences from the datasets. These sequences are typically very long (over 20 points), occur less than 6 times in the Foursquare dataset.

The threshold is fixed to 0.5 to represent the worst-case scenario for SISIS. The results are illustrated in Figure 5 and 6.

<figure><img src="image_7.png" /><figcaption>Fig. 5: SISIS response time for query sizes in the range [3, 14] - Foursquare dataset</figcaption></figure>

First, we observe on Figure 5 that SISIS response time is less than 1 ms for query size smaller than 8. Thus, SISIS meets users expectation in terms of response time.

On Figure 6, we notice that our solution (SISIS in blue) is faster than LCSS-based baseline (in red) for all queries smaller than 17, above which size it becomes slower
<figure><img src="image_8.png" /><figcaption>Fig. 6: Average time as a function of query size - Foursquare dataset</figcaption></figure>

than LCSS-based baseline. However, in domains such as mobility, it is unlikely that
users would formulate queries involving a large number of points, as this would not
reflect realistic user behavior. Therefore, we can claim that SISIS largely outperforms
the LCSS-based baseline for all realistic queries. Note that we also experimented SI-
SIS and LCSS-based baseline for other threshold values (0.1 and 0.9). As expected
(see Figures 7 and 8), the results are more in favour of SISIS than for 0.5.

<figure><img src="image_9.png" /><figcaption>Fig. 7: Average time as a function of query size (threshold = 0.1)</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 8: Average time as a function of query size (threshold = 0.9)</figcaption></figure>

*Generalization to other Datasets: Gowalla and YFCC.* We performed the same experi-
ment on other datasets to show that SISIS can produce good results on any other dataset.
The chosen datasets are : Gowalla and YFCC. The Figures 9 and 10 show the results
obtained with the experiments conducted on these 2 datasets.

We observe that the results are comparable with the ones obtained for Foursquare,
which confirms that SISIS outperforms LCSS-based baseline for reasonable query sizes
and various datasets. We highlight the benefit of SISIS for queries of average sequence
size (6 and 5 for Gowalla and YFCC respectively). SISIS is 330x (resp. 2200x) faster
than LCSS-based baseline.
<figure><img src="image_11.png" /><figcaption>Fig. 9: Average time as a function of query size - Gowalla dataset</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Fig. 10: Average time as a function of query size - YFCC dataset</figcaption></figure>
*SISIS: Estimated vs. experimental cost on Foursquare Dataset.* In Section 4.4, we computed the theoretical cost of SISIS. In this section, we compare the estimated cost with the cost obtained from experimental results on Foursquare dataset. We calculate the theoretical average cost (TC) as a function of query size and plot it alongside the experimental results.

As shown in Figure 11, the estimated cost values (in green) closely match the experimental costs (in blue) obtained from experiments, with a Mean Absolute Error (MAE) of 0.14 and a Mean Squared Error (MSE) of 0.11. Since the estimated cost of SISIS closely match the experimental one, we can conclude that our implementation is correct. The theoretical estimate is an accurate reflection of reality.

<figure><img src="image_13.png" /><figcaption>Fig. 11: SISIS estimated cost vs. experimental cost - Foursquare</figcaption></figure>

*Baseline Method: Estimated vs. experimental cost on Foursquare.* We compare the theoretically estimated cost of the LCSS-based baseline with the experimental cost obtained from our experiments on Foursquare dataset. As done in Section 6.4, we set the maximum sequence size to $n = 20$. We then calculate the theoretical average cost (TC) as a function of query size and plot it alongside the experimental results.

From Figure 12, the estimated cost values (in green) closely match the experimental costs (in blue) obtained from experiments, with a Mean Absolute Error (MAE) of 0.02 and a Mean Squared Error (MSE) of 0.0004. The baseline cost estimate is in line with reality.

*Validating the Cost-Based choice between SISIS and the baseline.* The aim of this discussion is to validate the hypothesis stated in Section 4.4: by applying the theoretical formulas derived earlier, and for small to medium query sizes, SISIS outperforms the baseline in terms of cost.

By comparing the estimated costs of both the baseline and SISIS, we obtain the results illustrated in Figure 13. As expected, since the estimated costs for both the baseline and SISIS closely align with the real values observed in the experiments, the same trend emerges: SISIS remains more efficient than the baseline up to a certain query size,
<figure><img src="image_14.png" /><figcaption>Fig. 12: Baseline estimate cost vs. experimental cost - Foursquare</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>Fig. 13: Baseline estimated cost vs. SISIS estimated cost - Foursquare</figcaption></figure>
as early discussed. Figure 13 shows that for small and medium query values (up to 16), SISIS achieves lower costs compared to the baseline. For instance, when $|q| = 5$ the cost of SISIS is 0.0002s whereas the baseline costs 0.12s. Similarly, for $|q| = 16$ SISIS has a cost of 0.34s, while the baseline reaches 0.39s. However, beyond this threshold, SISIS becomes less efficient: for $|q| = 18$, its cost increases to 1.32s, compared to 0.44s for the baseline, and for $|q| = 20$, SISIS reaches 5.16s, whereas the baseline remains at 0.49s.

One practical advantage of the cost formulas proposed in Section 4.4 is their ability to guide the choice between SISIS and the baseline when searching for sequences similar to a given query *q*. The only requirement is to calibrate the cost formula parameters during the computation of the experiments on the target dataset. As an illustration, we provide the parameter values for the foursquare dataset in Table 4.

<table><caption>Table 4: Notations used for theoretical cost formulas, and their values</caption><thead><tr><th>Notation</th><th>Description</th><th>Value</th></tr></thead><tbody><tr><td>$|q|$</td><td>Query size</td><td>Varies according to input query size</td></tr><tr><td>$cs$</td><td>Combination size</td><td>$|q|/2$</td></tr><tr><td>$iat$</td><td>Intersection average computation time</td><td>$6.6e-07$</td></tr><tr><td>$fat$</td><td>Filtering average computation time</td><td>$2.58e-06$</td></tr><tr><td>$as$</td><td>Average size of candidate sequences</td><td>8.56</td></tr><tr><td>$C$</td><td>$t_{as} * a_t * m$</td><td>0.024</td></tr></tbody></table>

By applying the formulas with the values mentioned, we obtain the same results as those reported in the previous experiment.

## SISIS exact indexing using point pairs

We compare the performance of the single point index (1P) and of the point-pair index (2P) using the Foursquare dataset. As shown in Figure 14, the point-pair index (represented by the green curve) performs faster than the single point index (represented by the blue curve). On Figure 15, the performance benefit ranges from 5x to 8x (with an average benefit of 6x) for queries of size 3 to 12.

<table><caption>Table 5: Index construction cost</caption><thead><tr><th></th><th>Index with 1P</th><th>Index with 2P</th></tr></thead><tbody><tr><td>#entries</td><td>2,900</td><td>40,900</td></tr><tr><td>Avg #sequences</td><td>15 ± 20.24</td><td>3 ± 4.74</td></tr><tr><td>Build time (ms)</td><td>12</td><td>120</td></tr><tr><td>Memory size (Mo)</td><td>3.61</td><td>17.32</td></tr></tbody></table>
<figure><img src="image_16.png" /><figcaption>Fig. 14: 1 Point index vs. 2 Points index - Foursquare</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>Fig. 15: Response time 1P/2P - Foursquare</figcaption></figure>
As a counter part, the index creation time increases from 12ms to 120ms as reported in Table 5. Indeed, the 2P index contains 40,900 entries, compared to only 2,900 in the 1P index, making it approximately 14 times larger.

This moderate increase in the number of entries is due to the construction strategy used. For the 1P index, we extract all distinct points from the dataset sequences, resulting in 2,900 unique entries. In contrast, the 2P index is built by considering all possible pairs of these points. While this could theoretically lead to a quadratic number of combinations (i.e., in the millions), in practice, we retain only the pairs that actually occur together in at least one sequence in the dataset. This filtering significantly reduces the total number of entries, resulting in a manageable size of 40,900 entries, which remains tractable in real-world scenarios.

As anticipated, the 2P index demonstrates a high level of selectivity due to its reliance on pairs of points for indexing. It significantly narrows down the candidate set during the retrieval process. In our experiments on the Foursquare dataset, this selectivity results in an average of only 3 sequences retrieved out of 10,000, highlighting the index's ability to effectively filter out non-relevant sequences.

SISIS currently supports indexing either single point (1P) or ordered pairs of points (2P). The choice of stopping at pairs, rather than considering more selective units such as points triples, is primarily motivated by the trade-off between selectivity and efficiency. While increasing the size of the index points could improve selectivity and potentially reduce the number of candidate sequences retrieved, it would come at the cost of a substantial increase in index size (# entries) and construction time.

Additionally, our experiments show that the 2P index already offers a good balance between selectivity and efficiency: it provides significantly better filtering than 1P, while keeping the index size and construction cost manageable (as shown in Table 5). As such, we opted not to extend the SISIS index to higher-order combination of points like triplets, in order to preserve its scalability.

## embedding-based Indexing: Impact of similarity threshold and cost evaluation

In the context of $\epsilon$-similarity search, we analyze how varying the relaxation threshold $\epsilon$ affects the number of sequences retrieved, using the Foursquare dataset. Recall that SISIS* extends the standard SISIS method, by integrating points embeddings to capture contextual similarity between sequences. This embedding-based approach allows the retrieval of a broader set of sequences, including those that do not strictly match the query points but that contain semantically related ones.

On Figure 16, we vary the value of the similarity threshold $\epsilon$ on the x-axis. The y-axis is the average percentage of extra sequences retrieved by the queries. For example, for $\epsilon = 0.72$, we retrieve twice as many sequences as SISIS. This increase is due to the fact that the number of neighbors increases with $\epsilon$. We illustrate this on Figure 17. Specifically, we obtained 14 neighbors for $\epsilon = 0.72$ and only 1 neighbor for $\epsilon \ge 0.9$.

Moreover, the cost remains close to that of the standard SISIS algorithm: less than 0.2s for $\epsilon > 0.72$ (see Figure 18), demonstrating the efficiency of our approach. For $\epsilon < 0.72$ the cost actually increases significantly (up to 1.35s for $\epsilon = 0.65$), but such a range of $\epsilon$ values would rarely be used in practice because it returns too many sequences (more than twice as many as with the standard SISIS method).
<figure><img src="image_18.png" /><figcaption>Fig. 16: Effect of $\epsilon$ on the average percentage of additional sequences - Foursquare</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>Fig. 17: Average number of neighbors per similarity threshold - Foursquare</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>Fig. 18: average cost per similarity threshold - Foursquare</figcaption></figure>
Another aspect that our experiments aimed to investigate concerns the relevance of embeddings. To this end, we reduced the embeddings dimension to 2 (instead of the previous dimension value of 10), so that we can plot them on Figure 19. We observed that they are rather uniformly dispersed.

Several recent works have demonstrated the efficacy of using embeddings to repre-
sent mobility sequences or points for various tasks, such as location classification and
next location prediction. Notable examples include [14,15,3,26].

One way to assess the relevance of the embeddings is to verify that they are well
dispersed on the vector plan, which is illustrated in (Figure 19).

Another approach to assess the relevance of embeddings is to show that the number of neighbours for any point is increasing gradually with the similarity threshold. This is the case on Figure 20 where we plot the number of neighbours per point according to the threshold (boxplots in this figure highlight the percentiles 5,25,50,75,95 of the number of neighbours).

<figure><img src="image_21.png" /><figcaption>Fig. 19: 500 points sample (in 2D plan)</figcaption></figure>

Finally, it should be noted that in our embedding-based indexing experiments, we
focus exclusively on the 1P index and do not include the 2P index. The 2P index, which
involves sequence associations for all possible point pairs (pᵢ, pⱼ) and the identifica-
tion of ϵ-similar pairs (pₖ, pₗ), results in a significantly higher number of entries and
a substantially greater index construction cost. Specifically, the number of entries in-
creases from 1,754 in the 1P index to 8,645 in the 2P index (almost 5x larger), and the
construction time rises from 240s to 2,220s (almost 10x slower), as shown in Table 6.

The significant increase in index construction time, as shown in Table 6 compared
to the values reported in Table 5 is explained by the use of point embeddings. In this
setting, the index is built not only from the exact points in the dataset, but also from all
points that are considered similar in the embedding space.
<figure><img src="image_22.png" /><figcaption>Fig. 20: #Neighbours per point</figcaption></figure>

<table><caption>Table 6: Embeddings indexes construction cost</caption><thead><tr><th></th><th>Index with 1P</th><th>Index with 2P</th></tr></thead><tbody><tr><td>#entries</td><td>1,754</td><td>8,645</td></tr><tr><td>Build time (s)</td><td>240</td><td>2,220</td></tr></tbody></table>

For the 1P embedding-based index, we retrieve sequences containing not only a given point, but also those that contain any point deemed similar to it. This results in a broader search and more sequences to process during index construction.

The 2P embedding-based index further increases this complexity. For each point pair, we retrieve not only the sequences containing the exact pair but also those matching any combination involving similar points, whether the first point, the second point, or both are replaced by similar ones. This leads to a combinatorial increase in the number of candidate sequences to process, which significantly increases the construction time compared to the exact indexing.

# 7 Conclusion

This study demonstrates the effectiveness of an indexing-based approach for sequence similarity search when compared to a baseline method that relies on the Longest Common Subsequence (LCSS) algorithm. To address the performance limitations inherent in LCSS-based search, we introduce *SISIS* (Sequence Indexing for Similarity Search). SISIS employs an exact indexing approach for sequence similarity search. By leveraging two distinct sequence indexing techniques, our approach consistently produces results identical to the LCSS-based baseline, while offering significantly improved performance for queries of a reasonable size.

Nevertheless, SISIS may be overly restrictive, as it relies on exact matching of points, which can result in too few (or even no) returned results. To mitigate this limitation, we have developed and implemented *SISIS*\*, a relaxed variant of SISIS. This
extension enables more comprehensive retrieval of similar sequences by accounting for semantic similarities between points, rather than relying solely on exact matches. The relaxed method yields a significantly higher number of results (approximately twice as many as the exact method with a similarity threshold of 0.72) while preserving computational efficiency.

We conducted experiments on three real-world datasets, demonstrating that the proposed approach significantly outperforms the baseline up to a query size of 17 on the Foursquare dataset. However, as the query size increases beyond this threshold, its computational cost exceeds that of the LCSS-based baseline, showing that SISIS is not suitable for very large queries.

Currently, SISIS is limited to optimising only the LCSS-based similarity measure, as it retrieves sequences based on exact point matches and sequential order. This definition does not directly apply to other similarity measures that rely on different assumptions.

For instance, DTW (Dynamic Time Warping) is designed to compare continuous time series by aligning them through temporal warping. It measures similarity by computing the minimum cumulative Euclidean distance between points in the two sequences, even if they are not aligned in time. This flexibility allows DTW to handle shifts and stretching in the temporal dimension, which SISIS is not designed to support.

Likewise, ERP (Edit distance with Real Penalty) is based on the concept of edit distance. It computes the cost of transforming one sequence into another using insertions, deletions, and substitutions, where substitution costs are calculated via the Euclidean distance between points. Unlike LCSS, which focuses on counting matching points, ERP considers the accumulated numerical dissimilarity between sequences.

Because SISIS relies entirely on LCSS and its discrete matching strategy, it cannot currently support similarity measures such as DTW or ERP. Extending SISIS into a more general framework that accommodates different types of similarity metrics remains an open and promising direction for future work.

Another avenue we could explore is extending our approach to domains beyond mobility trajectories, thereby showcasing its applicability to a broader spectrum of sequential data. While the proposed method is structurally generic, its deployment in other contexts entails specific challenges. For instance, in the case of textual data, we may face a dramatic growth in index size due to the vast number of distinct words. Similarly, when applied to biological DNA sequences, differences in sequence length relative to mobility data may impact the overall effectiveness of the approach. Addressing such challenges will thus necessitate dedicated algorithmic adaptations

## References

1. Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: Basic local alignment search tool. Journal of Molecular Biology **215**(3), 403–410 (1990). https://doi.org/https://doi.org/10.1016/S0022-2836(05)80360-2, https://www.sciencedirect.com/science/article/pii/S0022283605803602

2. Berndt, D.J., Clifford, J.: Using dynamic time warping to find patterns in time series. In: Fayyad, U.M., Uthurusamy, R. (eds.) Knowledge Discovery in Databases: Papers from the 1994 AAAI Workshop, Seattle, Washington, USA, July 1994. Technical Report
WS-94-03. pp. 359-370. AAAI Press (1994), https://dblp.org/rec/conf/kdd/BerndtC94.bib

3. Biester, L., Banea, C., Mihalcea, R.: Building location embeddings from physical trajectories and textual representations. In: Wong, K., Knight, K., Wu, H. (eds.) Proceedings of the 1st Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 10th International Joint Conference on Natural Language Processing, AACL/IJCNLP 2020, Suzhou, China, December 4-7, 2020. pp. 425-434. Association for Computational Linguistics (2020). https://doi.org/10.18653/v1/2020.AACL-MAIN.44, https://doi.org/10.18653/v1/2020.aacl-main.44

4. Bringmann, K., Cohen-Addad, V., Das, D.: A linear-time $n^{0.4}$-approximation for longest common subsequence. ACM Trans. Algorithms 19(1), 9:1-9:24 (2023). https://doi.org/10.1145/3568398, https://doi.org/10.1145/3568398

5. Chan, W., Zhang, Y., Fung, S.P.Y., Ye, D., Zhu, H.: Efficient algorithms for finding a longest common increasing subsequence. J. Comb. Optim. 13(3), 277-288 (2007). https://doi.org/10.1007/S10878-006-9031-7, https://doi.org/10.1007/s10878-006-9031-7

6. Chen, L., Ng, R.T.: On the marriage of lp-norms and edit distance. In: Nascimento, M.A., Özsu, M.T., Kossmann, D., Miller, R.J., Blakeley, J.A., Schiefer, K.B. (eds.) (e)Proceedings of the Thirtieth International Conference on Very Large Data Bases, VLDB 2004, Toronto, Canada, August 31 - September 3 2004. pp. 792-803. Morgan Kaufmann (2004). https://doi.org/10.1016/B978-012088469-8.50070-X, http://www.vldb.org/conf/2004/RS21P2.PDF

7. Chen, L., Özsu, M.T., Oria, V.: Robust and fast similarity search for moving object trajectories. In: Özcan, F. (ed.) Proceedings of the ACM SIGMOD International Conference on Management of Data, Baltimore, Maryland, USA, June 14-16, 2005. pp. 491-502. ACM (2005). https://doi.org/10.1145/1066157.1066213, https://doi.org/10.1145/1066157.1066213

8. Cho, E., Myers, S.A., Leskovec, J.: Friendship and mobility: user movement in location-based social networks. In: Apté, C., Ghosh, J., Smyth, P. (eds.) Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA, USA, August 21-24, 2011. pp. 1082-1090. ACM (2011). https://doi.org/10.1145/2020408.2020579, https://doi.org/10.1145/2020408.2020579

9. Gotoh, O.: An improved algorithm for matching biological sequences. Journal of Molecular Biology 162(3), 705-708 (1982). https://doi.org/10.1016/0022-2836(82)90398-9, https://www.sciencedirect.com/science/article/pii/0022283682903989

10. Hajiaghayi, M., Seddighin, M., Seddighin, S., Sun, X.: Approximating LCS in linear time: Beating the $\sqrt{n}$ barrier. CoRR abs/2003.07285 (2020), https://arxiv.org/abs/2003.07285

11. Han, T.S., Ko, S., Kang, J.: Efficient subsequence matching using the longest common subsequence with a dual match index. In: Perner, P. (ed.) Machine Learning and Data Mining in Pattern Recognition, 5th International Conference, MLDM 2007, Leipzig, Germany, July 18-20, 2007, Proceedings. Lecture Notes in Computer Science, vol. 4571, pp. 585-600. Springer (2007). https://doi.org/10.1007/978-3-540-73499-4_44, https://doi.org/10.1007/978-3-540-73499-4_44

12. Hirschberg, D.S.: A linear space algorithm for computing maximal common subsequences. Commun. ACM 18(6), 341-343 (1975). https://doi.org/10.1145/360825.360861, https://doi.org/10.1145/360825.360861
13. Hirschberg, D.S.: Algorithms for the longest common subsequence problem. J. ACM 24(4), 664-675 (1977). https://doi.org/10.1145/322033.322044, https://doi.org/10.1145/322033.322044

14. Jarrad, S., Naacke, H., Gançarski, S., Gueye, M.: Embedding-enhanced similarity metrics for next POI recommendation. In: Gusikhin, O., Hammoudi, S., Cuzzocrea, A. (eds.) Proceedings of the 12th International Conference on Data Science, Technology and Applications, DATA 2023, Rome, Italy, July 11-13, 2023. pp. 247-254. SCITEPRESS (2023). https://doi.org/10.5220/0012060300003541, https://doi.org/10.5220/0012060300003541

15. Lin, Y., Wan, H., Guo, S., Lin, Y.: Pre-training context and time aware location embeddings from spatial-temporal trajectories for user next location prediction pp. 4241-4248 (2021). https://doi.org/10.1609/AAAI.V35I5.16548, https://doi.org/10.1609/aaai.v35i5.16548

16. Magdy, N., Sakr, M.A., Mostafa, T., El-Bahnasy, K.: Review on trajectory similarity measures. In: 2015 IEEE Seventh International Conference on Intelligent Computing and Information Systems (ICICIS). pp. 613-619 (2015). https://doi.org/10.1109/IntelCIS.2015.7397286

17. Mikolov, T., Chen, K., Corrado, G., Dean, J.: Efficient estimation of word representations in vector space. In: Bengio, Y., LeCun, Y. (eds.) 1st International Conference on Learning Representations, ICLR 2013, Scottsdale, Arizona, USA, May 2-4, 2013, Workshop Track Proceedings (2013), http://arxiv.org/abs/1301.3781

18. Needleman, S.B., Wunsch, C.D.: A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology 48(3), 443-453 (1970). https://doi.org/10.1016/0022-2836(70)90057-4, https://www.sciencedirect.com/science/article/pii/S002283670900574

19. Notredame, C., Higgins, D.G., Heringa, J.: T-coffee: a novel method for fast and accurate multiple sequence alignment edited by j. thornton. Journal of Molecular Biology 302(1), 205-217 (2000). https://doi.org/10.1006/jmbi.2000.4042, https://www.sciencedirect.com/science/article/pii/S0022283600940427

20. Sellers, P.H.: An algorithm for the distance between two finite sequences. J. Comb. Theory A 16(2), 253-258 (1974). https://doi.org/10.1016/0097-3165(74)90050-8, https://doi.org/10.1016/0097-3165(74)90050-8

21. Smith, T., Waterman, M.: Identification of common molecular subsequences. Journal of Molecular Biology 147(1), 195-197 (1981). https://doi.org/10.1016/0022-2836(81)90087-5, https://www.sciencedirect.com/science/article/pii/S0022283681900875

22. Smith, T., Waterman, M.: Identification of common molecular subsequences. Journal of Molecular Biology 147(1), 195-197 (1981). https://doi.org/10.1016/0022-2836(81)90087-5, https://www.sciencedirect.com/science/article/pii/S0022283681900875

23. Su, H., Liu, S., Zheng, B., Zhou, X., Zheng, K.: A survey of trajectory distance measures and performance evaluation. VLDB J. 29(1), 3-32 (2020). https://doi.org/10.1007/S00778-019-00574-9, https://doi.org/10.1007/S00778-019-00574-9

24. Thomee, B., Shamma, D.A., Friedland, G., Elizalde, B., Ni, K., Poland, D., Borth, D., Li, L.: YFCC100M: the new data in multimedia research. Commun. ACM 59(2), 64-73 (2016). https://doi.org/10.1145/2812802, https://doi.org/10.1145/2812802
25. Toohey, K., Duckham, M.: Trajectory similarity measures. ACM SIGSPATIAL Special 7(1), 43–50 (2015). https://doi.org/10.1145/2782759.2782767, https://doi.org/10.1145/2782759.2782767

26. Wan, H., Lin, Y., Guo, S., Lin, Y.: Pre-training time-aware location embeddings from spatial-temporal trajectories. IEEE Trans. Knowl. Data Eng. 34(11), 5510–5523 (2022). https://doi.org/10.1109/TKDE.2021.3057875, https://doi.org/10.1109/TKDE.2021.3057875

27. Wang, H., Su, H., Zheng, K., Sadiq, S., Zhou, X.: An effectiveness study on trajectory similarity measures. In: Wang, H., Zhang, R. (eds.) Twenty-Fourth Australasian Database Conference, ADC 2013, Adelaide, Australia, February 2013. CRPIT, vol. 137, pp. 13–22. Australian Computer Society (2013)

28. Yang, D., Zhang, D., Zheng, V.W., Yu, Z.: Modeling user activity preference by leveraging user spatial temporal characteristics in lbsns. IEEE Trans. Syst. Man Cybern. Syst. 45(1), 129–142 (2015). https://doi.org/10.1109/TSMC.2014.2327053, https://doi.org/10.1109/TSMC.2014.2327053

29. Yi, B., Jagadish, H.V., Faloutsos, C.: Efficient retrieval of similar time sequences under time warping pp. 201–208 (1998). https://doi.org/10.1109/ICDE.1998.655778, https://doi.org/10.1109/ICDE.1998.655778