Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/59462
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorMachado, Javam de Castro-
dc.contributor.authorFarias, Victor Aguiar Evangelista de-
dc.date.accessioned2021-07-12T13:55:26Z-
dc.date.available2021-07-12T13:55:26Z-
dc.date.issued2021-
dc.identifier.citationFARIAS, Victor Aguiar Evangelista de. Local dampening: differential privacy for non-numeric queries via local sensitivity. 2021. 100 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal do Ceará, Fortaleza, 2021.pt_BR
dc.identifier.urihttp://www.repositorio.ufc.br/handle/riufc/59462-
dc.description.abstractDifferential privacy is the state-of-the-art formal definition for data release under strong privacy guarantees. A variety of mechanisms has been proposed in the literature for releasing the output of numeric queries (e.g., the Laplace mechanism and smooth sensitivity mechanism). Those mechanisms guarantee different privacy by adding noise to the true query’s output. The amount of noise added is calibrated by the notions of global sensitivity and local sensitivity of the query that measure the impact of the addition or removal of an individual on the query’s output. Mechanisms that use local sensitivity add less noise and, consequently, have a more accurate answer. However, although there has been some work on generic mechanisms for releasing the output of non-numeric queries using global sensitivity (e.g., the Exponential mechanism), the literature lacks generic mechanisms for releasing the output of non-numeric queries using local sensitivity to reduce the noise in the query’s output. In this work, we remedy this shortcoming and present the local dampening mechanism. We adapt the notion of local sensitivity for the non-numeric setting and leverage it to design a generic non-numeric mechanism. We provide theoretical comparisons to the exponential mechanism and show under which conditions the local dampening mechanism is more accurate than the exponential mechanism. We illustrate the effectiveness of the local dampening mechanism by applying it to three diverse problems: (i) median selection. We report the median element in the database; (ii) Influential node analysis. Given an influence metric, we release the top-k most influential nodes while preserving the privacy of the relationship between nodes in the network; (iii) Decision tree induction. We provide a private adaptation to the ID3 algorithm to build decision trees from a given tabular dataset. Experimental evaluation shows that we can reduce the error for median selection application up to 18%, reduce the use of privacy budget by 2 to 4 orders of magnitude for influential node analysis application and increase accuracy up to 8% for decision tree induction when compared to global sensitivity based approaches.pt_BR
dc.language.isoenpt_BR
dc.subjectDifferential privacypt_BR
dc.subjectData anonymizationpt_BR
dc.subjectGraph analysispt_BR
dc.subjectDecision Treespt_BR
dc.titleLocal dampening: differential privacy for non-numeric queries via local sensitivitypt_BR
dc.typeTesept_BR
dc.description.abstract-ptbrPrivacidade diferencial é a definição formal do estado da arte para publicação de dados sob fortes garantias de privacidade. Uma variedade de mecanismos foram propostos na literatura para publicar as saídas de consultas numéricas (e.g., mecanismo de Laplace e o mecanismo smooth sensitivity). Esses mecanismos garantem a privacidade diferencial adicionando ruído na saída verdadeira da consulta. A quantidade de ruído adicionada é calibrada usando as noções de sensibilidade global e sensibilidade local da consulta que medem o impacto da adição ou remoção de um indivíduo na saída da consulta. Mecanismos numéricos que usam sensibilidade local adicionam menos ruído e, consequentemente, tem uma resposta mais acurada. Contudo, mesmo que também haja trabalhos para consultas não-numéricas usando sensibilidade global (e.g., mecanismo exponencial), a literatura carece de mecanismos genéricos para publicação de saídas não-numéricas que usem sensibilidade local para reduzir o ruído. Nesse trabalho, remediamos essa deficiência apresentando o mecanismo local dampening. Nós adaptamos a noção de sensibilidade local da configuração numérica para a configuração não-numérica e a usamos para criar um mecanismo não-numérico genérico. Nós provemos uma comparação teórica com o mecanismo exponencial e mostramos sob quais condições o mecanismo local dampening é mais acurado que o mecanismo exponencial. Nós ilustramos a efetividade do mecanismo local dampening aplicando-o em três problemas diversos: (i) Seleção de mediana. Nós reportamos o elemento mediano de um banco de dados; (ii) Análise de nós influentes. Dado uma métrica de influência, nós publicamos os top-k nós mais influentes da rede; (iii) Indução de árvores de decisão. Nós provemos uma adaptação privada para o algoritmo ID3 para construir árvores de decisão a partir de um dado tabular. Nossa avaliação experimental mostra que nós reduzimos o erro para a aplicação de seleção de mediana em até 18%, reduzimos o uso de orçamento de privacidade em 2 a 4 ordens de magnitude para a aplicação de análise de nós influentes e aumentamos a acurácia em até 8% para árvores a aplicação em indução de árvores de decisão quando comparado a abordagens que usam sensibilidade global.pt_BR
dc.title.enLocal dampening: differential privacy for non-numeric queries via local sensitivitypt_BR
Appears in Collections:DCOMP - Teses defendidas na UFC

Files in This Item:
File Description SizeFormat 
2021_tese_vaefarias.pdf1,12 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.