Fast Distance Oracles for Any Symmetric Norm
Authors: Yichuan Deng, Zhao Song, OMRI WEINSTEIN, Ruizhe Zhang
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main contribution is a fast (1 ε) distance oracle for any symmetric norm l. We propose a novel data structure with e O(n(d + mmc(l)2)) preprocessing time and space, and tq = e O(d + |S| mmc(l)2) query time... Our work strengthens and unifies a long line of work on metric embeddings and sketching, by presenting the first Distance Oracle for any symmetric norm, with nearly-optimal query and update times. |
| Researcher Affiliation | Collaboration | Yichuan Deng University of Science and Technology of China ethandeng02@gmail.com Zhao Song Adobe Research zsong@adobe.com Omri Weinstein The Hebrew University and Columbia University ow2161@columbia.edu Ruizhe Zhang The University of Texas at Austin ruizhe@utexas.edu |
| Pseudocode | Yes | Algorithm 1 Data structure for symmetric norm estimation: members, init, informal version of Algorithm 4 and Algorithm 5. Algorithm 2 Data structure for symmetric norm estimation: query, informal version of Algorithm 7. |
| Open Source Code | No | The paper is theoretical and does not report experimental results. The author checklist explicitly states '[N/A]' for questions regarding code availability and reproduction of experimental results, indicating no open-source code for the methodology is provided. |
| Open Datasets | No | The paper is theoretical and does not include experimental results on datasets. The author checklist explicitly states '[N/A]' for questions related to experiments and data, indicating no public datasets were used in the context of empirical validation. |
| Dataset Splits | No | The paper is theoretical and does not report experimental results. Therefore, it does not specify training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not report experimental results. The author checklist explicitly states '[N/A]' for questions related to experiments, indicating no hardware specifications were provided. |
| Software Dependencies | No | The paper is theoretical and does not report experimental results. The author checklist explicitly states '[N/A]' for questions related to experiments, indicating no software dependencies with version numbers were provided. |
| Experiment Setup | No | The paper is theoretical and does not report experimental results. The author checklist explicitly states '[N/A]' for questions related to experiments, indicating no experimental setup details were provided. |