U-DPAP: Utility-aware Efficient Range Counting on Privacy-preserving Spatial Data Federation

Range counting is a fundamental operation in spatial data applications. There is a growing demand to facilitate this operation over a data federation, where spatial data are separately held by multiple data providers (a.k.a., data silos). Most existing data federation schemes employ Secure Multiparty Computation (SMC) to protect privacy, but this approach is computationally expensive and leads to high latency. Consequently, private data federations are often impractical for typical database workloads.This challenge highlights the need for a private data federation scheme capable of providing fast and accurate query responses while maintaining strong privacy. To address this issue, we propose U-DPAP, a utility-aware efficient privacy-preserving method. It is the first scheme to exclusively use differential privacy for privacy protection in spatial data federation, without employing SMC. Moreover, it combines approximate query processing to further enhance efficiency. Our experimental results indicate that a straightforward combination of the two techniques results in unacceptable impacts on data utility. Thus, we design two novel algorithms: one to make differential privacy practical by optimizing the privacy-utility trade-off, and another to address the efficiency-utility trade-off in approximate query processing. The grouping-based perturbation algorithm reduces noise by grouping similar data and applying noise to the groups. The representative data silos selection algorithm minimizes approximate error by selecting representative silos using the similarity between data silos. We rigorously prove the privacy guarantees of U-DPAP. Moreover, experimental results demonstrate that U-DPAP enhances data utility by an order of magnitude while maintaining high communication efficiency.