K-repeating Substrings: a String-Algorithmic Approach to Privacy-Preserving Publishing of Textual Data

PACLIC 28 !658 K-repeating Substrings: a String-Algorithmic Approach to Privacy-Preserving Publishing of Textual Data Yusuke Matsubara and Kˆoiti Hasida Social ICT Research Center, School of Information Science and Technology, The University of Tokyo 7-3-1 Hongo, Bunkyo-ku, Tokyo, Japan matsubara@sict.i.u-tokyo.ac.jp, hasida.koiti@i.u-tokyo.ac.jp Abstract De-identifying textual data is an important task for publishing and sharing the data among researchers while protecting privacy of indi- viduals referenced therein. While supervised learning approaches are successfully applied to the task in the clinical domain, existing methods are hard to transfer to different do- mains and languages because they require a considerable cost and time for preparation of linguistic resources. This paper presents an efficient unsupervised algorithm to detect all substrings occurring less than k times in the input string, based on the assumption that such rare sequences are likely to contain sensitive information such as names of people and rare diseases that may identify individuals. The proposed algorithm works in asymptotically and empirically linear time against the input size when k is a constant. Empirical evalua- tion on the i2b2 (Informatics for Integrating Biology and Bedside) dataset shows the ef- fectiveness of the algorithm in comparison to baselines that use simple word frequencies. 1 Introduction The increasing amount of electronically available and searcheable texts poses an increasing need for privacy protection. Adversaries may extract previ- ously unconnected information about a person by aggregating different data sources. IDs such as so- cial security numbers in the United States are obvi- ous means to aggregate data sources, but full names, residential addresses, and other attributes about in- dividuals and their combinations may also work as pseudo identifiers from which one may be able to identify persons, or to raise the probability of suc- cessful identification (Sweeney, 2002)(Fung et al., 2010). While researchers and service providers wish to publish and share such textual data with the com- munity to help facilitate further research, it is costly to do so while preserving utility of non-sensitive part of the data. In response to the demand for efficient and ac- curate automatic methods to help removing sensi- tive material from textual data, the last decade has seen progress in automatic anonymization and de- identification of text (Liu, 2012; Fung et al., 2010; Uzuner et al., 2007). For example, health care indus- try puts efforts in utilizing electronic health record data that is accumulated daily while ensuring pa- tients’ privacy (Kushida et al., 2012; Meystre et al., 2010). Nevertheless, two major problems re- main unaddressed: 1) How to reduce human la- bor to prepare resources for automatic methods, in- cluding pattern-matching rules and training data for supervised-learning systems. 2) How to increase utility of published text by requiring less preprocess- ing of the input text. Our work explores aplicability of string algo- rithms into privacy-preserving publishing of textual data that reduce resource requirements. We pro- pose using new variations of maximum repeats algo- rithms to unsupervisedly suggest spans to be hidden. We argue that our approach brings new assets to pre- vious studies …

Content truncated to 500 words