Compute trajectory similarity using ST_lcsSimilarity - ApsaraDB RDS

Computes the similarity between two trajectory objects using the Longest Common Subsequence (LCSS) algorithm. Returns the count of consistent trajectory points.

Syntax

integer ST_lcsSimilarity(trajectory traj1, trajectory traj2, float8 dist, distanceUnit unit default 'M');
integer ST_lcsSimilarity(trajectory traj1, trajectory traj2, float8 dist, interval lag, distanceUnit unit default 'M');

Two overloads are available: one without a time tolerance (lag) and one with it.

Parameters

Parameter	Type	Description
`traj1`	`trajectory`	The first trajectory object.
`traj2`	`trajectory`	The second trajectory object.
`dist`	`float8`	The distance tolerance between two trajectory points. Unit: meters.
`lag`	`interval`	The time tolerance between two trajectory points.
`unit`	`distanceUnit`	The unit of `dist`. Default: `'M'`. Valid values: `'M'` (meters), `'KM'` (kilometers), `'D'` (degrees).

The 'D' value for unit is only valid when the Spatial Reference System Identifier (SRID) of the trajectory object is WGS 84 (EPSG code 4326). The default SRID is 4326 if not specified.

Algorithm

The LCSS algorithm finds the maximum similarity between two trajectory objects by identifying trajectory points that are consistent in both space and time. Two points are considered consistent when the spatial distance between them is within dist and, if lag is specified, the time difference is within lag.

The function returns the count of consistent trajectory points, not a normalized similarity score.

In the figure above, trajectory points 1, 3, and 6 meet the consistency conditions, so the function returns 3.

Examples

Example 1: Distance tolerance only

This example uses a distance tolerance of 100 meters without a time constraint.

With traj AS (
    Select ST_makeTrajectory('STPOINT', 'LINESTRINGZ(114.000528 33.588163 54.87, 114.000535 33.588235 54.85, 114.000447 33.588272 54.69, 114.000348 33.588287 54.73, 114.000245 33.588305 55.26, 114.000153 33.588305 55.3)'::geometry,
                             ARRAY['2010-01-01 11:30'::timestamp, '2010-01-01 11:31', '2010-01-01 11:32', '2010-01-01 11:33','2010-01-01 11:34','2010-01-01 11:35'], NULL) a,
           ST_makeTrajectory('STPOINT', 'LINESTRINGZ(114.000529 33.588163 54.87, 114.000535 33.578235 54.85, 114.000447 33.578272 54.69, 114.000348 33.578287 54.73, 114.000245 33.578305 55.26, 114.000163 33.588305 55.3)'::geometry,
                             ARRAY['2010-01-01 11:29:58'::timestamp, '2010-01-01 11:31:02', '2010-01-01 11:33', '2010-01-01 11:33:09','2010-01-01 11:34','2010-01-01 11:34:30'], NULL) b)
Select st_LCSSimilarity(a, b, 100) from traj;
-- 2

Example 2: Distance tolerance with time tolerance

This example adds a time tolerance of 30 seconds. Points within 100 meters spatially but more than 30 seconds apart are not counted as consistent.

With traj AS (
    Select ST_makeTrajectory('STPOINT', 'LINESTRINGZ(114.000528 33.588163 54.87, 114.000535 33.588235 54.85, 114.000447 33.588272 54.69, 114.000348 33.588287 54.73, 114.000245 33.588305 55.26, 114.000153 33.588305 55.3)'::geometry,
                             ARRAY['2010-01-01 11:30'::timestamp, '2010-01-01 11:31', '2010-01-01 11:32', '2010-01-01 11:33','2010-01-01 11:34','2010-01-01 11:35'], NULL) a,
           ST_makeTrajectory('STPOINT', 'LINESTRINGZ(114.000529 33.588163 54.87, 114.000535 33.578235 54.85, 114.000447 33.578272 54.69, 114.000348 33.578287 54.73, 114.000245 33.578305 55.26, 114.000163 33.588305 55.3)'::geometry,
                             ARRAY['2010-01-01 11:29:58'::timestamp, '2010-01-01 11:31:02', '2010-01-01 11:33', '2010-01-01 11:34:15','2010-01-01 11:34:50','2010-01-01 11:34:30'], NULL) b)
Select st_LCSSimilarity(a, b, 100, interval '30 seconds') from traj;
-- 2

ApsaraDB RDS:ST_lcsSimilarity