Graph Databases

For a small work project I have been evaluating a variety of graph databases so that I can efficiently model entity resolution. SQL joins are so boring.

Why Graph Database?

On the face of it, storing and modeling relationships between data is what Relational databases are all about, so why would you need a database that specifically models graph structures? 

One compelling argument lies in the way you query relational data versus the way you query graph data. SQL works well when querying data with well defined, node-to-node relationships. For example if you have a table of employees, it is very easy to create a JOIN that will allow you to retrieve an employee and their manager, joined on a manager serial number field. This becomes much more difficult if you want to do something as simple as retrieving an employee's manager chain (especially in large companies). In SQL this would require either a series of queries, or essentially a recursive JOIN. It is possible to do, but messy and potentially slow.

This becomes even more problematic as you model domains where each node has many relationships with many different types of nodes. Take, for example, an online store that has social data connected to it. You would have customers, their relationships with each other, and their purchases and relationships between their purchases (such as X items were bought together). Using this data you could provide personalized suggestions, such as "many of your friends have bought this item recently, and also bought it with this other item". In SQL you would need to union multiple joins against the customer's friends, their purchases and between the purchases.

With a graph-type query, it becomes much simpler, where you start at the customer node, fan out to friend nodes of a certain depth (friends or friends-of-friends) and count up distinct sets of recent purchases.

It is certainly possible to fit a graph query language on top of a relational datastore (such as SPARQL/RDF on top of IBM DB2 or Oracle). Sometimes, however, picking a dedicated tool for the job works better.

Experiments

In typical developer fashion, I used a project as an excuse to play with new tools. In the process I ended up trying 3 different databases that are compatible with Java: OrientDB with the TinkerPop Blueprints API, Neo4j using both the web and embedded java api, and Apache Jena's implementation of RDF.

OrientDB with TinkerPop Blueprints 

Links - OrientDB , Blueprints Plugin

OrientDB is a fantastic document store that is especially notable for its embedded Java implementation. If you ever need to store and query data in a semi-structured way for an application in-memory or with a local cache, OrientDB is a great way to go.

When it comes to graph storage, things get a little bit more complicated. It is very possible to use the native OrientDB API to do graph storage, but using this approach makes querying data a little more difficult. To get around this I tried using the Blueprints plugin for OrientDB to allow me to use a more standardized wrapper for creating and querying nodes in the graph. The idea behind this was that I could switch data-stores if OrientDB was not performant enough. Unfortunately the Bluepages plugin for OrientDB is not yet very stable and this made it very difficult to do things such as indexing nodes based on an attribute. This led to some very ugly code and use of an external index using Redis.

So I gave up using OrientDB.

Neo4j

Links - Neo4j , Cypher

Neo4j is a popular graph database that benefits from a relatively expansive query language called Cypher that allows for some very complex queries and update operations. Neo4j can be used as a standalone server or as an embedded database within a Java application.

When running as a standalone database server, Neo4j provides a very clean REST api for adding, querying and updating nodes. Unfortunately there are no wrapper APIs written to allow a Java application to access the database remotely, you must write your own. This is especially problematic since there is no option to use a binary remote API, so communication is slower than it needs to be and more verbose.

Because of this limitation, I ended up using Neo4j as an embedded database within my application. In order to simplify querying, I used a version 2.0 preview release so that I could assign labels to nodes and query them by their label (or "class" essentially). Everything seemed to go very smoothly and writing queries in Cypher proved relatively easy.

Unfortunately I ran into some issues with stability in the multi-threaded environment of my application. Eventually I was able to iron these out by upgrading to the next preview milestone and locking down all updates and queries to be single threaded. This made high-volume updates very slow, but I was able to mitigate this by surrounding the graph storage with a redis cache that would allow me to identify data changes and only perform updates on change.

Apache Jena RDF

Links - Jena , RDF , SPARQL

Apache Jena is a Java API that supports editing of Resource Description Frameworks (RDF) and graph queries using SPARQL. RDF is a format for describing relationships between objects rooted in Semantic Web data models. The native format of RDF is XML, so Jena supports reading and writing to XML RDF files. In addition to storing to XML files, Jena supports storing to a native Triple store called TDB as well as to relational databases using.

RDF makes heavy use of URIs/namespaces for identifying nodes. This provides good support for classifying nodes into different types and makes relationships between nodes very explicit and self-documenting. The typing system in RDF consequently feels much more mature than those in Blueprints or Cypher. Another benefit from the use of URIs is that it is very easy to create unique nodes, and providing additional data on the node is as simple as providing a REST service that uses the same URI structure.

For my initial implementation I used Jena with TDB for storage, as it allowed me to quickly prototype my data model. TDB supports multi-threaded applications through the use of thread-local transactions, but because of the complexity of the thread model of my application I ended up synchronizing a singleton, so its a bit slow. 

