SWI-Prolog + GMP rocks

SWI-Prolog provides unbounded integer and rational number arithmetic based on GMP library. Support comes out the box — no need to explicitly use a library in your code.

Even if you aren’t working with number ranges near the limits of most programming languages, unbounded integer support turns out to be fantastically useful for blazingly fast set operations by representing the sets as bit vectors. Given a mapping ix between set elements S and integers [0..n], we can assign any set an integer in the range [0..2**n], with each bit indicating whether an element is in the set, i.e  v(S) =  ∑ eS 2**ix(e). We can then use the bitwise arithmetic operators /\ and \/ to perform set-iintersection and set-union. The SWI-Prolog arithmetic function popcount/1 returns the cardinality of the set (corresponding the number of bits set).

This pattern is used in the blip simmatrix module. This allows for the computation of similarity scores between two features based on the attributes they share. E.g given a database with the predicate likes/2, e.g. between individuals and bands, we can determine the similarity of two individuals based on metrics like cosine similarity and Jacard coefficient.

Benchmarks to follow, but even on a 32 bit machine it appears possible to perform super-fast comparisons for databases of millions of facts utilizing 10k+ attributes (and thus integers in the range [0..2**10000]).

Advertisements
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: