The initial task can be described like this:I have a requirement to deduplicate HUGE list(potentially billions of items) without storing the original items - it's simply unaffordableAll I need to know is answer to the question Has my system ever seen this element before?The most close data structure I was able to find so far is a bloom filter, but it has false positives which better to avoid in my task as it results in data lossFor example providing I account to store at least 2^32 items, with positive error rate of just 1%(which means 1% of all urls won't be visited) I would need at leastn = 4,294,967,296, p = 0.01 (1 in 100)  m = 41,167,512,262 (4.79GB), k = 74.79GB of memory...The task itself is a high scale web crawler, so I need to keep track of already visited urls(or sha1 hashes of this urls)Any help is welcomeThanks!
Memory efficient structure for membership checking without false positive
bigdata;scalability
For web crawler scale why not use a distributed database like Apache Cassandra? Lookups on indexes are efficient and no false positives.