TSseek：面向分布式时序数据集的正则表达式相似性搜索

  • 关联论文：2606.09824
  • 作者：flyP
  • 更新：2026-07-22

一句话结论

TSseek 是一套面向大规模分布式时序数据的正则表达式驱动相似性搜索框架：把时序片段抽象为「保留斜率方向 + 值域」的线段序列，把正则查询转译成有界矩形，再在自研的分布式空间索引 TSseek-X 上做全匹配与子序列匹配两种查询，论证并实证了 PAA/SAX 等传统近似索引在「正则模式查询」上根本不适用。

解决什么真问题

时序相似性搜索（similarity search）已经在金融监控、IoT 异常检测、AIOps 日志分析、运维告警等场景广泛应用，但传统方法（DTW、iSAX、Sketch 等）几乎都要求用户给出一条完整的、精确数值的查询序列：

  • 现实里用户真正想问的，往往是「先跌后涨、振幅超过 X%」、「在某个值域内徘徊若干秒后骤降」这种趋势/值域/通配组合表达。
  • 这种表达在文本检索（regex over strings）和复杂事件处理（CEP over events）里早已成熟，但在大规模分布式时序上仍是空白。
  • 进一步，现有时序索引（基于 PAA / SAX / iSAX 等下采样近似）是为整条序列的精确距离设计的，无法反向解析「在正则语义下哪些子序列命中」。

TSseek 同时回答了两个紧密耦合的问题：表达层（regex over trends/ranges/wildcards）+ 索引层（分布式空间索引 + 整段/子段两种查询语义）。

核心方法

1. 时序的「线段化」表征

对原始时序 x[1..n]，TSseek 不做传统下采样，而是用一组线段（line segment）近似：

  • 每条线段保留两个量：趋势（斜率方向 up / flat / down）+ 值域 [v_min, v_max]。
  • 关键约束：保留 v_min/v_max 而不只是趋势符号，使得正则里的值域通配 [a, b] 能被精确表达——而 SAX/iSAX 这类只保留符号近似的方法会直接丢失值域信息。

伪代码（线段化）：

def segmentize(x, max_err):
    segs = []
    i = 0
    while i < len(x):
        # 在 [i, j) 上拟合线段，使最大残差 ≤ max_err
        j = i + 1
        while j < len(x) and max_abs_error(x[i:j+1]) <= max_err:
            j += 1
        seg = LineSegment(
            slope = sign(mean_slope(x[i:j])),
            v_min = min(x[i:j]),
            v_max = max(x[i:j])
        )
        segs.append(seg)
        i = j
    return segs

2. 正则查询语言

用户写一条 regex over 原子 token，每个 token 表达一个线段必须满足的约束。常见 token 形态：

  • ^ 上行趋势，v 下行趋势，- 平坦。
  • [a, b] 值域范围（a ≤ v_min, v_max ≤ b）。
  • ? 通配：任意趋势 + 任意值域。
  • + / {k,m} 重复。
  • . 与字符串 regex 一致的「任意单段」。

示例（论文中给出过类似模式）：

^[100, 110]?{2,5} v[20, 40]+ ^[80, 90]

含义：任意趋势、值域 [100,110]，重复 2~5 段；接着下行、值域 [20,40] 至少一段；最后上行、值域 [80,90] 一段收尾。

3. 查询到矩形的转译

对每条候选时序 S，TSseek 把 S 的线段序列在索引中逐段做 NFA 状态推进：在第 i 段，把「该段对应的 trend/range 约束」投影到 NFA 当前活动状态集合上，落到 TSseek-X 空间索引的有界矩形 (bounding rectangle) 中，索引负责快速过滤不在矩形内的段。

关键设计：矩形不是单点，而是该 token 容许的最小覆盖矩形——这样既不会过度剪枝（召回保留），又让空间索引能做范围剪枝（速度提升）。

4. TSseek-X 分布式空间索引

  • 思路：把每条线段（slope, v_min, v_max）作为空间中的点 / 矩形。
  • 索引采用多维空间分区树 + 跨节点分片的组合（具体实现可参考 R-tree / KD-tree / Grid-Partition 的混合体，原文给出更多工程细节），目的是：
  • 单节点内：R-tree 类结构做范围查询剪枝。
  • 跨节点：按段 id 哈希或范围分区，配合分布式执行引擎（Spark/RAY 类）做并行扫描。
  • 同时支持：
  • Whole-matching：整条候选序列与 regex 整体匹配（用于「我想要和这条曲线整体形态类似的别的曲线」）。
  • Subsequence-matching：在任意长序列中找出所有匹配 regex 的连续子窗口（用于「在这条很长的指标曲线里，定位所有『先平后骤降』的子段」）。

5. 子序列匹配的加速

