3 ms·

Fascinating! However two things are not clear: 1. How does marginalia build up the 10M bit vector for a site it has not seen before? 2. How do you do a cosine

by sireat 4y ago

Fascinating! However two things are not clear: 1. How does marginalia build up the 10M bit vector for a site it has not seen before? 2. How do you do a cosine similarity on a 64 bit bloom filter? ======== Example: https://explore2.marginalia.nu/search?domain=zombo.com https://explore2.marginalia.nu/search?domain=zombo.com Results seem quite good. 1. As I understand a 10M bit vector was created for zombo.com target, features were domains(10M of them), and values were booleans of whether site links to zombo.com . So on the fly to save space 10M bit vector was converted to a 64 bit bloom filter. So no false negatives and a certain percentage of false positives - so far so good. 2. Those 10M sites all have already precomputed bloom filters. If I understand correctly features would be 64 now and we calculate cosine similarity on those?

marginalia_nu 4y ago
1 -- I'm using the link graph for my search engine, which consists of the domains I've crawled, as well as domains I've not yet crawled. It's these linked-to, but not-yet-crawled domains it will discover. 2 -- The bloom filter is used to not calculate the cosine similarity directly. It's used to eliminate cases where the vectors are trivially orthogonal. It's this part in the code example if ((a.hash & b.hash) == 0) { return 0; } During vector construction, these bloom filters are calculated something like this hash = 0; if (values.size() < 128) { for (int v : values) { int bit = computeHash(v) % 64; hash |= 1 << bit; } } else { hash = ~0L; } If there is no overlapping bits between the bloom filters, it is possible to skip performing the calculation. If there are overlapping bits, the calculation needs to be performed. This only works for small vectors, but that is a relatively common case. For large vectors it's just a single logical AND and a comparison instruction, so the optimization is extremely cheap. I don't perform the calculation on the fly, but rather I've pre-calculated the similarity between each domain and store up to like 75 results given they have good similarity. This took about a day.

by sireat 4y ago

marginalia_nu 4y ago

1 -- I'm using the link graph for my search engine, which consists of the domains I've crawled, as well as domains I've not yet crawled. It's these linked-to, but not-yet-crawled domains it will discover. 2 -- The bloom filter is used to not calculate the cosine similarity directly. It's used to eliminate cases where the vectors are trivially orthogonal. It's this part in the code example if ((a.hash & b.hash) == 0) { return 0; } During vector construction, these bloom filters are calculated something like this hash = 0; if (values.size() < 128) { for (int v : values) { int bit = computeHash(v) % 64; hash |= 1 << bit; } } else { hash = ~0L; } If there is no overlapping bits between the bloom filters, it is possible to skip performing the calculation. If there are overlapping bits, the calculation needs to be performed. This only works for small vectors, but that is a relatively common case. For large vectors it's just a single logical AND and a comparison instruction, so the optimization is extremely cheap. I don't perform the calculation on the fly, but rather I've pre-calculated the similarity between each domain and store up to like 75 results given they have good similarity. This took about a day.