Resumo Técnico: ReBound – Privacidade Consciente de Reuso para Suporte à Decisão Interativo

Declaração do Problema

Consultas complexas de suporte à decisão (DS), que envolvem múltiplas condições agregadas (ex: "COUNT(Flu) > 100 AND AVG(Temp) > 101"), são fundamentais para aplicações em diagnóstico clínico, gestão predial e avaliação de KPIs. Essas consultas frequentemente operam sobre dados sensíveis, necessitando de Privacidade Diferencial (DP) para evitar vazamento de informações. No entanto, os mecanismos padrão de DP introduzem ruído que pode degradar a qualidade da decisão, levando a Falsos Positivos (FP) e Falsos Negativos (FN).

Frameworks existentes focados em "utilidade primeiro" (ex: APEx, MIDE, ProBE) fornecem garantias formais sobre Taxas de Falso Negativo (FNR) e Taxas de Falso Positivo (FPR) ao otimizar orçamentos de privacidade para atender a alvos específicos de utilidade. Contudo, uma limitação crítica desses sistemas é que eles tratam cada consulta como um evento independente. Na prática, analistas trabalham de forma interativa, emitindo sequências de consultas relacionadas para refinar limites, ajustar limiares ou derivar novas funções. Sob os paradigmas atuais, cada refinamento incorre em um custo total de privacidade, fazendo com que o orçamento cumulativo de privacidade se esgote linearmente com o número de interações, mesmo quando as consultas sucessivas compartilham uma sobreposição significativa.

O problema central abordado é como reutilizar sistematicamente resultados em cache de consultas diferencialmente privadas anteriores para responder a novas consultas relacionadas com custo de privacidade reduzido ou zero, mantendo garantias formais de FNR e FPR.

Metodologia: O Framework ReBound

O ReBound é um framework projetado para preencher a lacuna entre mecanismos de DP estáticos e fluxos de trabalho de analistas interativos. Ele opera em três princípios fundamentais: reuso de pós-processamento, propagação de utilidade e negociação consciente do orçamento.

1. Estratégias de Reuso

O ReBound identifica quatro tipos distintos de refinamento de consulta e aplica estratégias de derivação específicas para cada um, garantindo que as respostas derivadas satisfaçam os limites de utilidade solicitados ($\alpha$ para FPR, $\beta$ para FNR):

• Correspondência Exata (Exact Match): Se o cache contiver um lançamento para a mesma consulta atômica exata, o sistema reutiliza o valor escalar ruidoso. O limite $\beta$ é herdado diretamente. O sistema então verifica se o $\alpha$ induzido (FPR) atende ao solicitado; se não, executa um passo mínimo de endurecimento de $\alpha$ (usando o mecanismo ProBE) incorrendo apenas em custo incremental.
• Mudança de Limiar (Threshold Change): Para a mesma consulta com um limiar diferente, o ReBound reutiliza o escalar ruidoso em cache e recomputa a decisão via pós-processamento. O limite $\beta$ é transferido porque depende da região de incerteza, não do limiar. O limite $\alpha$ é reverificado; se falhar, um custo incremental é incorrido para endurecer a região.
• Decomposição de Predicado (Predicate Decomposition): Se um predicado solicitado puder ser expresso como uma operação de conjunto (união, interseção, diferença) de predicados em cache, o ReBound combina os escalares em cache relevantes. Para funções aditivas (COUNT, SUM), isso envolve combinações lineares de escalares ruidosos. O sistema propaga o $\beta$ de forma conservadora e verifica o $\alpha$.
• Combinação Linear (Linear Combination): Para agregados expressáveis como funções determinísticas de escalares em cache (ex: $AVG = SUM/COUNT$ ou $COUNT(x) + COUNT(y)$), o ReBound deriva o valor candidato via pós-processamento. O limite $\beta$ é propagado com base na sensibilidade e regiões de erro das entradas, e o $\alpha$ final é aplicado no resultado combinado.

2. Estrutura do Cache

Para facilitar a busca eficiente e a derivação, o ReBound emprega um cache de Grafo Acíclico Dirigido (DAG) de três camadas:

