Differentially Private Selection using Smooth Sensitivity
Resumo
Mecanismos de seleção diferencialmente privados (DP) obtem o elemento de maior qualidade em um conjunto finito, garantindo forte privacidade. No entanto, a maioria dos métodos existentes usa sensibilidade global, frequentemente adicionando ruído excessivo e prejudicando a utilidade dos resultados. Propomos o algoritmo Smooth Noisy Max (SNM), que emprega sensibilidade suave para obter limites de erro mais precisos e maior acurácia sob condições moderadas. Experimentos mostram que o SNM supera os melhores métodos de seleção com DP em três aplicações: seleção de percentis, árvores de decisão gananciosas e florestas aleatórias.
Palavras-chave:
differential privacy selection
Referências
Danilo Alves, Victor A. E. de Farias, Iago C. Chaves, Richard Chao, João Paulo Madeiro, João Paulo Pordeus Gomes, and Javam C. Machado. Detecting customer induced damages in motherboards with deep neural networks. In International Joint Conference on Neural Networks, IJCNN 2022, Padua, Italy, July 18-23, 2022, pages 1–8. IEEE, 2022. DOI: 10.1109/IJCNN55064.2022.9892047.
L. Cabral, V. Farias, L. Sena, I. Chaves, J. P. Pordeus, J. P. Santiago, D. Sá, J. Machado, and J. P. Madeiro. An active learning approach for detecting customer induced damages in motherboards with deep neural networks. Learning & Nonlinear Models, 21(2):29–42, 2023. DOI: 10.21528/lnlm-vol21-no2-art3.
Victor A. E. de Farias, Felipe T. Brito, Cheryl J. Flynn, Javam C. Machado, Subhabrata Majumdar, and Divesh Srivastava. Local dampening: differential privacy for non-numeric queries via local sensitivity. VLDB J., 32(6):1191–1214, 2023. DOI: 10.1007/S00778-022-00774-W.
Maria de Lourdes Maia Silva, Iago Castro Chaves, and Javam de Castro Machado. Aplicação de top-k reverso com privacidade sobre os dados públicos de COVID-19 no estado do ceará. In Proceedings of the 35th Brazilian Symposium on Databases, SBBD 2020, Online, September 28 - October 1, 2020, pages 193–198. SBC, 2020. DOI: 10.5753/SBBD.2020.13640.
Sam Fletcher and Md Zahidul Islam. Differentially private random decision forests using smooth sensitivity. Expert Syst. Appl., 78:16–31, 2017. DOI: 10.1016/j.eswa.2017.01.034.
Fernando Dione S. Lima, Francisco Lucas Falcao Pereira, Iago C. Chaves, Javam C. Machado, and João Paulo Pordeus Gomes. Predicting the health degree of hard disk drives with asymmetric and ordinal deep neural models. IEEE Trans. Computers, 70 (2):188–198, 2021. DOI: 10.1109/TC.2020.2987018.
Maria de Lourdes M. Silva, Iago C. Chaves, and Javam C. Machado. Private reverse top-k algorithms applied on public data of covid-19 in the state of ceará. Journal of Information and Data Management, 12(5), Nov. 2021. DOI: 10.5753/jidm.2021.1941. URL [link].
Francisco Lucas Falcao Pereira, Iago Castro Chaves, João Paulo Pordeus Gomes, and Javam C. Machado. Using autoencoders for anomaly detection in hard disk drives. In 2020 International Joint Conference on Neural Networks, IJCNN 2020, Glasgow, United Kingdom, July 19-24, 2020, pages 1–7. IEEE, 2020. DOI: 10.1109/IJCNN48605.2020.9206689.
Lucas B. Sena, Francisco D. B. S. Praciano, Iago C. Chaves, Felipe T. Brito, Eduardo Rodrigues Duarte Neto, José Maria Monteiro, and Javam C. Machado. AUDIO-MC: A general framework for multi-context audio classification. In Joaquim Filipe, Michal Smialek, Alexander Brodsky, and Slimane Hammoudi, editors, Proceedings of the 24th International Conference on Enterprise Information Systems, ICEIS, pages 374–383. SCITEPRESS, 2022. DOI: 10.5220/0011071500003179.
Maria Silva, Iago C. Chaves, and Javam C. Machado. LAGOON: achieving bounded individual fairness through classification frequency equalization. J. Braz. Comput. Soc., 30(1):238–251, 2024. DOI: 10.5753/JBCS.2024.3468.
Iago C. Chaves and Javam C. Machado. Differentially private group-by data releasing algorithm. In Proceedings of the 34th Brazilian Symposium on Databases, SBBD 2019, Fortaleza, CE, Brazil, October 7-10, 2019, pages 271–276. SBC, 2019. DOI: 10.5753/sbbd.2019.8835.
Iago C. Chaves, Antônio Diogo Forte Martins, Francisco D. B. S. Praciano, Felipe T. Brito, José Maria Monteiro, and Javam C. Machado. BPA: A multi-lingual sentiment analysis approach based on bilstm. In Joaquim Filipe, Michal Smialek, Alexander Brodsky, and Slimane Hammoudi, editors, Proceedings of the 24th International Conference on Enterprise Information Systems, ICEIS 2022, Online Streaming, April 25-27, 2022, Volume 1, pages 553–560. SCITEPRESS, 2022. DOI: 10.5220/0011071400003179.
Iago C. Chaves, Victor A. E. Farias, Amanda Perez, Diego Mesquita, and Javam C. Machado. Differentially Private Selection Using Smooth Sensitivity . In 2025 IEEE Symposium on Security and Privacy (SP), pages 3969–3987, Los Alamitos, CA, USA, May 2025. IEEE Computer Society. DOI: 10.1109/SP61157.2025.00216. URL [link].
L. Cabral, V. Farias, L. Sena, I. Chaves, J. P. Pordeus, J. P. Santiago, D. Sá, J. Machado, and J. P. Madeiro. An active learning approach for detecting customer induced damages in motherboards with deep neural networks. Learning & Nonlinear Models, 21(2):29–42, 2023. DOI: 10.21528/lnlm-vol21-no2-art3.
Victor A. E. de Farias, Felipe T. Brito, Cheryl J. Flynn, Javam C. Machado, Subhabrata Majumdar, and Divesh Srivastava. Local dampening: differential privacy for non-numeric queries via local sensitivity. VLDB J., 32(6):1191–1214, 2023. DOI: 10.1007/S00778-022-00774-W.
Maria de Lourdes Maia Silva, Iago Castro Chaves, and Javam de Castro Machado. Aplicação de top-k reverso com privacidade sobre os dados públicos de COVID-19 no estado do ceará. In Proceedings of the 35th Brazilian Symposium on Databases, SBBD 2020, Online, September 28 - October 1, 2020, pages 193–198. SBC, 2020. DOI: 10.5753/SBBD.2020.13640.
Sam Fletcher and Md Zahidul Islam. Differentially private random decision forests using smooth sensitivity. Expert Syst. Appl., 78:16–31, 2017. DOI: 10.1016/j.eswa.2017.01.034.
Fernando Dione S. Lima, Francisco Lucas Falcao Pereira, Iago C. Chaves, Javam C. Machado, and João Paulo Pordeus Gomes. Predicting the health degree of hard disk drives with asymmetric and ordinal deep neural models. IEEE Trans. Computers, 70 (2):188–198, 2021. DOI: 10.1109/TC.2020.2987018.
Maria de Lourdes M. Silva, Iago C. Chaves, and Javam C. Machado. Private reverse top-k algorithms applied on public data of covid-19 in the state of ceará. Journal of Information and Data Management, 12(5), Nov. 2021. DOI: 10.5753/jidm.2021.1941. URL [link].
Francisco Lucas Falcao Pereira, Iago Castro Chaves, João Paulo Pordeus Gomes, and Javam C. Machado. Using autoencoders for anomaly detection in hard disk drives. In 2020 International Joint Conference on Neural Networks, IJCNN 2020, Glasgow, United Kingdom, July 19-24, 2020, pages 1–7. IEEE, 2020. DOI: 10.1109/IJCNN48605.2020.9206689.
Lucas B. Sena, Francisco D. B. S. Praciano, Iago C. Chaves, Felipe T. Brito, Eduardo Rodrigues Duarte Neto, José Maria Monteiro, and Javam C. Machado. AUDIO-MC: A general framework for multi-context audio classification. In Joaquim Filipe, Michal Smialek, Alexander Brodsky, and Slimane Hammoudi, editors, Proceedings of the 24th International Conference on Enterprise Information Systems, ICEIS, pages 374–383. SCITEPRESS, 2022. DOI: 10.5220/0011071500003179.
Maria Silva, Iago C. Chaves, and Javam C. Machado. LAGOON: achieving bounded individual fairness through classification frequency equalization. J. Braz. Comput. Soc., 30(1):238–251, 2024. DOI: 10.5753/JBCS.2024.3468.
Iago C. Chaves and Javam C. Machado. Differentially private group-by data releasing algorithm. In Proceedings of the 34th Brazilian Symposium on Databases, SBBD 2019, Fortaleza, CE, Brazil, October 7-10, 2019, pages 271–276. SBC, 2019. DOI: 10.5753/sbbd.2019.8835.
Iago C. Chaves, Antônio Diogo Forte Martins, Francisco D. B. S. Praciano, Felipe T. Brito, José Maria Monteiro, and Javam C. Machado. BPA: A multi-lingual sentiment analysis approach based on bilstm. In Joaquim Filipe, Michal Smialek, Alexander Brodsky, and Slimane Hammoudi, editors, Proceedings of the 24th International Conference on Enterprise Information Systems, ICEIS 2022, Online Streaming, April 25-27, 2022, Volume 1, pages 553–560. SCITEPRESS, 2022. DOI: 10.5220/0011071400003179.
Iago C. Chaves, Victor A. E. Farias, Amanda Perez, Diego Mesquita, and Javam C. Machado. Differentially Private Selection Using Smooth Sensitivity . In 2025 IEEE Symposium on Security and Privacy (SP), pages 3969–3987, Los Alamitos, CA, USA, May 2025. IEEE Computer Society. DOI: 10.1109/SP61157.2025.00216. URL [link].
Publicado
29/09/2025
Como Citar
CHAVES, Iago; MACHADO, Javam.
Differentially Private Selection using Smooth Sensitivity. In: CONCURSO DE TESES E DISSERTAÇÕES (CTDBD) - SIMPÓSIO BRASILEIRO DE BANCO DE DADOS (SBBD), 40. , 2025, Fortaleza/CE.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 230-235.
DOI: https://doi.org/10.5753/sbbd_estendido.2025.247617.