The query language for Jena is SPARQL 1.1 (as of writing). From a pure query standpoint, SPARQL is relatively robust and very well defined (it is a W3C standard). Unfortunately from a performance standpoint, the complex queries I tried to perform proved difficult to optimize because the syntax abstracts a lot of the graph-walking process. Where an equivalent Cypher query would take seconds, a SPARQL query would take many many minutes, or I would give up and kill the query before any result was returned.

Conclusions

After more testing and trying the latest Milestone 6 of Neo4j, it looks like Neo4j is the winner. I attempted some larger scale testing in TDB with SPARQL and it turns out that performance is much worse than I had iniitially thought. Trying to formulate the same queries in SPARQL as Cypher can sometimes turn out to be exponentially worse in SPARQL. Cypher is a bit less abstract in the query structure so it allows you to avoid these pitfalls. This turned out to be a difference between a matter of seconds in Cypher and a matter of hours in SPARQL.

So with Neo4j more stable (thanks to avoiding parallel updates) Neo4j is now the best option for me.

SketchPad Progress

A (sort of) truss diagram drawn in SketchPad.

A lot of work has been completed on the SketchPad project. Here is a quick summary:

Porting Paleo to Android

1. Ported basic classes by removing external dependencies on most of java.awt.* . This involved moving source code from OpenJDK in to replace most of the geometry classes, such as Shape, and all of java.awt.geom.* .
2. Ported shape drawing code to android. This means drawing java.awt.Shape subclasses in an android.graphics.Canvas context. Turned out all you need is to get the PathIterator of the Shape. This code is now in edu.tamu.awt.ShapePainter.
3. Downgraded base java requirements by adding array copy features to the java.util.Arrays class. This allows for downgrading the required level of the android api below 2.2.
4. Removed unneeded classes in dependencies and all Ecology Lab simpl serialization dependencies.
5. Added new serialization code for the core.sketch classes based on Simple XML (simple.sourceforge.net)

Created Android Sketch Application

1. Supports one finger drawing with a color picker.
2. Allows saving files to srlweb for storage and analysis
3. Allows loading files from srlweb

Screen Shots

Shape recognition and beautification at work. Currently it is on by default

A drawing!

Visgo Project Report 2

What we have accomplished in last month:

Related Work - what other people have done to address this problem?

Design - what design we have to address this?

Implementation -

The worst user interface I have used.

One of the worst user interfaces I have used is that of the 3d modeling program, Blender 3d. I absolutely love using the program, but only because I have spent a long time learning its peculiarities, fighting it and looking up instructions.

(Blender 3d 2.5 beta default UI layout)

Non Standard Interface

The first thing you notice when starting up Blender is how completely different the interface looks than any other program on your operating system, whether Mac, Windows or Linux. It is not entirely clear if there was one original inspiration for the UI widgets used by Blender, but it is clear that they were built from the ground up for the program. This leads to behavior such as a typical horizontal spinner UI elements that requires the user to Shift-click on it to be directly

editable. Though this Shift-click to edit behavior is consistent across most of the interface

widgets, it does not follow any established widget interaction conventions and thus is not

intuitive even to people who are used typical window based GUIs.

(An example of a Shift-Click spinner. In previous versions of the program shift-clicking would be the only way to be able type it a specific value)

Speaking of windows, Blender throws out the entire window convention, opting for a single window with re-arrangeable sub panels. It is easy to understand why you would not want to have to contend with layers of floating windows cluttering your screen while trying to move quickly through many different functionality modes. What is not understandable is the

arbitrary solution that Blender comes up with to handle sub panels. To create a new panel, say for a new view of the 3d editing space, the user must "peel off" a new

panel by dragging it from the corner of an existing panel. This is easy enough to do, and users often inadvertently create new panels constantly while trying to resize existing ones. But to get rid of these new panels is tricky as there is no visible way to get rid of them. Most panel or window systems use the convention of a small 'x' icon or the sort to indicate where you click to get rid of a panel. Blender requires you to click and hold onto the same area you clicked to create the panel, then drag to merge the panel with a neighboring panel.

(An example of the "tear-away" corner of a panel. Disregard the "plus" sign, it does something different)

I appreciate that it is occasionally necessary to develop completely new interfaces to handle complex or new interactions. There is no reason, however, to throw away classic tropes of user interfaces when they have been shown to be flexible. Re-inventing the wheel is not always necessary.

Steep Learning Curve

Typically there is a tradeoff between how easy it is to learn to use a program and how complex the functionality of that program can be. This is no different in 3d modeling programs, where it is typical for users to spend a long time mastering the interface and functionality. Blender, however takes the high learning curve to an extreme. The interface itself provides very little hint of how to use it, is minimalistic on visible controls and expects the user to primarily use keyboard shortcuts. Keyboard shortcuts are not a bad means of control if they are consistent and have some sort of mnemonic mapping, but keyboard shortcuts in Blender change functionality depending on which mode you are in, operate with multiple modifier keys and seldom make mnemonic sense. This all adds up to an imposing learning experience that can turn away new users, whether they are experienced with other 3d programs or are new to modeling and are interested in learning the ropes. It is particularly dissapointing that complete newbies must face such an imposing learning curve since Blender is one of the few high quality free modeling programs, the perfect price for budding artists trying to learn the ropes.