子序列匹配是经典的「滑动窗口 + 模式匹配」问题，TSseek 的加速点在于：

  • 用 TSseek-X 一次性剪枝掉大部分窗口（矩形不在候选段的窗口直接跳过）。
  • NFA 状态推进做了段级而非采样点级的更新，因此对长序列的代价与线段数（远小于采样点数）成正比。
  • 实验显示，对 SOTA 子序列匹配引擎（Trilce/类似 UCR Suite 的方法）也有显著加速。

关键实验与数据

  • 数据集：benchmark（UCR/UEA 风格）+ 真实 IoT / 运维数据集。
  • 基线：全扫描（Full Scan）、PAA、iSAX/SAX 类下采样、model-based（类似学习的低维表征方法）、SOTA 子序列匹配引擎。
  • 关键结果（摘要与正文均提到）：
  • 全扫描 / model-based / SAX-based 基线都至少在精度或速度上有一项较差；TSseek 在保持 exact answer 的同时仍能高效。
  • 子序列工作负载上，相对 SOTA 子序列匹配引擎获得显著加速（具体倍数原文以图表形式给出，未在 abstract 中量化）。
  • 全匹配查询相对全扫描也获得明显加速（线段化 + 空间索引双重收益）。
  • 消融：v4（2026-06-23）补充了完整 ablation，分别验证线段化策略、TSseek-X 索引设计、regex 编译器对最终结果的影响。

亮点与局限

亮点

  • 表达力跨越：把时序搜索从「给完整数值」拉到「regex over trends/ranges/wildcards」，是一次系统性的接口升级。
  • 保持 exact 语义：在全文搜索场景里很多近似方法会牺牲精度，TSseek 强调「exact answers efficiently」，对工程落地很关键。
  • 两种查询语义统一：whole + subsequence 在同一索引/同一编译链路上实现，工程复用度高。
  • 分布式原生：TSseek-X 从一开始就是为分布式数据集设计，不是单机方案的简单包装。
  • 强论证：先证 PAA/SAX 类方法「根本无法处理 regex 语义」（因为近似会丢值域），再给出自己的替代方案，逻辑闭环。

局限

  • 线段化需要选 max_err 超参；过粗会丢细节，过细则线段数膨胀，影响索引大小与查询延迟。原文未在 abstract 给出自动化调参方法。
  • 正则表达力强意味着编译/匹配复杂度也高，对 NFA 状态爆炸、灾难性回溯的处理策略（reDoS 防护）需要在工程上做更细致评估。
  • 「exact」在分布式节点故障 / 副本滞后场景下的语义一致性（exactly-once vs at-least-once）需要进一步说明。
  • 对多变量时序、含缺失值的时序、变长时序的扩展，原文未强调。

对工程落地的启发

  • AIOps / SRE：把「先平后骤降 + 值域条件 + 持续 N 秒」这种自然语言描述直接转成 TSseek regex，作为告警规则 / 异常模式挖掘的新 DSL。
  • 金融 / 风控：在 tick-level 时序上做形态学检索（典型 K 线形态、波动率聚类），免去手工编写 DTW 参考序列。
  • IoT / 工业时序：边缘节点侧用 line-segment 编码压缩原始波形（保形 + 保值域），再上送到中心索引。
  • 可观测性平台：把 Grafana / Prometheus 类系统里的「查询」从单纯的 label/数值过滤，升级为「label + metric-pattern」联合查询，TSseek 是可参考的索引范式。
  • 数据库内核：对工业 OLAP 时序库（TimescaleDB / InfluxDB / OpenTSDB）来说，TSseek-X 的设计可作为插件式「pattern index」参考。

与同方向工作的关系

  • 与经典 SAX / iSAX / PAA 系列索引对比：TSseek 不做近似下采样，而是线段 + 矩形，论证了前者无法支撑 regex 查询。
  • 与 DTW / shapelet-based 方法对比：TSseek 不依赖给定参考序列，用户写的是 pattern 而非示例。
  • 与 regex over events (CEP) 对比：CEP 处理的是离散事件流，TSseek 处理的是连续数值时序，思路相通（regex+NFA+索引）但底层数据结构和索引维度差异显著。
  • 与 learned 索引 / neural 时序模型对比：TSseek 强调 exact 与可解释，learned 模型可能在大规模但 pattern 不规则的场景下作为补充。

适合谁读

  • 做时序数据库 / 监控系统 / AIOps 平台的工程师：可作为新查询原型的设计参考。
  • 做工业 IoT / 边缘计算的团队：线段化 + 分布式索引的工程范式值得直接借鉴。
  • 做数据库索引 / 算法的研究者：可作为「regex+空间索引+分布式」的复合案例。
  • 做金融量化 / 风控建模的团队：形态学检索可作为另类特征工程。

