3 ms·
I was trying to make the point that the dominant factor becomes linear instead of logarithmic, but more accurately it's O(S log N) = O(N log N) because S is pro
by jbellis 2y ago
I was trying to make the point that the dominant factor becomes linear instead of logarithmic, but more accurately it's O(S log N) = O(N log N) because S is proportional to N.
- deleted 2y ago[deleted]
- HammadB 2y agoSure, I see. I think this is an area where complexity analysis doesn’t lead to useful information. To be more correct it’s O(N/C log C) where C is the capacity of a segment. In this case you can ignore 1/C and log C as constant. So now sure, you actually just have O(N). But this is not super useful as it says that a segmented hnsw approach and brute force approach are the same - when this is really not the case in practice. Also O(N log N) > O(N) so I’m not sure why we would ever do anything with segmentation according to that analysis if it were correct.
- jbellis 2y ago> I’m not sure why we would ever do anything with segmentation according to that analysis if it were correct. What's your alternative when you can't build an index larger than C?
- HammadB 2y agoIf segmented hsnw indices were O(N log N) - it would make no sense to build the index at all - brute force would be better as O(N log N) > O(N)