K-means clustering has been heavily employed to mine valuable insights from interval data. Nevertheless, serious privacy leakage concerns are stumbling blocks impeding its widespread application. To quantify the privacy of small and large-scale interval data, we introduce two notions of α-Condensed Local Differential Privacy and ϵ-Local Differential Privacy, and propose two distance-aware perturbation mechanisms of α-exponential and square wave mechanisms. Rigorous theoretical analysis proves that our proposed mechanisms satisfy these two privacy notions. The experimental results built on multiple synthesized and real datasets show that our proposed mechanisms can provide more accurate clustering results than prior work, such as Randomized Response, Generalized Randomized Response, and Optimized Local Hash.

Social data outsourcing is an emerging paradigm for effective and efficient access to the social data. In such a system, a third-party Social Data Provider (SDP) purchases social network datasets from Online Social Network (OSN) operators and then resells them to data consumers who can be any individuals or entities desiring social data through query interfaces. The SDP cannot be fully trusted and may return forged or incomplete query results to data consumers for various reasons, e.g., in favor of the businesses willing to pay. In this paper, we initiate the study on verifiable query processing over outsourced social graph whereby a data consumer can verify both the integrity and completeness of any query result returned by an untrusted SDP. We propose three schemes for single-attribute queries and another scheme for multi-attribute queries over outsourced social data. The four schemes all require the OSN provider to generate some cryptographic auxiliary information, based on which the SDP can construct a verification object to allow the data consumer to verify the integrity and completeness of the query result. They, however, differ in how the auxiliary information is generated and how the verification object is constructed and verified. Detailed analysis and extensive experiments using a real Twitter dataset confirm the efficacy and efficiency of the proposed schemes.