본 논문은 차등적 개인정보 보호(DP) 커널 밀도 추정(KDE)을 위한 개선된 DP 데이터 구조를 제시합니다. 기존 연구보다 향상된 개인정보 보호-유용성 절충 및 효율성을 제공합니다. 특히, 유사도 함수 f(또는 DP KDE)와 개인 데이터 X ⊂ ℝᵈ가 주어졌을 때, 임의의 쿼리 y ∈ ℝᵈ에 대해 Σ_(x ∈ X) f(x, y)를 DP 방식으로 근사하는 수학적 문제를 연구합니다. 기존 최고 알고리즘(Backurs et al., ICLR 2024)의 노드 오염 균형 이진 트리를 개선하여 쿼리 시간을 α⁻¹log n 배 감소시키고, 근사 비율을 α에서 1로, 오류 의존성을 α⁻⁰⋅⁵ 배 감소시켰습니다. 기존 연구와 달리, 트리 구조를 다르게 구성하여 답을 log n 개의 숫자로 분할하는데, 각 숫자는 두 거리 값, 두 계산 값 및 y 자체의 스마트 조합입니다.
