Priscilla Layton’s ancestors on another Web site:

The two pedigrees seamlessly linked:

Way, way back in the beginning, long before I’d ever even heard of this semantic web thing, I was planning on Genesis being nothing more than a really good record manager (like PAF, only usable).  This of course necessitated a database for storing all the data on the user’s computer.  I always assumed that one would be there, even though the whole concept later evolved.  It never occurred to me that a database wasn’t really neccessary anymore.

The flash of insight came yesterday morning as I was contemplating the next step in the replumbing/resurfacing effort.  I don’t recall the exact circumstances, but I do remember asking myself what would happen if I stopped caching data in the database.  Well, performance would go through the roof, for starters!  Startup and shutdown time would become negligible.  Disk space usage would fall dramatically.  And perhaps most important of all, I could take advantage of the OWL inference support in Jena!

This last point bears explanation.  A major part of this project is the ability for the user to indicate that Person A and Person B are in fact the same person.  This is done by creating an owl:sameAs relationship between the two.  Given this fact, Genesis should infer (using the OWL inference rules) that anything said about Person A is also true about Person B, and vice versa; the two are effectively one.  With some tricks this could efficiently be done using a database.  However, anything more complex would be next to impossible without bloating the size (and reducing the speed) of the database several orders of magnitude; all inferences would need to be precomputed each time new data is added to the database.  But inferences like this can be done in-memory (without a database) on demand!

Well there are obviously many positive aspects, but are there any downsides?  The most obvious drawback is the fact that it takes PGVAgent a long time to search each PhpGedView website one-by-one.  Having a database means that these search results can be cached for future searches.  If the database goes, so does the persistent caching.  In fact, this is why I had never considered dropping the database before.  Which begs the question, why did I suddenly start considering it now?

So what is that purpose?  To patch up all the independent genealogical trees out there into one distributed family tree (see the title of this blog, up there at the top of this page).  These improvements to search, particularly the Lucene index I mentioned yesterday, allow Genesis to take a given indiviudal and ask, “Are there any other individuals out there that are similar to this one?”  Using the index, a list of candidates in order of decreasing likelihood can be quickly returned, the most likely of which can be scrutinized in greater detail to find potential matches.  The user then has the ability to confirm, reject, or punt on suggested matches, implicitly forging links between hitherto independent genealogical trees.  These links will be stored directly on participating websites (PGV already provides a mechanism for this), as well as on third-party servers where websites do not provide a mechanism.

And what’s so great about that?  For users navigating participating websites through a web browser, they will see links on individual and family tree pages that lead to additional information and connections on other sites.  For those using Genesis or any other potential application that may come along (whether it be a client application, a website, a mashup, or what-have-you) users will be able to navigate a seamless family tree, with information coming from any number of sites and aggregated according to a user-specified trust policy.  That will be really neat, but when autonomous agents get to work on that network… well, you ain’t seen nothin’ yet.

Search in Genesis is a tricky problem.  In most search applications the entire corpus is available and indexed.  For example, when you do a search on Google, the search engine doesn’t go and find web pages that are related to your search.  The search engine already knows all the web pages that are out there (or at least all the web pages it has found), so it can quickly gather the most relevant results (supposedly) and present them, in order, almost immediately.  By contrast, Genesis may have some data cached and indexed from a previous search which it can show immediately, but there’s almost certainly a lot more out there, possibly better, which will take some time to locate.

Peer-to-peer applications such as Kazaa, Guntella, and the original Napster, face a similar problem.  Their approach, and the one used by Genesis until now, is to throw all the search results into one, big, scrollable list.  This doesn’t work very well for two main reasons:

1. The list can get really long, really fast, making it difficult to find what you’re looking for.  You could sort it, but…
2. When the list is sorted to help find something, new results continually displace old ones, forcing you to scroll down to find what you were looking at.  This is especially annoying if it happens just as you’re double-clicking on a result.

Most web search engines solve the first problem by sorting the results according to relevance and paging them.  Not only does this help the user find the best results quickly, but it is also much more efficient than showing all the results at once.  I want to do something similar with Genesis, but unfortunately I don’t know what the most relevant results are.  Also, the list is sorted by relevance, so won’t results be continually displaced if I try to do this dynamically?