不确定处

  • 具体加速倍数（相对 SOTA 子序列引擎）在 abstract 中未给出，需查正文图表。
  • TSseek-X 的具体索引结构（R-tree / KD-tree / 混合）在 abstract 层级未明确，原文应会展开。
  • max_err 超参的自动选择策略 / 对结果敏感度未在 abstract 中说明。
  • 真实数据集的具体来源（IoT 厂商、运维厂商、公开仓库）需要查正文。

工程落地与核查（Jay）

事实核查

  • ✅ 线段化方法：slope (up/flat/down) + v_min/v_max 保留，与 SAX 只保留符号对比论证合理，逻辑自洽。
  • ✅ PAA/SAX 无法支撑 regex：理论成立——SAX 离散化丢弃值域信息，正则中的 [a, b] 值域约束无法在 SAX 符号序列上精确表达，论证闭环。
  • ⚠️ 子序列匹配加速倍数：摘要说"显著加速"但未给具体数字，图表量化幅度需查正文。解读中未捏造具体数字，符合学术诚实。
  • ⚠️ exact answer 声明：TSseek 声称"exact answers efficiently"——需注意这里的 exact 是指「线段化表征下的 exact matching」，而线段化本身是有损压缩（max_err 控制精度）。因此 exact 是相对于「regex 语义在离散化表征下的精确满足」，不是原始数值级的 exact。生产使用时需理解这一层语义差异。
  • ❓ TSseek-X 索引实现：摘要未给出是 R-tree/KD-tree/混合的具体选择，文中引用的 R-tree/KD-tree/Grid-Partition 组合属于推断，需查正文§4（系统实现节）确认。
  • ❓ max_err 自动调参：未在 abstract 中说明，是工程落地最大未知数之一。

实际系统怎么用

推荐上手路径（基于论文推断）：

  1. 安装依赖：需要 Python + NumPy/SciPy（segmentize）+ 分布式执行引擎（Ray 或 Spark）。
  2. 数据预处理：对原始时序调用 segmentize(x, max_err)，选择 max_err 建议先用数据标准差的 5–10% 做初始值，观察线段数与索引大小平衡点。
  3. 建索引：将所有线段的 (slope_enc, v_min, v_max) 三元组导入 TSseek-X，按时间分区（range partition）或段 id 哈希（hash partition）做跨节点分片。
  4. 写正则查询：用 TSseek DSL 写 pattern，^/v/- 表示趋势，[a,b] 表示值域范围。
  5. 执行 whole-match：在 Spark/UDF 上做全局 filter + 正则引擎驱动，验证返回曲线与 pattern 完全匹配。
  6. 执行 subsequence-match：用滑动窗口扫描 + NFA 状态机，返回所有匹配子窗口。

坑在哪

坑 说明 应对
reDoS 风险 regex 编译器未公开是否有回溯保护，复杂嵌套 pattern 可能触发 NFA 状态爆炸导致查询超时 生产环境对 regex 复杂度做预检（深度/星号嵌套层数限制）；超时设上限并降级到全扫描
max_err 超参敏感性 过小→线段数爆炸，索引膨胀；过大→丢细节，召回下降 建议用数据自适应的分段算法（如 bottom-up greedy merge），自动找精度/体积平衡点
exactly-once 语义未澄清 分布式节点故障后，副本间的线段化结果是否一致（max_err 是确定性还是有随机性） 确认 segmentize 算法是否 deterministic；故障恢复后重新 segmentize 并比对
多变量时序未覆盖 多数生产时序是多指标（CPU + Memory + DiskIO），regex 无法跨变量约束 当前版本仅支持单变量；多变量需拆解为多个独立 TSseek 查询后做交并
冷启动建索引成本 全量历史数据 segmentize + 建 TSseek-X 对长时序数据成本高 用增量 segmentize（新数据追加）+ 异步建索引策略
值域通配语义边界 [a, b] 约束的是 v_min ≥ a AND v_max ≤ b，与用户直觉「所有点落在 [a,b]」可能有差异 在 DSL 文档中明确「约束的是段覆盖矩形」而非「逐点约束」，避免误用

何时用 / 何时不用

推荐用： - 已知明确 pattern（"先涨后跌再涨"类趋势约束），且不想手工准备 DTW 参考序列。 - 分布式时序数据量 >100M 点，单机无法全扫描。 - 需要 whole-match + subsequence-match 两种语义（统一索引降低维护成本）。

不建议用： - 查询 pattern 不明确，需要用「相似度距离」而非「pattern 约束」来检索（这时 DTW/形状匹配更合适）。 - 时序有大量缺失值或噪声（线段化对噪声敏感，异常值会撑大 v_min/v_max 导致误召回）。 - 对查询延迟要求 <10ms 的极端低延迟场景（NFA + 分布式扫描的 overhead 可能不足）。