💻 computer science

TraCS: Trajectory Collection in Continuous Space under Local Differential Privacy

本文提出了 TraCS 框架，通过 TraCS-D 和 TraCS-C 两种方法在本地差分隐私下实现了连续空间中的轨迹收集，不仅解决了现有离散空间方法的局限性，还证明了其在隐私保障独立于空间规模的同时，能显著提升轨迹效用并具备更高的计算效率。

原作者： Ye Zheng, Yidan Hu

发布于 2026-03-03

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Ye Zheng, Yidan Hu

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文介绍了一种名为 TraCS 的新方法，旨在解决一个非常现实的问题：如何在保护用户隐私的前提下，收集大家的移动轨迹数据（比如你每天开车、跑步或坐飞机的路线）？

想象一下，你每天的生活轨迹就像一条**“数字足迹”**。虽然这些数据对城市规划、交通分析很有用，但如果直接收集，就像把你家钥匙和日记本直接交给陌生人一样危险。

为了解决这个问题，研究人员使用了“本地差分隐私”（LDP）技术。你可以把 LDP 想象成**“在数据上撒一把盐”：在数据离开你的手机之前，先人为地加一点“噪音”（干扰），让收集者看到的是一条“模糊但大致正确”**的路线，从而无法精准定位你的真实位置。

然而，以前的方法有一个大毛病：它们像是在**“网格地图”**上撒盐。它们先把世界切成一个个小方格（离散空间），然后随机把点挪到旁边的格子里。这就好比你想描述一个圆形的披萨，却非要用方形的格子去拼，不仅拼不圆，格子越多（城市越大），计算越慢，效果还越差。

TraCS 的突破在于：它不再把世界切成方格，而是直接在“连续空间”（像真实的地图一样平滑、无限）中撒盐。

为了让你更容易理解，我们可以用两个生动的比喻来解释 TraCS 的两种核心方法：

1. TraCS-D：像“指南针 + 卷尺”一样撒盐

想象你要告诉别人你从 A 点走到了 B 点。

传统方法：先猜你在哪个街区，再猜你在街区的哪个角落。
TraCS-D 方法：它把移动分解成两个动作：
1. 方向（指南针）：你往哪个方向走？（比如正北偏东 30 度）。
2. 距离（卷尺）：你走了多远？

怎么撒盐？

方向撒盐：它不会把方向切成固定的扇形（像切披萨一样），而是根据隐私保护的程度，动态地调整“模糊圈”。如果你很在意隐私（隐私参数 $\epsilon$ 小），模糊圈就大；如果你愿意牺牲一点隐私换取更准的数据（ $\epsilon$ 大），模糊圈就自动缩小，紧紧包住真实方向。这就像一个智能的指南针，它不会死板地指错方向，而是根据需求灵活地“晕头转向”。
距离撒盐：同样，它也会给距离加一点随机误差，但这个误差是动态计算的，不会像以前那样不管走多远都加同样的错。

优点：这种方法特别适合那些方向感很强的轨迹，或者在圆形区域（比如雷达扫描）里使用。

2. TraCS-C：像“经纬度坐标”一样撒盐

这是另一种更直观的思路。

方法：直接把你的位置看作地图上的 X 坐标（经度） 和 Y 坐标（纬度）。
怎么撒盐？：它分别给 X 坐标加一点噪音，给 Y 坐标加一点噪音。
比喻：想象你在玩一个“蒙眼画线”的游戏。你原本想画一条直线，但手抖了一下，X 轴偏了一点，Y 轴也偏了一点。TraCS-C 就是专门控制这种“手抖”的机制，确保手抖的幅度既保护了隐私，又不会让你画歪得太离谱。

优点：对于大多数城市里的日常路线（通常是矩形区域），这种方法计算起来非常快，而且效果通常比 TraCS-D 更好。

为什么 TraCS 这么厉害？（三大优势）

不再受“格子数量”限制：
以前的方法，如果城市很大，格子成千上万，计算起来就像在数沙子，慢得要死。TraCS 直接在平滑的地图上操作，不管城市多大，计算速度都一样快。就像你切蛋糕，以前是按块切（格子越多越慢），现在是用刀直接切（速度恒定）。
速度极快：
论文测试显示，TraCS 生成一条受保护轨迹的时间，只有以前最先进方法的 1% 甚至更少。这意味着它可以实时运行在你的手机或智能手表上，不会卡顿。
两头通吃：
虽然 TraCS 是在“连续空间”（平滑地图）里工作的，但它最后可以把结果“四舍五入”到具体的“离散空间”（比如具体的街道或兴趣点）。
- 比喻：就像你用高精度的激光笔在墙上画了一个点（连续空间），然后告诉别人“这个点落在哪个瓷砖上”（离散空间）。这样既享受了连续空间的高精度和速度，又兼容了现有的系统。