• Camada 1 (Índice de Predicados): Armazena nós de colunas e nós de predicados (intervalos para numéricos, conjuntos de valores para categóricos). Esta camada suporta decomposição de predicados.
• Camada 2 (Agregados Escalares): Armazena nós correspondentes a pares (predicado, função). Cada nó mantém lançamentos sob vários parâmetros ($c, \beta, \alpha, \epsilon$) e suporta nós derivados (ex: $a_4 = a_1 + a_2$) que armazenam expressões de derivação.
• Camada 3 (Composição Booleana): Representa cláusulas HAVING compostas (AND/OR), permitindo o reuso quando a estrutura lógica de uma consulta muda.

3. Processamento de Consulta e Negociação

Quando uma nova consulta chega, o ReBound a analisa em uma forma canônica e percorre o DAG do cache para selecionar uma estratégia de reuso.

• Se uma derivação completa for encontrada, a resposta é retornada com $\Delta\epsilon = 0$.
• Se apenas o reuso parcial for possível, o sistema executa o mecanismo ProBE apenas para os componentes não resolvidos.
• Mecanismo de Negociação: Se os limites de utilidade exigidos não puderem ser atendidos dentro do orçamento de privacidade restante ($\epsilon_{max}$), o sistema não simplesmente nega a consulta. Em vez disso, ele propõe uma contraproposta com limites relaxados (ex: um $\alpha$ ou $\beta$ ligeiramente maior) que pode ser satisfeito dentro do orçamento, permitindo que o analista aceite um compromisso significativo.

Principais Contribuições

1. Framework de Reuso para Consultas de DS: Ao contrário de trabalhos anteriores focados em limites de erro numérico ou cargas de trabalho lineares, o ReBound introduz um framework especificamente para consultas de classificação por limiar, onde a utilidade é definida por FNR/FPR por predicado. Ele suporta múltiplos tipos de refinamento (limiares, limites, estrutura lógica, combinações lineares).
2. Design de Cache Hierárquico: O artigo propõe uma estrutura de DAG de três camadas inovadora que armazena não apenas respostas finais, mas também resultados intermediários e subexpressões compostas. Isso maximiza as oportunidades de reuso mesmo quando a estrutura geral da consulta muda.
3. Negociação de Privacidade: O sistema introduz um mecanismo para lidar com solicitações inviáveis oferecendo relaxações mínimas nos limites de precisão, evitando a negação direta de consultas e maximizando a carga de trabalho sob orçamentos fixos.

Resultados Preliminares

Os autores avaliaram o ReBound usando padrões de sessão de analistas sobre o conjunto de dados de táxis de NYC (aprox. 3 milhões de viagens). Dois padrões foram testados:

• Padrão A (Drill-and-Tighten): Endurecendo progressivamente os limites de precisão e ajustando os limiares.
• Padrão B (Exploratory Branching): Pivotando através de predicados, agregados e combinações lineares.

Descobertas:

• Economia de Privacidade: O ReBound alcançou uma redução de 75% na perda de privacidade cumulativa para o Padrão A e 70% para o Padrão B em comparação com um baseline sem reuso.
• Vazão de Consulta (Throughput): Sob orçamentos de privacidade fixos, o sistema baseline pôde responder apenas 4 de 10 consultas (Padrão A) e 3 de 10 (Padrão B). O ReBound respondeu com sucesso a todas as 10 consultas em ambos os padrões.
• Eficácia da Negociação: Em cenários onde limites estritos levaram a negações de consulta (ex: 12 negações em 10 execuções para o Padrão A sem negociação), habilitar a negociação permitiu que todas as consultas tivessem sucesso ao oferecer relaxações menores (ex: ajustando $\alpha$ de 0,05 para 0,063).

Significância e Alegações

O artigo afirma que o ReBound aborda a ineficiência de tratar consultas de suporte à decisão interativas como eventos independentes. Ao reutilizar sistematicamente os resultados em cache, o ReBound permite sessões de análise interativas significativamente mais longas e complexas sob orçamentos de privacidade fixos. O framework mantém garantias formais de utilidade (FNR/FPR) enquanto minimiza a perda de privacidade incremental.

Os autores observam que o trabalho atual apresenta o framework e resultados preliminares, com provas formais para todos os casos de reuso, operações de cache otimizadas e um framework de negociação completo reservados para implementação futura em um sistema completo. Eles também planejam estender o sistema para suportar formas mais ricas de reuso parcial e tipos adicionais de consultas.