An Efficient Link Store

• Another web of data store that produces a subset of RDF/XML, Astoria, is from an unlikely source, Microsoft. Instead of a proprietary Semantic Web, Danny sees it as going to town with URIs and REST.


• Silverlight was the other surprising Microsoft development, nothing beats running code - except maybe browser-based dynamic code 2000 times faster. Applets are cool again.


• Some ideas for static triple indexing "Most mature triplestores also index a 4th query element ‘graph’ or ‘context’. I intend to support this query type without expanding the index by using a trick: In my triples format the fact that the subjects are auto-generated and local to the graph means I can choose them to be sequential and effectively re-use them as graph indexes..."


• Plugged In/Invisible Worlds/Tucana/Northrop/TKS/TMex/Kowari/Mulgara podcast (links to the Talis page).


• PAGE a distributed triple store using DHT and YARS (the original). It does seem to miss the DELIS work on P2P RDF which scaled up to 64 nodes.


• Haskell and the Faith of Programming Languages Phillip Wadler gives a rather brilliant talk on programming languages. Covers Haskell, Java generics, combining different typed languages (weak, strong, very strong) as well as monads and Links.

YARS Revenge

With little fanfare the folks at DERI have announced YARS2. I know of at least 4 next generation RDF stores (you know who you are) with a few others on the drawing board. Storing data is cool again.

To save disk space for the on-disk indices, we compress the individual blocks using Huffman coding. Depending on the data values and the sorting order of the index, we achieve a compression rate of ≈ 90%. Although compression has a marginal impact on performance, we deem that the benefits of saved disk space for large index files outweighs the slight performance dip.

Figure 4 shows the correspondence between block size and lookup time, and also shows the impact of Huffman coding on the lookup performance; block sizes are measured pre-compression. The average lookup time for a data file with 100k entries (random lookups for all subjects in the index) using a 64k block size is approximately 1.1 ms for the uncompressed and 1.4 ms for the compressed data file. For 90k random lookups over a 7 GB data file with 420 million synthetically generated triples (more on that dataset in Section 7), we achieve an average seek time of 23.5 ms.

I still wonder how the DERI guys can make the claim about it being their indexing scheme especially when Kowari was open sourced before YARS or the original paper came out. Maybe it's who publishes first? See Paul's previous discussion about it in 2005 (under the title "Indexing"). I mind that this hasn't been properly attributed as I'd like Paul and any others to get the attribution they deserve. On the other hand, I'm glad that people are taking this idea and running with it.

It's good to see that text searching on literals now seems like a standard feature too. They used a sparse index to create all 6 indices. They also hint out how reasoning is going to be performed by linking to, "Unifying Reasoning and Search to Web Scale", which suggests a tradeoff over time and trust.

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."

YARS

I thought I'd put a link in as well into my recent Graph and Triple Store to YARS. Lots of good stuff in there (small, HTTP interface, etc). Interestingly, they use JDBM which doesn't use NIO. I evaluated JDBM for blank node tracking but found that it was too slow for Kowari.