Similarity search is the backbone of many large-scale applications in machine-learning, optimization, databases and computational geometry.
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.
The generality of our data structure allows to apply it as a black-box for data-driven learned symmetric distance metrics [1]} and in various optimization problems involving symmetric distances.
