使用间隔阈值对具有可变连续时间戳的记录进行分组

Question

我有一系列带时间戳的间歇性间隔GPS坐标。我正在使用PostGIS将它们渲染到地图画布上。要渲染它们，需要使用PostGIS中的ST_MakeLine()聚合函数将点聚合为线，从而在地图上留下GPS数据缺失的空白。数据不一定按顺序从设备到达。

一个示例序列如下：

ID | Timestamp              | Location
--------------------------------------
1  | 2013-11-12 03:31:31    | (1,2)   
3  | 2013-11-12 03:31:34    | (1,3)   
7  | 2013-11-12 03:31:37    | (1,4)  
4  | 2013-11-12 03:31:43    | (1,5)   
2  | 2013-11-12 03:31:55    | (1,6)   
16 | 2013-11-12 03:33:22    | (1,7)   
22 | 2013-11-12 03:33:28    | (1,8)   
18 | 2013-11-12 03:33:32    | (1,9)   

分组的条件是：

• 如果与前一记录的差距大于30秒或
• 如果自该组中的第一个记录以来的时间<15秒。在这种情况下，该点属于两组(即，一组以该点结束，下一组开始)

PostGIS中的ST_MakeLine()函数将生成必要的行，问题是正确地对行进行分组。

基于此，以上将产生：

Start               | End                 | ST_MakeLine(?)
----------------------------------------------------------------------------
2013-11-12 03:31:31 | 2013-11-12 03:31:43 | LINE((1,2),(1,3),(1,4),(1,5))
2013-11-12 03:31:43 | 2013-11-12 03:31:55 | LINE((1,5),(1,6))
2013-11-12 03:33:22 | 2013-11-12 03:33:32 | LINE((1,7),(1,8),(1,9))

这似乎是大多数其他"连续选择"问题所引用的"岛屿和缺口"问题的变体，但由于排序不规则，因此这些解决方案似乎不适用。

我目前正在SQL之外处理数据以生成序列，但这会导致多次往返，如果可以的话，我希望避免。

示例数据的SQLFiddle：http://sqlfiddle.com/#！15/1ff93/7

Answer 1

我最终采用了由两部分组成的方法来解决这个问题：

• 一个存储过程，将"组id"附加到每一行
• 一个简单的聚合查询

性能明显优于在数据库外部执行(45s vs 2.8s)

因此，给定一个由以下内容创建的表：

CREATE TABLE locations (
id SERIAL PRIMARY KEY,
ts TIMESTAMP WITHOUT TIME ZONE,
location GEOMETRY(Point,4326)
);

下面的函数将遍历该表，并在每行附加一个"组id"：

CREATE FUNCTION group_locations(
IN scan_start_time TIMESTAMP WITHOUT TIME ZONE,
IN max_time_gap INTERVAL, 
IN max_line_duration INTERVAL)
RETURNS TABLE(
out_geom GEOMETRY, 
out_ts TIMESTAMP WITHOUT TIME ZONE, 
out_group_id INTEGER) AS
$BODY$
DECLARE
r locations%ROWTYPE;
gid INTEGER;
lastts TIMESTAMP;
startts TIMESTAMP;
BEGIN
gid := 0;
lastts := NULL;
startts := NULL;
FOR r IN 
SELECT * FROM locations 
WHERE ts > scan_start_time
ORDER BY ts ASC
LOOP
out_ts := r.ts;
out_geom := r.location;
out_group_id := gid;
IF startts IS NULL OR lastts IS NULL THEN
startts := r.ts;
ELSIF r.ts - lastts >= max_time_gap THEN
-- If we've hit a space in our data, bump the group id up
-- and remember the start time for this group
gid := gid+1;
out_group_id = gid;
startts := r.ts;
ELSIF r.ts - startts >= max_line_duration THEN
-- First, emit the current row to end the group
RETURN NEXT;
-- Then, bump the group id and start time, we will
-- re-emit the same row with a higher group_id below
gid := gid+1;
out_group_id := gid;
startts := r.ts;
END IF;
-- Emit the current row with the group_id appended
RETURN NEXT;
lastts := r.ts;
END LOOP;
RETURN;
END;
$BODY$
LANGUAGE plpgsql VOLATILE;

如果运行我的示例数据，结果是：

out_ts              | out_geom | out_group_id
---------------------------------------------
2013-11-12 03:31:31 | (1,2)    | 0
2013-11-12 03:31:34 | (1,3)    | 0
2013-11-12 03:31:37 | (1,4)    | 0
2013-11-12 03:31:43 | (1,5)    | 0
2013-11-12 03:31:43 | (1,5)    | 1
2013-11-12 03:31:55 | (1,6)    | 1
2013-11-12 03:33:22 | (1,7)    | 2
2013-11-12 03:33:28 | (1,8)    | 2
2013-11-12 03:33:32 | (1,9)    | 2

然后，这个过程的输出可以简单地分组和聚合：

SELECT ST_Makeline(out_geom) AS geom,MIN(out_ts) AS start,MAX(out_ts) AS finish
FROM group_locations(
NOW() AT TIME ZONE 'UTC' - '10 days'::INTERVAL,  -- how far back to look
'30 seconds'::INTERVAL,  -- maximum gap allowed before creating a break
'15 seconds'::INTERVAL  -- maximum duration allowed before forcing a break
)
GROUP BY out_group_id;

该函数执行速度相当快，至少比在外部执行相同的逻辑好一个数量级。缺点是结果没有索引，因此在进一步的查询中直接使用它们并不是特别有性能。它在大约O(2N)时间内运行，第一次扫描附加组ID，然后第二次扫描聚合。

我的最终解决方案每隔几分钟执行一次以上操作，以刷新一个完全索引的"calculated_tracks"表。