3 ms·
Adaptive Range Filters
- daniel-levin 12y agoHow interesting. I would have thought such a common database operation (querying by ranges) would have been a better solved problem by now. Also, how come the author of the blog post writes O(k) instead of O(1) for constant time? Is it because 1 is as arbitrary a constant as any or is there some difference that I am not aware of? Link to the original paper [1] [1] http://www.vldb.org/pvldb/vol6/p1714-kossmann.pdf http://www.vldb.org/pvldb/vol6/p1714-kossmann.pdf
- nitayj 12y ago(I'm the author of the post) You're right in terms of big-O it's O(1), that is O(k) and O(1) mean the same thing. I said O(k) because BFs normally require multiple, but constant amount, of operations (hashes).