Despite all of these problems, Blender eventually makes an odd sort of sense for me to use. Perhaps I suffer from Stockholm syndrome.

Best user interface I have used.

The best interface I have used is the interface of my second generation iPod touch. Functionality is pretty self evident, the user model is simple, the input mappings are either natural feeling finger motions or explicitly written out and above all it is (still) fun to use.

Clear Input Mappings

The biggest advantage of using a multitouch screen with (almost) no physical input buttons is that mappings between inputs are necessarily limited. If the application designer wants to have the user interact with the interface they must either put a button on the screen that performs a specific purpose or use one of the well established finger gestures that are present throughout the system, such as two finger pinch for zooming or one finger vertical and horizontal swipe for scrolling. This leaves little room for the ambiguous input mappings that can be found in systems with more physical buttons. As I have more recently moved to an Android mobile device this has become more clear, as the functionality of the hardware buttons often changes from application to application and even within the context of the core operating system.

Simple User Model

The simplicity of the user model in the iPod touch is another strong point. By this I mean it is clear what is going on with the system when you are using it. If you press on the button of an application it turns on and you use it. If you press the home button the program goes away and you do not have to worry about whether the application is still running, whether you saved what you were doing, whether you quit it properly. All of that is handled by the application and OS, with the only exception to this function being the music player that can run in the background. Again this is in comparison to my recent Android device, where it is never quite clear what state a program will be in when you return to it. Did it quit when you left it? Is it still running and consuming battery? Did it crash? These questions are simplified in the single application/process at a time user model of the non-multitasking version of iOS.

Fun to Use

Finally one of the things that impressed me the most when I first started using the iPod touch was how fun it was to interact with things with your fingers. This was compounded by the smooth and logical way things moved. I honestly spent hours idly scrolling between the home screens on the device because the movement was very satisfying. The kinematic scrolling introduced to handle scrolling through long lists was similarly satisfying. Scrolling through a long music library looking for a particular song was easy and actually fun, where performing such a task on a traditional ipod or laptop would be a long, imprecise process.

CHI Project Ideas

Here are a few ideas from the January 27th brainstorming session:

#1
Augmented Reality Virtual Interaction Space -

You use fiduciary markers to demarcate a virtual interaction space on a surface, most likely a table. You then use networked mobile devices to place virtual objects on the surface and interact with them. For example you could place a document on the surface with one device, then pick it up with another device, or interact with it on the surface.

Basically microsoft surface but virtual and displayed using augmented reality on multiple mobile devices.

The purpose of the system is to be able to create a virtual collaborative workspace on any flat surface, a real world table for example. The user's mobile devices would then act as "portals" into the virtual space by using augmented reality. If a user is a few feet away from the table and holds up their phone/pad, they see the real table but with virtual documents placed all over the table. As they move closer the documents become bigger and bigger until they place their device directly on top of where the virtual document resides in the physical space. The effect would be like putting a small picture frame over a 8.5x11 sheet of paper. The user can then pull the virtual document into their device, if they wish, and take it off of the virtual workspace. Similarly the user may take a document that resides on their device and place it into the shared virtual workspace.

The user may also edit documents directly in the virtual workspace using their device. For example, a user holds their ipad over a picture that they have placed on the workspace. They can now edit that picture through the ipad. If they wish to edit only a portion of the image they can "picture frame" a particular section of the image by placing the iPad directly onto the surface. If on the other hand they want to edit the whole image at once, they hold the ipad a little bit further away from the surface so that they can see more of the image through the picture frame, effectively getting a zoomed out view of the workspace.

This is basically an embodied 2d virtual workspace using mobile devices as both the viewer and the means of interaction.

As far as implementation goes, this would all be done by demarcating your virtual workspace on a real table with AR markers (fiduciary markers) and combining the visual location of these markers with they gyroscope in an iPhone. I do not know if this would be really possible, a subset probably is. But hey, dream big.

#2
Predictive Theories for finger/thumb interactions on tablets -

Manoj pointed out that he has had trouble finding good predictive theory on using thumb and finger interactions on tablets. This would be likely studying hand grips on tablets, sizes of tablets, how people have to hold them to perform certain tasks and what sort of limitations this places on their ability to interact with the software on the tablets.

624 #28 Dixon,Dasarp,Hammond - iCanDraw?

Introduction

This paper presents an assistive feedback system for hand drawing human faces. It is meant to help teach students how to draw a human face and help them see where to make corrections to make their drawing more accurate. The system does this automatically by constructing a drawing template from the reference image that the user has chosen to draw from. The user's drawing strokes are then compared against the template to see if they need correction and feedback.

Discussion

iCanDraw is a nice different way to apply sketch recognition ideas. I personally would like to use some of the design principles that come from this paper to create other such systems, such as for teaching users one and two point perspective drawing.