A Simple Linear Space Data Structure for ANN with Application in Differential Privacy
<|reference_start|>A Simple Linear Space Data Structure for ANN with Application in Differential Privacy: Locality Sensitive Filters are known for offering a quasi-linear space data structure with rigorous guarantees for the Approximate Near Neighbor search problem. Building on Locality Sensitive Filters, we derive a simple data structure for the Approximate Near Neighbor Counting problem under differential privacy. Moreover, we provide a simple analysis leveraging a connection with concomitant statistics and extreme value theory. Our approach achieves the same performance as the recent findings of Andoni et al. (NeurIPS 2023) but with a more straightforward method. As a side result, the paper provides a more compact description and analysis of Locality Sensitive Filters for Approximate Near Neighbor Search under inner product similarity, improving a previous result in Aum\"{u}ller et al. (TODS 2022).<|reference_end|>
@article{aumüller2024a,
    title={A Simple Linear Space Data Structure for ANN with Application in
  Differential Privacy},
    author={Martin Aum"uller, Fabrizio Boninsegna, Francesco Silvestri},
    journal={arXiv preprint arXiv:2409.07187},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.07187},
    primaryClass={cs.DS}
}