Universidade Federal do Ceará
Mestrado e Doutorado em Ciências da Computação

Título: PrivMDC: Leveraging Multi-Dimensional Correlations to Answer Differentially Private Range Queries

Data: 12/02/2025
Horário: 14h
Local: Sala de Seminários – Bloco 952

Resumo:

Answering multi-dimensional range queries while preserving privacy is a significant problem that has been the focus of recent studies since range queries serve as a core component of many data analysis tasks. Existing techniques that use local differential privacy, which adds noise to users’ data locally, make assumptions that significantly affect utility. In particular, they assume that all attributes in a dataset are correlated and materialize all pair-wise grids/trees. Moreover, they assume that each pair-wise correlation is equally relevant when answering queries. These assumptions result in a low signal/noise ratio, especially for datasets with a large number of attributes.  To address the deficiency of existing techniques, we propose a new approach to answer multi-dimensional range queries that leverage side information and workload characteristics to selectively choose what and how data is collected under the local differential privacy model. Our approach first builds a correlation model to determine how attributes are correlated. Then, we generalize the notion of multi-dimensional grids to capture multi-dimensional correlations. That allows us to materialize fewer grids, boosting the signal/noise ratio. Finally, we propose a new optimization step that considers workload characteristics. We identify the user distribution that minimizes the total error when answering multi-dimensional queries among users during the grid assignment process. We conduct extensive experiments on real and synthetic datasets and demonstrate the superiority of our method over existing approaches.

Banca examinadora:

• Prof. Dr. Javam de Castro Machado (MDCC/UFC) – Orientador
• Prof. Dr. César Lincoln Cavalcante Mattos (MDCC/UFC)
• Prof. Dr. Victor Farias Aguiar Evangelista (UFC)
• Prof. Dr. Divesh Srivastava (AT&T Labs – EUA)
• Prof. Dr. Héber Hwang Arcolezi (Inria/Grenoble – França)