Parallel Metric Skip Lists and Nearest Neighbor Search

Xiangyun Ding, Rohin Garg, Yan Gu +1

The metric skip-list is a data structure designed for efficient nearest and $k$-nearest neighbor search in metric spaces. For many real-world datasets with reasonable distributions…