Here's one of my own efforts on density-aware locality-sensitive hashing for embeddings. It uses k-means at one stage, I'll give this approach a shot.

https://dyf.io/