总结

这就好比以前的隐私保护像是在粗糙的网格纸上画画，画得慢且容易失真；而 TraCS 就像是在光滑的画布上作画，它用更聪明的“抖动”技巧（方向 + 距离，或 X+Y 坐标），既让画看起来模糊到无法辨认具体是谁（保护隐私），又保留了整体轮廓（保留数据价值），而且画得飞快。

这项技术让未来的位置服务（如导航、运动分析）既能利用大数据，又不用担心泄露我们的行踪秘密。

TraCS 论文技术总结

1. 研究背景与问题定义

背景：
轨迹数据（用户随时间移动的位置序列）对于基于位置的服务（LBS）和活动分析至关重要。然而，直接收集轨迹数据会泄露用户的日常习惯和敏感活动，引发严重的隐私担忧。本地差分隐私（Local Differential Privacy, LDP）提供了一种强有力的隐私保护机制，允许用户在将数据发送给不可信的数据收集者之前，在本地对数据进行扰动。

现有方法的局限性：
现有的 LDP 轨迹收集方法主要针对离散空间（Discrete Spaces），即位置被划分为有限的网格或兴趣点（POI）。这些方法存在以下三个固有缺陷：

隐私保障依赖于空间大小： 离散方法的隐私保障与位置空间的大小（ $|X|$ ）紧密相关。空间越大，有效隐私越弱；且随着候选位置数量增加，机制输出真实位置的概率降低。
效率低下： 广泛使用的指数机制（Exponential Mechanism）在采样时需要遍历所有候选位置，时间复杂度为 $O(m)$ （ $m$ 为位置数量），在大规模位置空间中计算成本高昂。
不适用于连续空间： 许多现实应用（如飞行轨迹、可穿戴设备传感器数据）天然存在于连续空间（Continuous Spaces）。虽然可以将连续空间离散化后应用现有方法，但这不仅继承了上述缺陷，而且难以选择平衡隐私、效用和效率的离散化粒度。

核心问题：
如何在连续空间中设计高效的 LDP 轨迹收集方法，既能提供严格的隐私保证，又能保持高数据效用，同时避免离散化带来的计算和隐私开销？

2. 方法论：TraCS

本文提出了 TraCS（Trajectory Collection in Continuous Space），这是首个针对连续空间设计的纯 LDP 轨迹收集框架。TraCS 的核心思想是将二维连续空间分解为两个一维子空间，并利用现有的基于分段（Piecewise-based）的一维 LDP 机制来构建二维扰动机制。

TraCS 提出了两种具体方法：

2.1 TraCS-D：方向 - 距离分解法

该方法将连续空间 $S$ 视为方向空间（Direction Space, $D_\varphi$ ）和距离空间（Distance Space, $D_{r(\varphi)}$ ）的组合。

方向扰动 ( $M_\circ$ )：
- 挑战： 方向空间 $[0, 2\pi)$ 是圆形的，传统的拉普拉斯机制（无界）或 $k$ -RR（离散）无法直接适用。
- 创新： 作者设计了一种针对圆形域的分段概率分布机制。与简单的“扇区 + 均匀采样”（Strawman 方法）不同，TraCS-D 的“主导扇区”（Dominant Sector）宽度随隐私参数 $\varepsilon$ 动态变化。 $\varepsilon$ 越大，主导扇区越窄，采样误差越小，从而避免了固定扇区带来的固有内扇区误差。
距离扰动 ( $M_-$ )：
- 基于参考位置 $\tau_i$ 和扰动后的方向 $\varphi'$ ，计算到边界的有效距离空间大小 $|D_{r(\varphi)}|$ 。
- 将敏感距离归一化到 $[0, 1)$ ，应用基于分段的 LDP 机制（如 OGPM）进行扰动，再通过线性映射还原。
流程： 依次对轨迹中的每个点进行方向扰动和距离扰动，利用序列组合定理（Sequential Composition）保证整体 LDP。

2.2 TraCS-C：笛卡尔坐标分解法

该方法将矩形连续空间 $S$ 视为两个独立的距离空间（即经度轴和纬度轴）的笛卡尔积。

