TraCS: Trajectory Collection in Continuous Space under Local Differential Privacy

Resumo Técnico: TraCS

1. O Problema

A coleta de dados de trajetória (sequências de locais que descrevem o movimento ao longo do tempo) é fundamental para serviços baseados em localização e análise de atividades. No entanto, esses dados revelam informações altamente sensíveis sobre os usuários, como rotinas diárias e atividades pessoais.

• Limitações das Abordagens Atuais: Os métodos existentes de Privacidade Diferencial Local (LDP) para trajetórias são projetados principalmente para espaços discretos (grades ou conjuntos finitos de pontos de interesse).
• Desafios dos Espaços Discretos:
  1. Dependência do Tamanho do Espaço: A garantia de privacidade e a utilidade dos dados degradam-se à medida que o número de locais candidatos aumenta.
  2. Custo Computacional: Mecanismos como o Exponential Mechanism exigem complexidade linear em relação ao tamanho do domínio ($\Theta(m)$), tornando-os ineficientes para grandes espaços.
  3. Inadequação para Dados Contínuos: Muitas aplicações reais (como trajetórias de voo, navegação ou dados de sensores vestíveis) operam naturalmente em espaços contínuos. Discretizar esses dados antes da perturbação introduz erros de granularidade e herda as limitações acima.

O objetivo do artigo é desenvolver métodos de coleta de trajetórias que operem diretamente em espaços contínuos sob LDP, garantindo privacidade rigorosa, alta utilidade e eficiência computacional.

2. Metodologia: TraCS

Os autores propõem TraCS (Trajectory Collection in Continuous Space), que introduz duas abordagens principais para perturbar trajetórias em um domínio contínuo bidimensional ($S \subset \mathbb{R}^2$). A ideia central é decompor o espaço 2D em dois subespaços 1D e aplicar mecanismos de perturbação otimizados em cada um, utilizando o Teorema de Composição Sequencial para garantir a privacidade global.

As duas variações do método são:

A. TraCS-D (Perturbação de Direção e Distância)

• Decomposição: Trata o espaço contínuo como a composição de um espaço de direção ($D_\phi$, um domínio circular $[0, 2\pi)$) e um espaço de distância ($D_r(\phi)$, dependente da direção).
• Mecanismo de Direção: Desenvolve um novo mecanismo de perturbação baseado em piecewise (pedaços) para o domínio circular. Diferente de abordagens ingênuas que dividem o círculo em setores fixos (como $k$-RR), o TraCS-D define um "setor dominante" que se ajusta dinamicamente ao parâmetro de privacidade $\epsilon$. Isso reduz o erro de amostragem dentro do setor.
• Mecanismo de Distância: Normaliza a distância e aplica um mecanismo baseado em piecewise (inspirado em OGPM) para garantir LDP no intervalo $[0, 1)$.
• Fluxo: Para cada ponto da trajetória, perturba-se a direção do movimento e, em seguida, a distância percorrida nessa nova direção.

B. TraCS-C (Perturbação de Coordenadas Cartesianas)

• Decomposição: Trata o espaço retangular como o produto cartesiano de dois espaços de distância independentes (eixos $x$ e $y$).
• Mecanismo: Normaliza as coordenadas cartesianas para o intervalo $[0, 1)$ e aplica o mecanismo de perturbação baseado em piecewise independentemente em cada eixo.
• Vantagem: Simplifica o cálculo, pois os subespaços são independentes da localização específica do usuário, ao contrário do TraCS-D onde o espaço de distância depende da direção.

Aplicação a Espaços Discretos:
Embora projetado para contínuos, o TraCS pode ser aplicado a espaços discretos arredondando os locais perturbados para o ponto discreto mais próximo. Isso preserva a garantia de privacidade (devido à propriedade de pós-processamento) e elimina a dependência do tamanho do conjunto de locais.

3. Contribuições Principais

1. Primeiro Trabalho em LDP Puro para Espaços Contínuos: É a primeira proposta de métodos de coleta de trajetórias que operam nativamente em espaços contínuos sob LDP, evitando a necessidade de discretização prévia.
2. Eficiência Computacional ($\Theta(1)$): Ao contrário dos métodos baseados no Exponential Mechanism (que exigem $\Theta(m)$ para amostragem), o TraCS gera cada ponto perturbado em tempo constante $\Theta(1)$, independentemente do tamanho do espaço de localização.
3. Novos Mecanismos de Perturbação:
   • Um mecanismo inovador para domínios circulares (direção) que supera as limitações de erros internos de métodos baseados em setores fixos.
   • Integração de mecanismos piecewise otimizados para utilidade em subespaços 1D.
4. Análise Teórica e Experimental: Prova teórica da garantia de LDP e análise de convergência do erro quadrático médio (MSE), mostrando que o erro decai exponencialmente com o aumento de $\epsilon$.

4. Resultados Experimentais

Os autores avaliaram o TraCS em espaços sintéticos e reais (conjuntos de dados de Tóquio e Chicago), comparando-o com métodos do estado da arte (NGram, L-SRR, ATP) e com uma abordagem "palhaço" (strawman) baseada em $k$-RR.

• Utilidade (Erro Médio - AE):
  • Em espaços contínuos, o TraCS superou consistentemente o método strawman e o mecanismo Laplaciano truncado, especialmente para valores maiores de $\epsilon$.
  • Em espaços discretos, o TraCS (especialmente a versão TraCS-C) demonstrou menor erro médio (AE) do que NGram, L-SRR e ATP. A vantagem torna-se mais significativa à medida que o número de pontos discretos aumenta.
  • O TraCS-C geralmente apresentou melhor utilidade para trajetórias aleatórias, enquanto o TraCS-D foi superior em cenários específicos onde o espaço de distância é menor.
• Eficiência (Tempo de Execução):
  • O TraCS é drasticamente mais rápido. Em testes, o tempo total de execução do TraCS foi menos de 1% do tempo necessário para os métodos NGram, ATP e L-SRR.
  • O custo de perturbação por local no TraCS é de apenas 0,003 ms, comparado a centenas de milissegundos para os concorrentes baseados em Exponential Mechanism.
• Preservação de Consultas e Hotspots: O TraCS manteve melhor a precisão de consultas de intervalo (Range Query Preservation) e a retenção de hotspots após o arredondamento, indicando que a utilidade dos dados para tarefas downstream é superior.

5. Significado e Conclusão

O artigo TraCS representa um avanço significativo na privacidade de dados de localização. Ao migrar da abordagem de discretização para o tratamento nativo de espaços contínuos, o trabalho resolve o dilema entre privacidade, utilidade e eficiência.

• Impacto Prático: Permite a coleta de dados de sensores vestíveis, drones e GPS de alta precisão sem a perda de informação inerente à discretização e sem o custo computacional proibitivo dos métodos atuais.
• Versatilidade: A capacidade de aplicar o método tanto em cenários contínuos quanto discretos (via arredondamento) torna-o uma solução robusta e adaptável para diversas aplicações de serviços baseados em localização.

Em suma, o TraCS demonstra que a coleta de trajetórias em espaços contínuos não apenas é viável sob LDP, mas também oferece vantagens superiores em termos de utilidade dos dados e eficiência computacional em comparação com as melhores práticas atuais baseadas em espaços discretos.