I was reading about the semantic search and how do many indexes performs it on a vector space. However, I could not understand why no one uses segment trees for this searching because, For example, we may have a large number of points in space at certain distances from a central reference/origin point. Suppose we have to lookup the points which are in a certain range of distances from our origin. An ordinary lookup table would require a linear scan over all the possible points or all possible distances (think hash-maps). Segment Trees lets us achieve this in logarithmic time with much less space cost.
If anyone knows the answer please let me know. current search time complexity is O(k+m) for FAISS index k being the number of clusters and m being the closest m clusters among k clusters. We can easily reduce this time complexity from O(k+m) to (log k).
Looking forward to responses. Thanks!