67 Bricks Blog

I’ve just contributed some code examples to the OpenHandle project.

OpenHandle exposes data from Handle, which is an interesting way of providing persistent digital identifiers for information, incorporating metadata. It’s used by systems such as DSpace and DOI.  In some ways, it’s a competitor to existing DNS-based ways of providing persistent URIs.

The code examples I’ve written demonstrate how to download OpenHandle data in F# and in C#. The C# implementation uses Linq.

Further to my previous post on bloom filters for efficient ontology lookup, I’ve made a simple implementation in F#. This is based on a Java implementation by Ian Clarke.

The neat thing about Ian’s implementation is its use of Random to extend the hashcode provided by the object being stored into a hash of arbitrary length, suitable for use by the bloom filter algorithm. This will reduce the quality of the hash, but for an arbitrary passed-in object, it’s hard to do better. (For a specific application, like storing ontology labels, it would be better to use a more specific algorithm such as a Jenkin’s Hash).

#light
open System
// Based on Java Bloom Filter implementation by Ian Clarke 
// http://locut.us/blog/2008/01/12/a-decent-stand-alone-java-bloom-filter-implementation/
type BloomFilter(bitArraySize : int, expectedElementCount : int) =
    let bitSet  = new System.Collections.BitArray(bitArraySize, false)
    let bitArraySize = bitArraySize
    let expectedElementCount = expectedElementCount
    let k = (int) (Math.Ceiling( ((double) bitArraySize / (double) expectedElementCount) * Math.Log(2.0) ))
    let bitSequence o =
        let r = new Random( hash o )
        Seq.init_infinite (fun n -> r.Next(bitArraySize))
    member b.expectedFalsePositiveProbability =
        Math.Pow((1.0 - Math.Exp( -((double) k) * (double) expectedElementCount / (double) bitArraySize)), (double) k)
    member b.add o =
        let sq = bitSequence o
        for x in 0 to k do bitSet.Set( Seq.hd sq , true)
    member b.addAll os = Seq.iter b.add os
    member b.clear = bitSet.SetAll(false)
    member b.contains o =
        let sq = bitSequence o
        let isSet n = bitSet.Get( Seq.hd sq )
        Seq.for_all isSet [0..k]
    member b.containsAll os = Seq.for_all b.contains os

Using F# makes the code slightly neater than Ian’s Java version - I’ve been able to factor out the hash code into a sequence supplied by the bitSequence function, and to collapse some of the for loops into operations over lists instead. But, the basic structure of the code is still very similar.

One of the problems with large ontologies such as SNOMED Clinical Terms is that they’re, well, large. So, it’s not typically possible to hold all of the ontology in memory at once, and queries against it require a database lookup. It’s possible to eliminate a number of database accesses, and thus speed up the query process, by using a Bloom filter.

A Bloom filter is a memory-efficient probabilistic data structure that lets you test whether a particular item is a member of a set. It may return false positives, but not false negatives. So, by adding all of the terms in your ontology to a Bloom filter, you can do a fast, in-memory check to see whether an entered term definitely doesn’t exist in your ontology. If the Bloom filter reports that the term does exist, then you can confirm with a slower file or database query for that term.

In an application where you expect to encounter many terms that aren’t in the ontology, such as automated metadata extraction from documents, and automated document classification, then this can potentially lead to large performance improvements.

I think there are also interesting possibilities in using Bloom filters in environments where storing a whole ontology isn’t feasible. For example, a JavaScript implementation of a Bloom filter, initialized with a few 100kb of data, could give a fairly high probability of testing accurately whether a particular term exists in an ontology of half-a-million terms.

It’s been a problem for a while that developers of web applications need to use a language like JavaScript on the web client, and another language like Java or C# or Python on the server. One popular attempt to fix this is Google’s GWT, and there have been other less mainstream options like ParenScript for Lisp and Links.

Now, Microsoft is launching another contender in the same space: Volta.

The post is somewhat obscure, but it’s essentially a beta version of a GWT competitor for .NET. You use annotations to mark chunks of code to be run on the client-side or server-side, and they’re compiled behind the scenes to JavaScript and deployed. There’s a debugger and profiler for the client-side code too.

An interesting feature about it, is that it works on MSIL (the .NET bytecode) rather than on the language syntax (as GWT does). Therefore, you should be able to use the more functional .NET languages with it - F#, for instance, is an ML implementation for .NET that appears well supported by MS. For that matter, C# 3 is already among the most functional mainstream languages.

The beta version is only available for Visual Studio.NET 2008 - currently available if you have an MSDN subscription, but not yet available for purchase.