  Join size estimation on sensitive data poses a risk of privacy leakage. Local
differential privacy (LDP) is a solution to preserve privacy while collecting
sensitive data, but it introduces significant noise when dealing with sensitive
join attributes that have large domains. Employing probabilistic structures
such as sketches is a way to handle large domains, but it leads to
hash-collision errors. To achieve accurate estimations, it is necessary to
reduce both the noise error and hash-collision error. To tackle the noise error
caused by protecting sensitive join values with large domains, we introduce a
novel algorithm called LDPJoinSketch for sketch-based join size estimation
under LDP. Additionally, to address the inherent hash-collision errors in
sketches under LDP, we propose an enhanced method called LDPJoinSketch+. It
utilizes a frequency-aware perturbation mechanism that effectively separates
high-frequency and low-frequency items without compromising privacy. The
proposed methods satisfy LDP, and the estimation error is bounded. Experimental
results show that our method outperforms existing methods, effectively
enhancing the accuracy of join size estimation under LDP.
