I remember that day clearly. As I entered SemantiNet’s offices, Sagie (our director of R&D) approached me holding a thin black box in his hand.
“We did it!” he said.
“Did what?” I asked, looking at the black box which resembled a hard disk drive on a diet.
“We managed to fit all of our Knowledge Graph on a 20GB Solid State Drive. This small box holds all of the information in Wikipedia and dozens of other web sources”.
“Wow”, I said, “Unbelievable! They say the world is getting smaller, but I never imagined that the web is getting smaller, too…”
To understand the significance of this achievement, you need to realize that Headup stores a lot of information. And I mean a lot. Headup knows about more than 100 million topics, spanning diverse fields from movies to microchips, and religion to rollerblades. Each topic has several attributes, and the topics are connected to each other through semantic relationships. For example, a band is connected to its albums, each album is connected to its tracks, a company is connected to its products, etc.
To get a better grasp on this, let’s look at a very small piece of the Headup knowledge graph described in the diagram below. This piece of the graph is connected to the actress Angelina Jolie, one of the entities or objects that Headup knows about. It includes the different pieces of information that Headup knows about her, gathered from various web sources. General information about Angelina Jolie, such as her birth date, husband, and city of birth, is taken from Wikipedia. The movies she appeared in, such as “Wanted”, “Bewulf” etc. are taken from IMDB. Ratings for those movies are taken from RottenTomatoes, Information about people who like each of these movies is taken from personal preferences that are exposed on social networks such as Facebook and MySpace.
Now imagine that Headup needs to store such detailed information about each one of millions of topics that appear in Wikipedia and in numerous other data sources, and constantly manage and update all the different relationships between them. Currently we have over 300 million nodes (objects and attributes) in our graph, with over 2 billion connections.
To store this data and enable scalable, reliable and efficient access to it, we needed a highly-optimized data store, with a small footprint and super-fast performance. Traditional off-the-shelf databases such as MySQL and Oracle are optimized for documents and transactions, but not for efficiently traversing relationships and properties of objects. Recently, several dedicated Graph Databases (also called “Triplestores”) have become available, which are more optimized for semantic web applications. However, as we kept adding more and more knowledge to Headup, we came to the conclusion that none of these off-the-shelf solutions were suitable for Headup. So we had no choice but to develop our own data store, that is optimized for our needs.
It turned out that by creating a unique data store and optimizing it for the structure of our knowledge graph, we were able to achieve an order of magnitude boost in performance over existing solutions, both for building the graph and for accessing it. Our data store can currently support up to 1 billion nodes (topics and attributes), and dozens of billions of edges (relationships between topics and attributes), so we still have plenty of room to grow.
Building such a huge graph in itself is a far from trivial task, since it requires processing amounts of data which cannot be stored in the computer’s main memory (RAM). Hard drives are also not a good choice due to their limited access speeds and data transfer rates. Therefore, we approached this challenge by utilizing the Hadoop software framework (inspired by Google’s MapReduce), which supports huge-scale, data-intensive distributed applications. Using Hadoop enables us to build the graph in a completely distributed manner, so we can easily deal with this vast amount of data.
The raw data of our current graph spans about 500 Gigabytes. Using numerous optimization techniques, we managed to compress this amount of data to just 15 GB, meaning that we can hold the whole graph in RAM. As we add more sources, the graph grows to a point where it is no longer cost effective to store it in RAM. For this reason, the graph can be easily stored on a commodity SSD, which costs around $100. Furthermore, the graph is designed for optimal utilization of the drive’s internal cache, block sizes and the fast random access.
The good news is that compressing the graph is done without compromising performance. In fact, using a compressed graph actually increases its performance, since much less data has to be accessed and processed. Using our graph data store, we can find every piece of information in about 10 milliseconds using a hard disk drive, 0.1 milliseconds using a solid state drive, and just 0.1 microseconds when the information is in RAM.
To demonstrate the performance of Headup’s graph database, let’s look at a typical Headup-powered web page which contains 50 terms and 700 candidates for disambiguating them. Using our unique data sore, such a page can be processed in only 2 seconds using an HDD, and about 200 milliseconds using an SSD. With such performance, we can easily support sites with millions of unique page views without overloading its computing resources.
“Can I have the graph for one night?” I asked Sagie.
“What do you need it for? Do you have anything to add to this immense knowledge repository?” Sagie was totally surprised.
“Not really”, I said. “I want to put it under my pillow when I sleep, and hopefully all the Angelina Jolie stuff you showed me will inspire my dreams…”