Well, I may not know what the most relevant results are, but I do know what the most relevant results are at any given point in time, which suggests a novel approach.  Without going into too much depth, it operates a little something like this:

The moment the user clicks the “Search” button, Genesis gets to work.  It start by telling all the search agents (PGVAgent, for example) to start searching their respective domains.  The agents may take a while before they return any meaningful results, so Genesis performs a quick search over the local cache to see if it can give any results immediately.  If it finds any, it ranks them by relevance and displays them on the first page.  If there are more than 10 or so, it onlys shows the top 10 and puts links at the bottom of the page to access subsequent pages.  So far, nothing new.

While the agents continue to search in the background, the user looks over the first page of results and might go on to the second or even third page.  Genesis keeps track of which pages have been visited and doesn’t mess with them; if the user ever goes back to a page that has already been seen, the page will remain the same.  If, however, the user goes to a subsequent page and better results have become available through the work of the search agents in the background, then that page will show the current top results (excluding those that have already been seen).  Also, the user can at any time refresh the search, returning to the first page of results but with all the current results correctly ordered by relevance.

I don’t know of any other system that does this, but I’d be interested to learn of any that exist.  I’d also be interested in learning about any other, possibly-better solutions.  Any ideas?

I’ve decided to scrap the old search, however.  I was going to simply refactor it in the interest of getting on with the thesis, but it will take just as much work to create a new search that works much better.  Central to this new search is a recent addition to the plumbing: full-text search.  Over the last two days I integrated Lucene, a full-text search engine, into the project.  Lucene makes it unbelievably easy to index content and then search it.  And it’s incredibly fast (at both)!

As proof of concept, I refactored the PGV website list to use a Lucene index (instead of a SPARQL query with caching).  Those of you who have used the PGV Websites view before will know very well that it was very slow.  You will be pleased to learn that it now takes less than a second to populate the list, even the first time it is opened!  True, the PGV Websites view is really not all that important (or at least not yet; in the future you’ll go here to add/remove sites and enter account details for non-anonymous access).  But it does suggest that using Lucene indexes for search will be very successful.

Technorati Tags: Genesis, RDF, Jena, ARQ, SDB, NG4J, PGV, SPARQL, Lucene

So far I’ve only had one problem with Jena SDB, and it’s already been fixed.  The results of SPARQL queries were being collected into an array before being returned as a result set to my code.  This was a problem because Genesis relies on the results being streamed out as they are found.  I mentioned it on the jena-dev discussion group and within twenty-four hours the code was altered so that result sets now stream!  All I had to do was perform an update on the code and Genesis immediately began performing much better.  I love open source.  Thanks Andy!

In other news, I’m contemplating a resurfacing project to follow the replumbing effort, which will make Genesis look and act a lot more like a web browser than an IDE.  I’ll tell you more later.

Technorati Tags: Jena SDB, SPARQL, Genesis

When I embarked on this project, the plan was to use Jena and NG4J for the data plumbing.  When I started programming, however, I found it much easier to just write my own custom plumbing.  It wasn’t as complete or as powerful as Jena/NG4J, but at least I understood how it worked and it did exactly what I wanted.  As time wore on I began to feel the constraining effects of that decision, though.  I vowed to myself that I would eventually replace my code with Jena and NG4J.  Well, as I can’t make any more progress on the thesis until I’ve fixed this mess, the time has come.  So that’s what I’ve been doing.  What’s really sick and twisted is that the parts I’ve already upgraded are so much more elegant and clean now.  What was I thinking!?

So I’ve come full circle.  When I finish this huge refactoring effort, I’ll be able to leverage all the improvements that have been happening in Jena and NG4J lately.  Particularly exciting is the new Jena SDB, which is a very well written SPARQL to SQL translator.  The lack of such a translator is what originally motivated me to do my own custom plumbing.  It still lacks SQL FILTER evaluation, though, which perhaps can be my contribution to the community.  I’ve already extended it for named graphs.

In other news, the Genesis interface has really been grating on me lately.  It needs to be easier to use, fun, and, well, obvious.  Think Google.  We’ll see if I have enough self-restraint to leave it as is until I finish the thesis.  Then I can play all I want.

Technorati Tags: Genesis, Jena, NG4J, Jena SDB