坐标扰动： 将每个位置 $(a_i, b_i)$ 相对于参考点（如矩形左下角）表示为 $(d_a, d_b)$ 。
机制： 分别对 $d_a$ 和 $d_b$ 进行归一化，并独立应用分段 LDP 机制（各分配 $\varepsilon/2$ 的隐私预算），最后映射回笛卡尔坐标。
特点： 实现简单，两个子空间相互独立，无需计算复杂的几何边界距离。

2.3 离散空间的适配

虽然 TraCS 专为连续空间设计，但可以通过四舍五入（Rounding）将扰动后的连续坐标映射到任意嵌入在连续空间中的离散点集（如网格或 POI）。

隐私保证： 四舍五入是后处理步骤，不改变原有的 LDP 隐私保证。
优势： 此时，TraCS 的隐私和效用保证独立于离散空间的大小，且每个点的扰动时间复杂度仅为 $\Theta(1)$ 。

3. 主要贡献

首创连续空间 LDP 轨迹收集： 提出了 TraCS-D 和 TraCS-C 两种方法，填补了纯 LDP 下连续空间轨迹收集的空白。
理论创新：
- 利用序列组合定理，将二维连续空间分解为两个一维子空间。
- 设计了针对圆形方向空间的自适应主导扇区机制，解决了传统离散化方法在方向扰动上的精度损失问题。
- 证明了两种方法在连续空间下均满足 $n\varepsilon$ -LDP（ $n$ 为轨迹长度）。
效率突破：
- TraCS 生成每个扰动位置的时间复杂度为 $\Theta(1)$ ，与位置空间大小无关。
- 相比之下，基于指数机制的现有方法（如 NGram, ATP）复杂度为 $O(m)$ ，L-SRR 为 $O(m \cdot n)$ 。
通用性： 方法既适用于连续空间，也可通过四舍五入应用于离散空间，且无需针对离散空间重新设计机制。

4. 实验结果

论文在合成数据集和真实世界数据集（东京 TKY、芝加哥 CHI）上进行了广泛评估。

4.1 连续空间表现

效用对比： TraCS 在平均误差（Average Error, AE）上显著优于截断拉普拉斯机制（T-Laplace）和基于 $k$ -RR 的 Strawman 方法。
参数影响： 随着隐私参数 $\varepsilon$ 增大，TraCS 的效用提升明显，而 Strawman 方法由于内扇区误差固定，效用提升有限。
方法选择： 对于随机轨迹，TraCS-C 通常表现更好；但在特定场景（如距离空间较小或圆形区域）下，TraCS-D 可能更优。

4.2 离散空间表现

精度优势： 在离散空间（包括 $10\times10$ 和 $60\times60$ 网格，以及真实城市 POI）中，TraCS 的轨迹效用（AE）普遍优于 NGram、L-SRR 和 ATP。特别是在 $\varepsilon$ 较大时，优势更为显著。
效率优势（关键发现）：
- TraCS 的运行时间极快。在 TKY 数据集上，TraCS 的总耗时仅为 ATP 和 NGram 的 0.05%，仅为 L-SRR 的 1%。
- 单点扰动时间：TraCS-D 和 TraCS-C 仅需约 0.018ms 和 0.003ms，而 ATP 和 NGram 需要数十毫秒。
其他指标： 在范围查询保留率（RQP）和热点保留（Hotspot Preservation）指标上，TraCS 也表现出更好的性能。

5. 意义与结论

技术意义：
TraCS 证明了在连续空间直接进行 LDP 轨迹收集不仅可行，而且在隐私保障的独立性（不依赖空间大小）和计算效率（常数级复杂度）上远优于传统的离散化方法。它消除了离散化粒度选择的难题，为飞行轨迹、传感器数据等天然连续的应用场景提供了理想的隐私保护方案。

实际应用价值：

实时性： 极低的计算开销使其非常适合边缘计算和实时轨迹应用。
通用性： 一套机制即可同时服务于连续和离散场景，降低了系统设计的复杂性。
高性能： 在保持严格 LDP 的同时，提供了比当前最先进方法（SOTA）更高的数据效用，特别是在隐私预算较宽松（ $\varepsilon$ 较大）的场景下。

综上所述，TraCS 通过巧妙的空间分解和基于分段的扰动机制，成功解决了连续空间轨迹隐私保护的效率与效用瓶颈，为未来的位置服务隐私保护提供了新的范式。