Here is one of the recent advancements in performing similarity (including nearest neighbor) search on sparse high dimensional data using learned indices: https

Here is one of the recent advancements in performing similarity (including nearest neighbor) search on sparse high dimensional data using learned indices: https://arxiv.org/abs/2204.10028 https://arxiv.org/abs/2204.10028 The paper basically deals with the most adverse case but the approach should work in lower dimensions and in data with a non-uniform density distribution as well.