|M.Sc Student||Balter Dorit|
|Subject||Medical Records Confidentiality Problem|
|Department||Department 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
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.