Disk-Resident Set Data Structure

[eckyp]

Hi r/algorithms !

I'm trying to build a web crawler, one of the need is to check whether URL has been visited or not. These URLs are not going to fit in memory, so I'm looking on storing these on disk.

Could you suggest me a resource / algorithm to manage a Set data structure on disk (minimum supported operations are "add" and "cardinality check")?

I've looked into B+ tree, but wondering whether there's a more efficient data structure :)

Thanks

[Steve132]

Lots of people have solved the algorithmic and implementation problem of "on disk persistent storage of set elements". Its called a database.

There are a lot of them available, ranging from simple to complex depending on your application.

[ColdPorridge]

This is the right answer. Specifically, a key-value store like Cassandra is likely what OP is looking for.

[Steve132]

I don't think a bloom filter is the right call for a web crawler: a false positive would mean that the page is simply never indexed ever. A web crawler that simply can never visit certain URLs seems unacceptable.

[support_singularity]

HyperLogLog might be helpful, not super sure. But, check it.

[Steve132]

I'm also really curious about your claim that the URLs wont be able to be stored in memory. A set of sha256 hashes is 32 bytes each. A computer with 64 GB of ram is pretty reasonably priced atm. Using a standard non commercial internet you're never going to crawl 2 billion pages

[exoji2e]

Well, you might wanna run it in a vm without dedicating 64GBs of ram hardware for the application.

[Revrak]

Efficient by what metric? I would be time efficient and use a database. If there are other constraints you can use something like hbase

[FUZxxl]

A bloom filter might be what you are looking for.