TraCS: Trajectory Collection in Continuous Space under Local Differential Privacy

1. 문제 정의 (Problem)

• 배경: 위치 기반 서비스 (LBS) 를 위해서는 사용자의 궤적 데이터 (시간에 따른 위치 시퀀스) 수집이 필수적이지만, 이는 사용자의 일상 습관 및 민감한 활동을 노출시켜 심각한 프라이버시 위협이 됩니다.
• 현재의 한계: 기존 궤적 수집 방법은 국소적 차분 프라이버시 (LDP) 를 적용하더라도 대부분 이산 공간 (Discrete Space) 에 국한되어 있습니다.
  • 이산 공간의 단점:
    1. 공간 크기에 의존: 프라이버시 보장과 데이터 유용성 (Utility) 이 위치 공간의 크기 (그리드 수 또는 관심 지점 수) 에 직접적으로 의존합니다. 공간이 커질수록 유용성이 급격히 떨어집니다.
    2. 계산 비용: 지수 메커니즘 (Exponential Mechanism) 등을 사용할 경우, 후보 위치 수가 많아지면 샘플링 및 점수 평가에 선형 시간 복잡도 ($\Theta(m)$) 가 소요되어 실시간 적용이 어렵습니다.
    3. 적용 불가: 비행 궤적, 웨어러블 센서 데이터 등 본질적으로 연속 공간 (Continuous Space) 에서 발생하는 데이터에는 직접 적용하기 어렵습니다. 연속 공간을 이산화하는 과정은 추가적인 오차와 복잡성을 유발합니다.

2. 제안 방법: TraCS (Methodology)

이 논문은 이산 공간이 아닌 연속 공간에서 직접 궤적을 수집하기 위해 TraCS라는 두 가지 새로운 LDP 메커니즘을 제안합니다. 핵심 아이디어는 2 차원 연속 공간을 1 차원 부분 공간으로 분해하고, 기존에 개발된 1 차원 최적화 기반 (Piecewise-based) 메커니즘을 활용하는 것입니다.

A. TraCS-D (Direction & Distance Perturbation)

• 개념: 위치 공간을 방향 (Direction) 과 거리 (Distance) 의 조합으로 분해합니다.
  • 방향 공간 ($D_\varphi$): $[0, 2\pi)$ 의 원형 도메인입니다.
  • 거리 공간 ($D_{r(\varphi)}$): 기준 위치에서 특정 방향 $\varphi$ 로 이동할 때 공간의 경계까지의 거리입니다.
• 메커니즘:
  1. 방향 교란: 원형 도메인 $[0, 2\pi)$ 에 적합한 조각 기반 (Piecewise-based) 메커니즘을 적용하여 방향을 교란합니다. 이는 고정된 섹터 (Sector) 를 사용하는 기존 방식과 달리, 프라이버시 파라미터 $\epsilon$ 에 따라 우세한 섹터 (Dominant Sector) 의 크기가 동적으로 조절되어 내부 오차를 최소화합니다.
  2. 거리 교란: 정규화된 거리 $[0, 1)$ 에 대해 조각 기반 메커니즘을 적용합니다.
  3. 조합: 교란된 방향과 거리를 다시 2 차원 좌표로 변환합니다.
• 특징: 방향 정보가 먼저 교란된 후 거리가 교란되며, 시퀀스 합성 정리를 통해 전체 궤적에 대해 LDP 를 보장합니다.

B. TraCS-C (Cartesian Coordinate Perturbation)

• 개념: 위치 공간을 직교 좌표 (Cartesian Coordinates) 의 두 독립적인 거리 공간 ($D_a, D_b$) 으로 분해합니다.
• 메커니즘:
  1. 기준 좌표 (예: 공간의 왼쪽 하단) 를 기준으로 각 위치의 $x$ 축 거리 ($d_a$) 와 $y$ 축 거리 ($d_b$) 를 계산하고 $[0, 1)$ 로 정규화합니다.
  2. 두 좌표에 대해 각각 독립적으로 조각 기반 메커니즘을 적용하여 교란합니다.
  3. 교란된 좌표를 다시 원래 좌표계로 변환합니다.
• 특징: 구현이 간단하며, 직사각형 공간에서 두 좌표가 독립적이므로 효율적입니다.

C. 이산 공간 적용

