Differentially Private Approximate Near Neighbor Counting in High Dimensions
Authors: Alexandr Andoni, Piotr Indyk, Sepideh Mahabadi, Shyam Narayanan
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we present an efficient algorithm that offers a sweet spot between these two classes. The algorithm has an additive error that is an arbitrary small power of the data set size, depending on how fuzzy the range boundary is, as well as a small (1 + o(1)) multiplicative error. Crucially, the amount of noise added has no dependence on the dimension. Our main result is an efficient data structure that can approximate the number of near neighbors to any query point over Euclidean (ℓ2) space, with differential privacy (see Preliminaries for the formal of definition of privacy). We discuss extensions 1 4 more formally in Appendix C. |
| Researcher Affiliation | Collaboration | Alexandr Andoni Columbia University andoni@cs.columbia.edu Piotr Indyk MIT indyk@mit.edu Sepideh Mahabadi Microsoft Research smahabadi@microsoft.com Shyam Narayanan MIT shyamsn@mit.edu |
| Pseudocode | Yes | Algorithm 1 Data Structure. Algorithm 2 ANSWER(D, ηq, q, v): Answering a query |
| Open Source Code | No | The paper does not provide any statement about releasing source code for the described methodology, nor does it include links to a code repository. |
| Open Datasets | No | This is a theoretical paper focusing on algorithm design and analysis. It defines a general 'dataset X' but does not specify or provide access information for any publicly available or open dataset for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper focusing on algorithm design and analysis. It does not perform experiments that would require explicit training, validation, or test dataset splits. |
| Hardware Specification | No | The paper does not mention any specific hardware used to perform computations or run simulations. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers needed to replicate any aspect of the work. |
| Experiment Setup | No | This is a theoretical paper focusing on algorithm design and analysis. It does not describe an experimental setup with hyperparameters or system-level training settings. |