Private Computation of the Longest Increasing Subsequence in Data Streams
Luca Bonomi, Li Xiong · 2015
In this paper, we study the problem of privately computing ordered statistics with the goal of monitoring sequential data streams. De-spite the broad series of techniques for time-series monitoring, only few works provide provable privacy guarantees employing the for-mal notion of differential privacy. While these solutions are well es-tablished, their focus is mostly limited to count based statistics (e.g. number of distinct elements, heavy hitters). In this paper, we con-sider a more general problem of privately computing the length of the longest increasing subsequence (LIS) in the data stream model. This important statistic can be used to detect trends in time-series data (e.g. finance) and perform approximate string matching in computational biology domains. Our proposed approaches employ the differential privacy notion which provides strong and provable privacy guarantees. Our solutions estimate the length of the LIS us-ing block decomposition and local approximation techniques. We provide a rigorous analysis to bound the approximation error of our algorithms in terms of privacy level and length of the stream. 1.