• TraCS 는 연속 공간에서 생성된 교란된 위치를 가장 가까운 이산 점 (Discrete Point) 으로 반올림 (Rounding) 함으로써 이산 공간에도 적용 가능합니다.
• 이 과정은 사후 처리 (Post-processing) 이므로 LDP 보장을 약화시키지 않습니다.
• 시간 복잡도: 기존 이산 공간 방법들 (NGram, L-SRR, ATP 등) 이 후보 위치 수 $m$ 에 비례하는 $\Theta(m)$ 복잡도를 가지는 반면, TraCS 는 위치 수와 무관하게 $\Theta(1)$ 의 상수 시간 복잡도를 가집니다.

3. 주요 기여 (Key Contributions)

1. 최초의 연속 공간 LDP 궤적 수집: 순수 LDP 하에서 연속 공간 궤적 수집을 위한 최초의 방법론을 제시했습니다.
2. 새로운 메커니즘 설계: 2 차원 연속 공간을 1 차원 부분 공간으로 분해하고, 유틸리티가 최적화된 조각 기반 메커니즘을 활용하여 방향/좌표 교란을 수행하는 TraCS-D 와 TraCS-C 를 제안했습니다.
3. 이론적 및 실험적 분석:
   • 연속 공간에서의 LDP 보장을 수학적으로 증명했습니다.
   • 교란된 위치의 평균 제곱 오차 (MSE) 가 $\epsilon$ 이 증가함에 따라 지수적으로 감소함을 보였습니다.
4. 효율성 및 유용성 입증: 이산 공간에서도 기존 최첨단 방법들보다 월등히 빠른 속도와 더 높은 궤적 유용성을 달성함을 실험을 통해 입증했습니다.

4. 실험 결과 (Results)

실험은 합성 데이터 (Synthetic) 와 실제 데이터 (Tokyo, Chicago) 를 사용하여 수행되었습니다.

• 연속 공간 성능:

  • TraCS 는 기존 strawman 접근법 (방향에 $k$-RR 적용) 과 잘라낸 Laplace 메커니즘 (Truncated Laplace) 보다 평균 오차 (Average Error, AE) 가 현저히 낮았습니다.
  • 특히 프라이버시 파라미터 $\epsilon$ 이 클수록 TraCS 의 유용성 우위가 두드러졌습니다.
  • TraCS-C 는 일반적인 직사각형 공간에서 TraCS-D 보다 우수한 성능을 보였으나, TraCS-D 는 특정 방향의 거리가 짧은 경우 (예: 좁은 도로) 에 유리할 수 있습니다.

• 이산 공간 성능:

  • 유용성: NGram, L-SRR, ATP 와 비교했을 때, TraCS 는 모든 $\epsilon$ 범위에서 더 낮은 평균 오차를 보였습니다. 특히 $\epsilon$ 이 크고 위치 공간이 세분화될수록 (예: $60 \times 60$ 그리드) 성능 차이가 커졌습니다.
  • 범위 쿼리 및 핫스팟 보존: TraCS 는 범위 쿼리 보존율 (RQP) 이 높고 핫스팟 보존 오차 (CD) 가 낮아, 교란된 데이터의 분석 가치가 높음을 입증했습니다.
  • 시간 비용: TraCS 는 기존 방법들보다 압도적으로 빠릅니다.
    • NGram 및 ATP 대비 총 소요 시간이 0.05% 미만 (약 2000 배 이상 빠름).
    • L-SRR 대비 1% 미만의 시간 소요.
    • 이는 TraCS 가 지수 메커니즘의 복잡한 샘플링이나 그룹화 과정 없이 상수 시간 ($\Theta(1)$) 으로 교란을 수행하기 때문입니다.

5. 의의 및 결론 (Significance)

• 프라이버시와 유용성의 균형: 이산 공간의 크기 제약에서 벗어나, 연속 공간에서 직접 데이터를 처리함으로써 공간 크기에 따른 유용성 저하 문제를 해결했습니다.
• 실시간 적용 가능성: $\Theta(1)$ 의 시간 복잡도는 엣지 디바이스나 실시간 애플리케이션에서 대규모 궤적 데이터를 처리하는 데 필수적인 효율성을 제공합니다.
• 범용성: 제안된 방법은 본질적으로 연속 공간에 최적화되었지만, 반올림을 통해 기존 이산 공간 기반 애플리케이션에도 즉시 적용 가능하여, 기존 방법들의 한계를 극복하는 새로운 표준을 제시합니다.

요약하자면, TraCS는 LDP 하에서 궤적 데이터를 수집할 때 발생하는 이산화 오차와 계산 비효율성을 해결하고, 연속 공간에서 직접 작동하여 프라이버시 보장, 높은 데이터 유용성, 그리고 실시간 처리 속도를 모두 달성한 획기적인 프레임워크입니다.