Collecting Partial Ordered Data With Local Differential Privacy

The partial ordered data is typically used to describe the order of some elements within a set, and it widely exists in various fields, such as clinical investigations, preference ranking and voting. However, the collection of partial ordered data poses critical privacy concerns about abusing records to infer individuals’ identities and preferences. To solve this problem, this paper proposes a distribution analysis method for partial ordered data with local differential privacy (LDP). The private information of partial ordered data includes whether an element is associated with a partial order relation and either a relation is preceding or succeeding. To preserve privacy, we perturb partial ordered data by randomly responding raw data or the data with mapped elements. This makes it impossible to distinguish whether any element has a partial order relationship with other elements and what kind of partial order relationship exists. To maintain the logicality of partial ordered data, we utilize the transitivity of partial orders to distinguish between direct and indirect orders in the perturbation. The inherent properties of partial orders are still satisfied after perturbation, which reduces the possibility of servers inferring the raw data through logical errors. Moreover, we theoretically analyze the error bound and prove the security of our work. Extensive experimental results on synthetic and real-world datasets demonstrate that our scheme achieves better utility than existing state-of-the-art approaches.