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

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.