TraCS: Trajectory Collection in Continuous Space under Local Differential Privacy

1. Il Problema

La raccolta di dati di traiettoria (sequenze di posizioni che descrivono il movimento nel tempo) è fondamentale per i servizi basati sulla posizione (LBS) e l'analisi delle attività. Tuttavia, questi dati rivelano informazioni altamente sensibili sulle abitudini e la vita privata degli utenti.
Le tecniche di anonimizzazione tradizionali (come la $k$-anonimità) si sono rivelate insufficienti. Di conseguenza, la Privacy Differenziale Locale (LDP) è stata adottata come standard per garantire la privacy anche quando il raccoglitore dei dati non è attendibile.

Tuttavia, i metodi esistenti per la raccolta di traiettorie sotto LDP presentano limitazioni significative:

• Spazi Discreti: La maggior parte dei metodi attuali opera su spazi di posizione discreti (griglie o punti di interesse).
• Dipendenza dalla Dimensione: Le garanzie di privacy e l'utilità dei dati in questi metodi dipendono fortemente dalla dimensione dello spazio dei luoghi (numero di celle o punti). All'aumentare del numero di candidati, la probabilità di restituire la posizione vera diminuisce e la complessità computazionale aumenta (spesso lineare rispetto alla dimensione dello spazio).
• Inadeguatezza per Spazi Continui: Molte applicazioni reali (traiettorie di droni, dati di sensori indossabili, navigazione aerea/marittima) operano naturalmente in spazi continui. Discretizzare questi spazi introduce errori di approssimazione e perde i vantaggi intrinseci della continuità.

2. Metodologia: TraCS

Il paper propone TraCS (Trajectory Collection in Continuous Space), un approccio che sposta il focus dalla raccolta di dati in spazi discreti a quelli continui, mantenendo garanzie LDP rigorose. L'idea centrale è decomporre lo spazio continuo 2D in sottospazi 1D e applicare meccanismi di perturbazione ottimizzati su ciascuno di essi.

Vengono proposti due metodi principali:

A. TraCS-D (Perturbazione di Direzione e Distanza)

Questo metodo tratta lo spazio continuo come una composizione di uno spazio di direzione e uno spazio di distanza rispetto a una posizione di riferimento.

1. Spazio di Direzione ($D_\phi$): Rappresentato come un dominio circolare $[0, 2\pi)$. Viene utilizzato un meccanismo di perturbazione basato su "pezzi" (piecewise-based) adattato al dominio circolare. A differenza degli approcci "strawman" che dividono il cerchio in settori fissi (introducendo errori interni), il dominio di campionamento dominante di TraCS-D si adatta dinamicamente al parametro di privacy $\epsilon$, riducendo l'errore di campionamento.
2. Spazio di Distanza ($D_r$): La distanza dal punto di riferimento fino al bordo dello spazio nella direzione specifica. Viene normalizzata nell'intervallo $[0, 1)$ e perturbata utilizzando un meccanismo piecewise-based.
3. Composizione: I due meccanismi sono composti sequenzialmente per garantire LDP per l'intera posizione 2D.

B. TraCS-C (Perturbazione delle Coordinate Cartesiane)

Questo metodo tratta lo spazio continuo come il prodotto cartesiano di due spazi di distanza indipendenti (longitudine e latenza relativi a un angolo di riferimento fisso).

1. Decomposizione: Ogni posizione è rappresentata da due coordinate distanziali indipendenti ($d_a, d_b$).
2. Perturbazione: Ogni coordinata viene normalizzata su $[0, 1)$ e perturbata indipendentemente utilizzando il meccanismo piecewise-based, con una divisione del budget di privacy ($\epsilon/2$ per ciascuna coordinata).
3. Vantaggio: Sfrutta l'indipendenza delle coordinate per una gestione più semplice e spesso più efficiente in spazi rettangolari.

Adattamento agli Spazi Discreti

Sebbene progettato per spazi continui, TraCS può essere applicato a spazi discreti arrotondando le posizioni perturbate al punto discreto più vicino. Questo passaggio è un'operazione di post-processing che non indebolisce la garanzia di privacy.

3. Contributi Chiave

• Primo lavoro su Spazi Continui: È il primo lavoro a sviluppare metodi di raccolta traiettorie sotto LDP puro specificamente per spazi continui, evitando la discretizzazione preliminare.
• Indipendenza dalla Dimensione: A differenza dei metodi basati sul meccanismo esponenziale (che hanno complessità $\Theta(m)$ dove $m$ è il numero di luoghi), TraCS ha una complessità temporale di $\Theta(1)$ per ogni posizione perturbata, indipendentemente dalla dimensione dello spazio.
• Nuovi Meccanismi di Perturbazione: Introduzione di meccanismi specifici per domini circolari (direzione) e spazi di distanza variabili, che superano le limitazioni degli approcci esistenti.
• Analisi Teorica ed Empirica: Dimostrazione della convergenza dell'errore quadratico medio (MSE) e validazione sperimentale su dataset sintetici e reali.

4. Risultati Sperimentali

Le valutazioni sono state condotte su spazi continui (dati sintetici e reali di Tokyo e Chicago) e su spazi discreti (confronto con NGram, L-SRR e ATP).

• Utilità della Traiettoria (Errore Medio - AE):

  • Negli spazi continui, TraCS supera significativamente i metodi basati su discretizzazione (come il metodo "strawman" e il meccanismo Laplace troncato), specialmente per valori elevati di $\epsilon$.
  • TraCS-C tende a performare meglio di TraCS-D in spazi rettangolari standard, mentre TraCS-D è superiore in scenari specifici dove lo spazio di distanza è più piccolo (es. traiettorie lungo il lato corto di un rettangolo).
  • Negli spazi discreti, TraCS supera gli stati dell'arte (NGram, L-SRR, ATP) in termini di utilità, specialmente quando $\epsilon$ è grande.

• Efficienza Computazionale:

  • TraCS è drasticamente più veloce. Il tempo di esecuzione per posizione è inferiore all'1% di quello richiesto dai metodi di riferimento (NGram, L-SRR, ATP).
  • Mentre i metodi esistenti richiedono tempo lineare rispetto al numero di luoghi ($\Theta(m)$) per il campionamento, TraCS richiede tempo costante ($\Theta(1)$).

• Metriche Aggiuntive:

  • TraCS mostra una migliore preservazione delle query di intervallo (Range Query Preservation) e degli hotspot rispetto ai metodi concorrenti.

5. Significato e Impatto

Il lavoro di TraCS è significativo perché:

1. Risolvi il problema della discretizzazione: Elimina la necessità di scegliere una granularità di discretizzazione, che è un compromesso difficile tra privacy, utilità ed efficienza.
2. Scalabilità: La complessità costante $\Theta(1)$ rende il metodo ideale per applicazioni in tempo reale e su dispositivi edge (es. sensori indossabili, droni), dove le risorse computazionali sono limitate e la dimensione dello spazio geografico può essere enorme.
3. Versatilità: Offre un framework unificato che funziona nativamente in spazi continui ma può essere facilmente adattato a spazi discreti esistenti senza perdere garanzie di privacy.

In conclusione, TraCS dimostra che la raccolta di dati di traiettoria in spazi continui sotto LDP è non solo fattibile, ma superiore in termini di efficienza e utilità rispetto agli approcci basati su discretizzazione, aprendo la strada a nuove applicazioni di servizi basati sulla posizione con garanzie di privacy robuste.