Publication:
Learning Markov Chain Models from sequential data under local differential privacy

dc.contributor.departmentDepartment of Computer Engineering
dc.contributor.departmentGraduate School of Sciences and Engineering
dc.contributor.kuauthorGüner, Efehan
dc.contributor.kuauthorGürsoy, Mehmet Emre
dc.contributor.schoolcollegeinstituteCollege of Engineering
dc.contributor.schoolcollegeinstituteGRADUATE SCHOOL OF SCIENCES AND ENGINEERING
dc.date.accessioned2024-12-29T09:38:50Z
dc.date.issued2024
dc.description.abstractMarkov chain models are frequently used in the analysis and modeling of sequential data such as location traces, time series, natural language, and speech. However, considering that many data sources are privacy-sensitive, it is imperative to design privacy-preserving methods for learning Markov models. In this paper, we propose Prima for learning discrete-time Markov chain models under local differential privacy (LDP), a state-of-the-art privacy standard. In Prima, each user locally encodes and perturbs their sequential record on their own device using LDP protocols. For this purpose, we adapt two bitvector-based LDP protocols (RAPPOR and OUE); and furthermore, we develop a novel extension of the GRR protocol called AdaGRR. We also propose to utilize custom privacy budget allocation strategies for perturbation, which enable uneven splitting of the privacy budget to better preserve utility in cases with uneven sequence lengths. On the server-side, Prima uses a novel algorithm for estimating Markov probabilities from perturbed data. We experimentally evaluate Prima using three real-world datasets, four utility metrics, and under various combinations of privacy budget and budget allocation strategies. Results show that Prima enables learning Markov chains under LDP with high utility and low error compared to Markov chains learned without privacy constraints.
dc.description.indexedbyWOS
dc.description.indexedbyScopus
dc.description.publisherscopeInternational
dc.description.sponsoredbyTubitakEuTÜBİTAK
dc.description.sponsorshipAcknowledgements. We gratefully acknowledge the support by The Scientific and Technological Research Council of Turkiye (TUBITAK) under project number 121E303.
dc.description.volume14345
dc.identifier.doi10.1007/978-3-031-51476-0_18
dc.identifier.eissn1611-3349
dc.identifier.isbn978-303151475-3
dc.identifier.issn0302-9745
dc.identifier.quartileQ4
dc.identifier.scopus2-s2.0-85182588570
dc.identifier.urihttps://doi.org/10.1007/978-3-031-51476-0_18
dc.identifier.urihttps://hdl.handle.net/20.500.14288/22806
dc.identifier.wos1207205300018
dc.keywordsLocal differential privacy
dc.keywordsMarkov chain models
dc.keywordsPrivacy
dc.keywordsSequential data
dc.language.isoeng
dc.publisherSpringer Science and Business Media Deutschland Gmbh
dc.relation.grantnoTürkiye Bilimsel ve Teknolojik Araştırma Kurumu, TÜBİTAK, (121E303)
dc.relation.ispartofLecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.subjectComputer science
dc.subjectInformation systems
dc.subjectTheory
dc.subjectMethods
dc.subjectTelecommunications
dc.titleLearning Markov Chain Models from sequential data under local differential privacy
dc.typeConference Proceeding
dspace.entity.typePublication
local.contributor.kuauthorGüner, Efehan
local.contributor.kuauthorGürsoy, Mehmet Emre
local.publication.orgunit1GRADUATE SCHOOL OF SCIENCES AND ENGINEERING
local.publication.orgunit1College of Engineering
local.publication.orgunit2Department of Computer Engineering
local.publication.orgunit2Graduate School of Sciences and Engineering
relation.isOrgUnitOfPublication89352e43-bf09-4ef4-82f6-6f9d0174ebae
relation.isOrgUnitOfPublication3fc31c89-e803-4eb1-af6b-6258bc42c3d8
relation.isOrgUnitOfPublication.latestForDiscovery89352e43-bf09-4ef4-82f6-6f9d0174ebae
relation.isParentOrgUnitOfPublication8e756b23-2d4a-4ce8-b1b3-62c794a8c164
relation.isParentOrgUnitOfPublication434c9663-2b11-4e66-9399-c863e2ebae43
relation.isParentOrgUnitOfPublication.latestForDiscovery8e756b23-2d4a-4ce8-b1b3-62c794a8c164

Files