Tissue Parade

This is just a quick note to let people who have expressed interest before in BioMANTA that the web site is now pretty much up-to-date with the latest papers and presentations (except for the InterOntology08 presentation in Japan next week). If we've sneezed and there was a Powerpoint slide it's there.

Do You Have an Internet Sized Problem?

Yahoo! Launches World's Largest Hadoop Production Application. This is mainly about Hadoop reaching a certain level of maturity.

The Webmap build starts with every Web page crawled by Yahoo! and produces a database of all known Web pages and sites on the internet and a vast array of data about every page and site. This derived data feeds the Machine Learned Ranking algorithms at the heart of Yahoo! Search.

Some Webmap size data:

* Number of links between pages in the index: roughly 1 trillion links
* Size of output: over 300 TB, compressed!
* Number of cores used to run a single Map-Reduce job: over 10,000
* Raw disk used in the production cluster: over 5 Petabytes

As described in the video, Webmap is the directed graph of the web and store the aggregate the metadata about the links. A lot of the code sounds like it is written in C++ (which is why there's the pipes API in Hadoop). According to the Hadoop mailing list, this means that Webmap is roughly equal to Google's scale.

Sorry

Maybe I'm in leftist, socialist heaven here but it does seem that most people were following the apology to the stolen generations. People were sitting in their cars listening to it rather than going to work. I liked the focus on how saying sorry is not about making you feel better it's about the person (or people in this case) you're saying sorry to and that you have to take the good with the bad about your country and make amends. There is also a sense that some sort of action will take place; with both sides of parliament working together. A lot of the Howard policies were designed as wedges to divide, so while I'm very skeptical, I'm a little bit hopeful that some inclusive politics will occur.

There were a couple of moments I thought worth mentioning from Rudd's speech:

After living in Alice Springs for a "few years", government policy changed and the young girl was handed over to the missions.

"The kids were simply told to line up in three lines ... those on the left were told they had become Catholics, those in the middle, Methodist and those on the right, Church of England," Mr Rudd said.

"That's how the complex questions of post-reformation theology were resolved in the Australian outback in the 1930s.

"It was as crude as that."

Mr Rudd said should there still be doubts, the historical record showed that between 1910 and 1970, between 10 and 30 per cent of indigenous children were forcibly taken from their mothers and fathers.

"As a result up to 50,000 children were forcibly taken from their families," he said.

Mr Rudd said one of the most notorious examples of this approach came from the Northern Territory Protector of Natives, who had stated: "Generally by the fifth and invariably by the sixth generation all native characteristics of the Australian Aborigine are eradicated. The problem of our half castes... will quickly be eliminated by the complete disappearance of the black race and the swift submergence of their progeny in the white."

"The 1970s is not exactly a point in remote antiquity," he said.

"There are still serving members in this parliament who were first elected to this place in the early 1970s.

It's been a long time, I remember Paul Keating's Redfern Park speech which was voted the number 3 speech after Martin Luther King and Jesus.

Concept Extractor

Last year ClearForest was bought by Reuters and Tim O'Reilly has covered the story of how the CEO of Reuters sees a Semantic future. This is one of those companies that I'd hope would become semantically enabled way back when. It would be good for other text mining companies like Autonomy and Inxight to jump on board too. The free web service provided "categorizes and links your document with entities (people, places, organizations, etc.), facts (person ‘x’ works for company ‘y’), and events (person ‘z’ was appointed chairman of company ‘y’ on date ‘x’). The metadata results are stored centrally and returned to you as industry-standard RDF constructs accompanied by a Globally Unique Identifier (GUID). Using the Calais GUID, any downstream consumer is able to retrieve this metadata via a simple call to Calais".

No Crappy Wrappers

Charles Petrie has an article called, "Is Semantic Web Technology Taking the Wrong Turn?". The author suggests that the current direction in Semantic Web development is leading it towards irrelevance. He notes its requirements and its attempt to provide ways to simplify and speed up tasks, such as integration, by an order of magnitude over existing technologies.

He sees a problem with how Semantic Web Technologies (SWTs) have typically been applied by adding layers alongside existing ones. This just increases "the number of interfaces and mediations required". Furthermore, most publications using SWTs talk about homogeneous environments - languages, ontologies, definitions are all constrained and any differences avoided. The other mistake highlighted is that the work has been divided into the usual architectural layers (persistence, processes, UI, etc) which has lead to each of these layers having their own Semantic Web layer added - creating "a disaster for software architects and engineers who must use the results from several communities in building software applications that are hosted and interconnected".

There are two obvious ways you could attack this argument. The first is that these types of constraints have been applied because of the immaturity of the underlying systems. It's hard to develop an integrated system in one go - dividing up these problems into their layers is obviously one way to make progress. There is also obvious infrastructure missing, not just better triple stores, but also ways to make sure you can reuse ontologies and processes. The other is that there are many examples of aligning ontologies, reusing them, and merging concepts from them; but it too is still in its infancy. Areas like data mining, that the Semantic Web could leverage, lacks mainstream use as well.

Straight ahead from here leads to more SWT languages, hard-to-integrate ontologies, and technology components such as libraries, RDF databases, and logic reasoners. Those who build real-world applications will have to integrate all those elements to use them holistically, thus leaving the integration problem unresolved. As this approach increases the effort required in every part of the software engineering life cycle, chances are that developers will adopt the SWT only for very specific areas and solutions, rather than for general use across all domains in which computing is applied.

He offers a possible solution in addressing the data and process heterogeneity by not restricting SWT to the edges of systems but for it to be applied throughout systems.

Rather than looking at SWT as interface-wrapping technology, it seems appropriate to make it the foundation for all aspects of information technology and scientific computing. In concrete terms, one way to eliminate mediations when crossing layers is to ensure that data objects are encoded in a single format (such as RDF) and not mapped between layers but rather handed over from layer to layer without change. This, in turn, would challenge the various technologies used for implementing these layers to become totally SWT aware.

I think that development goes through cycles of integration and separation but I do agree that if the Semantic Web is just a technology of wrappers it will fail.

Update: Much along similar lines is an article about Dieter Fensel, "Are Semantic Researchers Missing the Big Picture?", he says:

...we do a lot on research of apply[ing] in semantics to all aspects of Enterprise Application Integration where you integrate data, processes, and services (and not only web pages)...

Is the industry neglecting the greater overall goals of scalability for interoperability?

“No,” writes Fensel. “I think they are aware of [it]. For example, Michael Broodie, Scientific Director at Verizon, estimates that world wide around 1 trillion dollars are spent per annumn on application integration. The semantic web community (and not the industry) is mostly ignoring this area.”

I do like the cycle though, we've gone from an initial SEMANTIC web and criticism, to semantic WEB and now this criticism and back to highlighting semantic again.

50% Less Code or Your Money Back

Less that two weeks ago 0.5.3 of JRDF is released and now it's 0.5.4's turn.

This is mainly driven by making the fix to the bug in the btree (or Sesame's version) available.

It does however mean that the changes to the Resource API are made available more quickly. I remember looking at Jena's Resource and thinking it was bloated, confusing and rather poorly thought out from an efficiency point of view (holding onto all Graph and associated objects) but now I finally understand the positive effects it has on the code and I like it. JRDF's Resource sits on top of an RDF graph and automatically performs conversion from Java objects like URIs (which become URIReferences) and insert or removes them from the graph. It too has many methods that do the same thing but with different types. It's better than the recent changes to TripleFactory as it allows blank nodes too. JRDF's Graph implementation is no longer the heavy weight object it once was, it references the indexes and nodepool but no longer has any real control over them (this meant removing serialization).

Code becomes a lot smaller too, for example (the create call is URI.create):

Resource supplier = elementFactory.createResource();
supplier.addValue(create("urn:supplier"), "S1");
supplier.addValue(create("urn:name"), create("urn:Smith"));
supplier.addValue(create("urn:status"), 20);
supplier.addValue(create("urn:city"), "London", XSD.STRING);


Creates the triples:

_:1 urn:sno "sno"
_:1 urn:name urn:Smith
_:1 urn:status "20"^^xsd:int
_:1 urn:city "London"^^xsd:string


It used to be something like:

Resource supplier = elementFactory.createResource();
URIReference supplierPred = elementFactory.
createURIReference(create("urn:supplier"));
graph.add(supplier, supplierPred, "S1");
...


Scaling MapReduce

Before I started down using Hadoop I had to be roughly sure that it would scale. One of the pieces of evidence that convinced me was done by IBM in "Scalability of the Nutch Search Engine", they performed tests using real world systems and also modeled the architecture to verify it:

We observe...that the throughput, for a fixed data set size per back-end, increases with the number of back-ends.

We observe a generally good agreement between measurement and prediction for small number of back-end servers. The response time is essentially flat with the number of back-end servers, up to 500, 1000, and 2000 servers for data set sizes (per server) of 10 GB, 20 GB, and 40 GB respectively. The system is more scalable for larger data set
sizes because the work per back-end server per query increases.

They are able to service 1000+ nodes with a single server.

Kids Today

You tell them that there used to be monkey shaped pixels and they wouldn't believe you.

Nodes by Type

JRDF 0.5.3 released. This has a couple of bug fixes and features added. The find with no constraints (find(ANY_SUBJECT_NODE, ANY_PREDICATE_NODE, ANY_OBJECT_NODE)) has always been fast with the on disk version but not if it was constrained in anyway (a fixed subject for instance). This was because the wrong method on the btree was being called. This is a big improvement in performance obviously.

A cleanup on the Graph interface also occurred. There were all these methods like findUniquePredicates, getBlankNodes and getResources. There is now findNodes(NodeType) where NodeType is any of the positional (SPO) or value (Resource, URIRef, bnode, Literal) node types. This was able to be done because JRDF has a NodeTypePool where all nodes are in maps by their type. It is missing some types being supported but that should be done next release.

The other thing that was very annoying and now fixed was that a Literal or URI Reference had to be added via the GraphElementFactory before you could add it to the Graph. This only makes sense for blank nodes - other node types can just be re-localized (get their internal node id) each time. Handy for the amount of graph copying we have done lately.

There were some other boring changes like a bug fix to the RDF/XML parser and TripleImpl now being null proof.

Much more to do - haven't had a chance to cleanup the Molecule implementation or add the persistence support.

Solid State Drives

I was wondering what the effect would be on data structures and algorithms given the new features of SSD (solid state drives) - that is, drives with ten times the seek performance and improved read speeds. Desktop hard drives are about the same (18% slower) or beat SSDs in a straight line, sequential access, especially writes. In the short term, it looks like solid state drives biggest impact is likely to be in providing laptop drives the same performance as desktop ones.

A secondary short term impact may well be in providing another level of storage between spinning hard disks and other caches. This is mentioned in, "The five-minute rule twenty years later, and how flash memory changes the rules".

The name of their rule refers to the break-even interval between accesses. If a record (or page) is accessed more often, it should be kept in memory; otherwise, it should remain on disk and read when needed.

Not surprisingly, the optimal page size for B-tree indexes on modern high-bandwidth disks is much larger than traditional database systems have employed. The access time dominates for all small page sizes, such that additional byte transfer and thus additional utility are almost free. B-tree nodes of 256 KB are very near optimal...a traditional rotating hard disk, Table 3 indicates 337 seconds or just over 5 minutes.

Due to the lack of mechanical seeking and rotation, the transfer time dominates even for small pages. The optimal page size for B-trees on flash memory is 2 KB, much smaller than for traditional disk drives. In Table 3, the break-even interval for pages of 4 KB is 351 seconds.

Using O’Neil’s SB-trees, extents of 256 KB are the units of transfer between flash memory and disk, whereas pages of 4 KB are the unit of transfer between RAM and flash memory.

Mentions this paper, SB-Tree : An Index-Sequential Structure for High-Performance Sequential Access.

Via, Flash Memory and Databases.

Years to Days

Dr J Craig Venter – A DNA-Driven World (video)

For the past 15 years at ever faster rates we have been digitising biology. By that I mean going from the analog world of biology through DNA sequencing into the digital world of the computer. I also refer to this as reading the genetic code. The human genome is perhaps the best example of digitising biology. Our computer databases are growing faster per day then during the first 10 years of DNA sequencing. The databases have been filling even faster with the results of our global ocean sequencing project. As a result we have now over 10 million genes in the public databases, the majority of which have been contributed by my teams.

Instead of evolution happening only due to random mutations that survived selective pressure, we can see how by adding chromosomes to or exchanged between species, that thousands of changes could happen in an instant.

Now they can happen not just by random chance but by deliberate human design and selection. Human thought and design and specific selection is now replacing Darwinian evolution.

The biggest question in my mind is the one of scale. Last year we consumed more than 83 million barrels of oil per day or 30 billion barrels during the year. In addition we used over 3 billion tons of coal. These are mind boggling numbers and the only way that I can see replacing oil and coal is through a widely distributed system. If there were one million bio-refineries around the globe each one would still need to produce 17,000 liters per day.

He also talks about the rise of fundamentalism, that 25% of people in the US don't know that the Earth revolves around the Sun, half think people and dinosaurs co-existed and that 58% don't know how to calculate a 10% tip.

Who Killed Functional Programming?

MapReduce: A major step backwards. Two good responses, "The Great MapReduce Debate" and "Relational Database Experts Jump The MapReduce Shark":

MapReduce is not a data storage or management system — it’s an algorithmic technique for the distributed processing of large amounts of data.

MapReduce has the same relationship to RDBMSs as my motorcycle has to a snowplow — it’s a step backwards in snowplow technology if you look at it that way.

I don’t think the authors understand distributed processing and distributed file systems when they think reduce must rely on FTP. The Wikipedia article says “each [reduce] node is expected to report back periodically with completed work and status updates,” pretty much the opposite of the “pull” DeWitt and Stonebraker criticize.

It's a fairly specious argument that more features means better and the comparisons are not equivalent - it would be better compare BigTable or HBase with databases not MapReduce - and that'd be silly because these guys are column database proponents which is (roughly) the same as HBase/BigTable (they do say it lacks views but the idea used by Google is copying rather mutating). An example of using MapReduce to do indexing, is Nutch. The distributed filesystem is important and it should be clear by now, you'd hope, that storing the data is not the problem, processing it is.

These types of comparisons, "X does something Y doesn't therefore X is better", reminds me of "Who Killed the Electric Car?". One of the reasons the EV1 was said to have failed was because "lacking an engine, it saves the driver the cost of replacement parts, motor oil, filters, and spark plugs" (and more) - all those moving parts, that had to maintained were gone. How can you change gears if you don't have a gearbox?

Does that remind you of a database or other piece of software you use? Isn't the software industry just like the car industry? There appears to be market forces ensuring that things stay complicated and expensive to maintain.

Meanwhile, Google is getting on with it by providing services for terabytes of data (via Wired), "Building on the company's acquisition of the data visualization technology, Trendalyzer, from the oft-lauded, TED presenting Gapminder team, Google will also be offering algorithms for the examination and probing of the information. The new site will have YouTube-style annotating and commenting features."

Update: It's been noted that bet on cheap and rickety if it's 10 times better (also mentions hypertable) and that they're comments are not even wrong.

Update 2: Part of my rant was going to be the whole Apple designs things with the fewest stuff in them - that's what makes them the leader what they leave out. It's the same gist that I read at "Heavier than Air".

Fusion Beats Transistor

Why fusion? Answered fairly well in, Big machines for big questions. The presenter says that fusion has been outstripping CPU development, the triple product in fusion generation doubles every 1.8 years vs 2 years. They talk about ITER being the first fusion plant to generate more energy than put in. Worth the price of admission to the 21st century alone.

Ricky Gervais Explaining what's Wrong with Evolution

Link.

It's Fun to Pun

Punning was one thing that stumped me about OWL 1.1 last time I looked - mainly because I got confused between it and OWL Full. We did similar things for ontologies such as the Cell Type ontology (although the names were not the same in order to avoid moving out of DL land).

Recently, there's been a nice thread on "Xtreme Punning". I quite like Pat Hayes description of the situation:

Conventions which everyone has to agree to use: which will never happen. Names are cheap, but agreement on names is not cheap, so the fewer names we can get away with the better. The datatype example in my earlier email is a good example, IMO: all three uses are quite natural, and I wouldn't want to have to remember to distinguish xsd:number from rdfs:numberMapping from owl:numberThing.

Names can be freely used in ANY logical syntactic role, without ANY restrictions. EVERY occurrence of a name denotes the same thing. ALL names denote both a class and a property (and in CL a function; and in IKL, a proposition. No doubt other ideas can be incorporated.) ANYTHING can be an instance. Hence, any two legal sentences
(ontologies) can be simply concatenated and the result is still legal (no checking to be done when merging graphs) and meaningful. And it all works very simply, with a simple uniform semantics, which one can quickly get used to.

RDF in a...database?

This is has many similiarities in a recent conversion about the relational model and RDF, comes "Relational databases for storing and querying RDF":

Our work in this area, "Scalable Semantic Web Data Management Using Vertical Partitioning," appeared in the VLDB Conference in Vienna in September. It showed that using a column-oriented database, along with this property representation, allows us to overcome the overhead of representing NULLs, while providing two orders of magnitude better performance than the naive triples representation. This is particularly true when processing queries that must access many triples during execution (e.g., computing the number of books grouped by subject area or institution.) Of course, there is a fair amount of subtlety to getting good performance out of such a representation. Have a look at our conference paper for the details!

This paper and others was mentioned previously. This view, of property tables in column databases, is very similar to untyped relations.

JDBC for Hadoop

From the Hadoop mailing list:

The code is heavily inspired by the MapReduce layer for HBase and works much like it. However, it's mainly meant to be used for development, as in it's current form, but could potentially be of use for people that must keep their data in a relational database and cannot migrate to HBase for some reason (without all the benefits of HBase of course).

Download here

Intellij Under OSX

Seems that the bug with IntelliJ under OS X 10.5 (Leopard) (works for me now anyway) is fixed in currently nightly builds and will be in 7.0.3. More information here.

Wii!

I couldn't be more impressed. For the first time in about 25 years (I think the last time was H.E.R.O. for the Atari 2600) my mum has sat down (well stood up too) and played a computer game - Wii golf, bowling and tennis. While I remained victorious, it wasn't by much (especially golf). It reminded me of a description of the arrival of Pong by Nolan Bushnell where women would hustle men (induce to gamble over the outcome of a game) in bars.

Fat Controller

When does MapReduce make sense and what architecture is appropriate? I don't really know; wheras Tom has some ideas. I like the idea of MapReduce in the Google architecture (as cloned by Hadoop). I like the use of a distributed file system to evenly smear the data across the nodes in the cluster. However, these choices don't always seem appropriate.

The easiest and most obvious example where this causes a problem is that sometimes you want to ensure a single entry or exit in your system (when to start or stop). Another obvious example is where the overhead of network latency overwhelms your ability to parallelize the processing. More than that, it seems that if you can order things globally then the processing should be more efficient but it's unclear to me where the line is between that and the more distributed MapReduce processing (and whether adding that complexity is always worth it).

Google's third lecture (slides) answers some of the basic questions such as why use a distributed file system. It also lists decisions made such as read optimization, mutation handling (serializing writes and atomic appends), no caching (no need due to large file size), fewer but larger files (64MB chunks) and how the file handling is essentially garbage collection. They have implemented appends as it was a frequent operation. This is something that Hadoop has yet to do and can be an issue, especially for databases (which includes the requirements for appends and truncates attached to that issue).

There is obviously some adaption needed to alogirthms to run in a MapReduce cluster. Lecture 5 gives some examples of MapReduce algorithms. It includes a breadth first search of a graph and PageRank. Breadth first is chosen so there doesn't need to be any backtracking. For graph searching, they suggested creating an adjacency matrix - 1 indicating a link in the matrix and 0 indicating no link. To transfer it efficiently they use a sparse matrix (where you only record the links - very much like column databases of course). MapReduce is similar, with the processing split as a single row per page. For both of these process there is a non-MapReduce component. For example, in the PageRank algorithm a process exists to determine convergence of page values.