M.Sc Thesis

M.Sc StudentBalter Dorit
SubjectMedical Records Confidentiality Problem
DepartmentDepartment of Computer Science
Supervisor PROFESSOR EMERITUS Shlomo Moran


Nowadays most medical institutes keep electronic medical records of patients. Sharing these records with other researchers such as statisticians and computer scientists is very important to the progress of medical science.  However, the information released to researchers should not compromise patients' privacy. One way of  insuring that the information shared does not reveal confidential  information on specific patients is generalizing fields' values so that the new information meets the safety criterion.

In this thesis we study the problem of generalizing a database so  that the generalized database does not compromise patients' privacy. We offer a formal framework for this problem and study its computational complexity. For each safety criterion we define an optimization problem. The set of such problems is a subset of a class of optimization problems we call we call Chain Product, denoted by ChP. The class of maximization  problems is denoted by ChPMAX and the class of minimization problems is denoted ChPMIN. We present problems in ChPMAX that  cannot be approximated within
for any unless P≠NP and within for any  unless ZPP≠NP where is the number of fields in the database.
We present problems in ChPMIN that cannot be approximated within
for any, unless . We present -approximation algorithms for all the problems in ChPMAX and ChPMIN.