Adapting .js Bloom Filter

Report · Jan 16, 2013

I'm interested in playing around with Bloom filters. I found this javascript implementation https://github.com/jasondavies/bloomfilter.js/blob/master/bloomfilter.js, but my understanding of javascript is a bit minimal.

So I'm not quite sure what all the part about the different kinds of typed arrays supported by javascript and what would be the best thing to use in Flash. Would it be array, vector, object? Or perhaps it could be something that I wouldn't normally think of like a bitmapdata or byte array?

Also I'm often not sure which number types I should use to get the best results. I'm guessing generally uint to take advantage of the 32 bits.

Also I'm wondering a little about the FNV hashing function. Given that I'll be hashing strings I'm wondering how often I would need to use the masking like:

while (++i < n) {

c = v.charCodeAt(i);

if (d = c & 0xff000000) {

a ^= d >> 24;

a += (a << 1) + (a << 4) + (a << 7) + (a << 8) + (a << 24);

}

if (d = c & 0xff0000) {

a ^= d >> 16;

a += (a << 1) + (a << 4) + (a << 7) + (a << 8) + (a << 24);

}

if (d = c & 0xff00) {

a ^= d >> 8;

a += (a << 1) + (a << 4) + (a << 7) + (a << 8) + (a << 24);

}

a ^= c & 0xff;

a += (a << 1) + (a << 4) + (a << 7) + (a << 8) + (a << 24);

}

charCodeAt returns a number, but I'm thinking unicode only goes up to 2^16, right? So it seems like I wouldn't need to mask anything larger than 0xff00—saving two if/assignment blocks. (Of course the whole hashing part runs so quickly! So maybe that part won't matter.)

Well anyways, if somebody knows anything about implementing Bloom filter in actionscript that would be great.

Report · Jan 16, 2013

Try porting JS to PixelBender:

Firstly, if Bloom is an image filter then you want to do the processing in a PixelBender filter. PB is a language that is specifically created for image manipulation, you can write "kernals", and have them compile into a format for Flash Player. The advantage of PB over normal AS3 is that it runs VERY fast, on the CPU. So you can actually do cool things with it, without taking minutes to process. Just google for pixel bender examples in flash and you'll see its power. PB also has more number types (float, double) that you can't usually access in AS3.

See this - http://www.adobe.com/cfusion/exchange/index.cfm?event=productHome&exc=26&loc=en_us

Or if it doesnt work - http://active.tutsplus.com/tutorials/effects/create-custom-filters-using-the-pixel-bender-toolkit/

If porting JS to AS3:

Javascript doesnt support typed arrays - its just the usual Array class in AS3. Apart from that all JS numbers are doubles (Number class in AS3) I don't know what FNV hashing is, but the code should be exactly the same. Flash has a charCodeAt (its in the String class), so when porting just take care to add types to the vars (JS is completely untyped) like if it looks like an array use Array or Object (Array if numeric access, Object if they are using named properties), if numbers use Number or int, and if strings use String. Then just run/step through the code and see if its giving you similar results. Obviously if you have a JS debugger you can play JS code and test them both side by side, FireBug is cool for this - Install it in Firefox and you can place breakpoints in JS code and single step. So essentially when porting, run/step both pieces of code side-by-side and ensure you are getting the same results. If at any line you're not, then you know where to fix (somwhere around there).

http://getfirebug.com/javascript

https://addons.mozilla.org/en-us/firefox/addon/javascript-debugger/

Bloom Filters:

Does this do anything like what you need?

http://code.google.com/p/kode80as3experiments/source/browse/trunk/src/com/kode80/experiments/pvbloom...

http://kode80.com/2009/06/23/realtime-bloom-filter-in-as3/

Report · Jan 17, 2013

Thanks for that. But no it isn't about graphics. It is a data structure that is used to test if a candidate element is a member of a set or not.

http://en.wikipedia.org/wiki/Bloom_filter

It is supposed to be very space effecient and fast (Running in O(k) time, relative to the number of hashing functions used). If done correctly it doesn't have false negatives, but may give false positives (with a rate that can be controlled, but not completely eliminated). It can be used to prevent more costly activities like a database lookup or such when you know that the result will be "No."

An example I've seen is for safe URL browsing. The blacklist of "forbidden/dangerous" sites could be very large (I've heard average 80 charcters per URL, many thousands of sites/pages.) An array of those values could take a lot of storage room. But a Bloom filter would be much smaller. The request would come "Is suchandsuch.com/possibley_dangerous/ on the list?" And the filter could say either "For sure not. Proceed." or "It looks like it is on the list. Do some further testing by querying a remote database." Or something like that.

I also found a reference to someone who wrote a Bloom filter that allowed for spell checking at a rate of around 13,000 words per second.

The FNV thing is a non-cryptographic-strength but quick and appropriate hashing function. That part I have been able to adapt from the original and it seems to be working. I'm just not sure I understand why the first two "masking/assignment" conditional blocks are in there.

If I understand correct, then this part (where c is the value returned by getCharAt()

if (d = c & 0xff000000) {

a ^= d >> 24;

a += (a << 1) + (a << 4) + (a << 7) + (a << 8) + (a << 24);

}

is checking to see if c has any turned on bits in the left-most 8 bits and if so assinging the last 8 bits to d and then doing some processing on them. Right? But how is getCharAt() ever going to get bits all the way "over there." True it returns a number which can use that many bits, but if all unicode fits into 0xffff when will they ever be used? Could this be an endian thing?

Overall it might not really be a usefull or effecient thing to do in actionscript, but I just want to play around with it and see what might come up.

Thanks for the suggestions on javascript debuggers.