RETE Rebuked

A recent blog I started reading after criticizing SPARQL. This time its criticizing an entry Paul made about the scalability of the RETE algorithm: "I am a bit confused by the statement that RETE does not scale. This is contrary to a mountain of papers by researchers and developers around the world. From the paragraph, a couple of things come to mind. "(loading indexes) does not need to be done often" tells me the author doesn't understand the purpose and goal of RETE. RETE was designed to solve machine learning problems where data changes rapidly and reasoning is a continuous process. What the author wants is something closer to BitMap indexes used in OLAP products."

A lot of the points raised, like RETE being for changing data, are mentioned in a previous post under Meeting. Drools was chosen as a starting to point to see what kind of system needed to be developed in Kowari.

Also mentioned, bitmap indexing: "Given Tucana is indexing everything, they might as well adapt Bitmap indexing and get better than linear performance. The problem described by the blog is a well understood problem in the OLAP world."

An previous entry, "Relational theory, RETE and Derby" points to some interesting articles about bitmap indexes (available in Oracle 9) and high scalability requirements: "In a large financial institution like a mutual fund company, they may have 1-20 million customers. If each customer has an average of 20-30 positions (aka specific holding of an equity) that means the potential dataset for firm wide compliance rule could involve 20million+ rows. Doing this within 2-5 seconds is rather hard, so it requires using lots of different techniques. In the extreme cases, a company might have 20 million accounts, which means the potential dataset is 600 million rows."

From the OTN article: "B-tree indexes are usually used when columns are unique or near unique; bitmap indexes should be used, or at least considered, in all other cases. While you would not generally use a b-tree index when retrieving 40 percent of the rows of a table, a bitmap index is often still faster than doing a full table scan. This is seemingly in violation of the 80/20 rule, which is to generally use an index when retrieving 20 percent or less of the rows and do a full table scan when retrieving more. Bitmap indexes are smaller and work differently from the 80/20 rule. You can effectively use bitmap indexes even when retrieving large percentages (20 to 80 percent) of a table. Bitmaps can also be used to retrieve conditions based on nulls (since nulls are also indexed) and for "not equal" conditions."

It would appear that this would be suitable for predicate indexation but not generally as both subjects and objects are near unique.

JRDF for Learning

In the past I used another project to practically use trendy new things like patterns, XML, Swing, etc. Similarly, I'm going to use JRDF for the same purpose. Kowari is a bit too big for things like going over to Java 1.5, IoC, mocking (real unit tests), lock free alogirthms (including B-Trees) and a few other things that I want to try. I'm not sure it's possible to have a system that doesn't have transactions but it would be interesting to find out. So basically this is just to let people know to expect some changes in JRDF.

Practically, it might mean an RDF/XML based pull parser, persistent JRDF, and more interesting APIs. I'm convinced that developing web services is too expensive and may implode under its own weight - so maybe something based on netKernel or a REST based framework would be a good idea. At the moment I'm just using it to see how much I can get out of IntelliJ.

Comparing YARS and Kowari

Cold, Mastering OWL, Scalability, Indexing "There are two differences in their implementation to our own. The first is that they used B-trees rather than the AVL trees that Kowari uses. That is not a significant difference, and I blogged about this several times before. The main advantage of the AVL tree is that they are cheaper to write to the structure than B-trees are, though a little slower to read. They also pointed out that they wanted to use an existing library for the index, and while B-tree libraries are common, we never found a completely working AVL tree library (deletions were always buggy).

The second difference is a set of special statements which count the number of triples in parts of each of the indexes. This is certainly novel, but not an approach I would use. I believe that counting is still very efficient in Kowari (O(log(n)), and the space overhead they incurred would seem prohibitive. More importantly, writing is always the slowest operation, and their system would incur a large writing penalty for using this scheme."