This is the second installment in a blog series examining exchange markets and how they are a good use case for using a graph database.

Civilization has designed exchange markets since the first early humans made stone tools and others recognized their value. In fact, non-monetary exchange markets predate all other markets by such a great deal of time that you might say that we are inherently predisposed towards them.  Of course, transacting in exchange markets can be extremely difficult, because value is subjective, and we have a tendency to overvalue what we have. Successfully making a trade often involves tedious work to first find potential participants and then convince them to close the deal.

This challenge is well illustrated in an episode of the animated show, “My Little Pony ©: Friendship is Magic,” titled “Trade Ya!” where one of the ponies named Rainbow Dash wants to trade for a rare book held by a book seller.  In the Rainbow Falls Traders Exchange, no money is used. Instead, the ponies must trade only for goods or services. Rainbow Dash brings her most valuable possession, her lucky horseshoe, to trade for a first edition copy of the Daring Do book. Unfortunately, the book seller does not find her horseshoe valuable, so the rest of the episode involves Rainbow Dash going from vendor to vendor to enact a series of trades starting with her “valuable” horseshoe and ending with the rare book.

Figure 1: My Little Pony: Friendship is Magic (Trade Ya)[i]

mylilpony

“My Little Pony” illustrates both points about the subjective overvaluing of what the seller has and the tedious work of finding traders.  As the episode proceeds, Rainbow Dash finds that she needs an Orthros, which is a three-headed dog, to trade for the Daring Do book. Next, she finds that she needs a lamp to trade for the Orthros, a cement chicken to trade for the lamp, and a crystal chalice to trade for the chicken. Finally, in a moment of exhaustion, they go to the crystal chalice seller only to find that what she needs is an old rusty horseshoe! This closes the chain, and the transactions can be completed, resulting in the trade for the rare book.

While this scenario makes for a great conflict-resolution storyline, it also illustrates the larger difficulty in finding the matches needed to transact in an exchange market.  The trade matches almost seem serendipitous because they happen so rarely. Whether it is finding patient-donor pairs to complete an organ donation (see my previous Kidney Exchange blog), or exchanging horseshoes for books, the ultimate goal is to fulfill the transaction chain.

Imagine that you are designing an exchange market.  Each trader in an exchange must be a buyer and a seller. If an exchange is simple, where there is only one type of transaction (say exchanging musical records), then the exchange can be represented by a simple schema: a Trader vertex type and a Match edge type (see class descriptions below).  In a record exchange market, records are traded not money, so trades are typically very subjective. In other words, a certain record may have huge value for one person, but might not have an equally high value to others.

Figure 2: Simple Exchange Schema

public class Match extends com.infinitegraph.BaseEdge 
{
  private String title;
  public Match(String title)
  { 
    this.title = title; 
  }
  public String getTitle() 
  { 
    fetch();
    return title; 
  }
} 

public class Trader extends com.infinitegraph.BaseVertex
{
  private String name;
  private String email;

  public Trader(String name, String email)
  {
    this.name = name;
    this.email = email;
  }

  public String getEmail()
  {
    fetch();
    return email;
  }
  …
  private String[] ownedTitles;
  public String[] getRecords()
  {
    fetch();
    return ownedTitles;
  }
  …
  private String[] interestedTitles;
  public boolean wants(Record record)
  {
     fetch();
     for(String title : interestedTitles)
     {
        if(title.equals(record.getTitle())
	  {
	     return true;
	  }
     }
     return false;
  }
}

In this record exchange, the matches are made when the title of a record is matched between a buyer and a seller.  Other factors, such as record condition, may be involved, so the match algorithm may be much more complex than just the title.  In most exchanges, like the kidney exchange, the matching algorithm is quite complex, but in our record exchange, it is quite simple.  Imagine the design for a simple record exchange application like this using InfiniteGraph, Objectivity’s distributed graph database:

Figure 3: Sample Record Exchange Application

public class ExchangeApp
{
  public static void createMatches(Trader buyer, Trader seller)
  {
    Transaction tx = 	xchangeGraph.beginTransaction(AccessMode.READ_WRITE);
    String[] recordsToSell = seller.getRecords();
    for(String record : recordsToSell)
    {
      boolean match = buyer.wants(record);
      if(match)
      {
	  seller.addEdge(new Match(record), buyer, EdgeKind.OUTGOING, 0);
      }
    }
    tx.commit();
  }
}

Every time traders are added to the exchange database, they are processed through the match algorithm, which builds up the graph as it adds the match relationships to the traders.  Then, at regular intervals, a separate monitoring process looks for chains of matching links.

Figure 4: Monitoring Process

public static void findChains(Trader trader)
{
  Transaction tx = xchangeGraph.beginTransaction(AccessMode.READ);
  NavigationResultHandler alertHandler = new AlertResultHandler();
  // expresses a chain pattern up to 10 degrees that ends in original
  String chainPattern = 
    “[Trader]…-[Match]->[Trader(‘name == ” + trader.getEmail() + “’)]”;
  Navigator navigator = trader.navigate(null, chainPattern, 
	new PolicyChain(new MaximumPathDepthPolicy(10)), alertHandler);
  navigator.start();
  tx.commit();
} 

The handler for the results would send off an alert once a chain was found. The alert may involve emailing the traders and possibly getting a confirmation, which would then activate the chain. Once the chain is processed, the records are removed from the database.

As you can see in this example, designing an exchange market using a graph database is very simple.  An intuitive API for making connections, querying for n-way chains, and handling the results is already available. The underlying graph engine can also process data at scale and in real time.  If an extra level of qualification is needed for matching, there are custom qualifiers for dynamically processing a match algorithm based on the data in the traders at query time.  Interfaces for representing data uniquely in the database are also provided so that data points and relationships are not duplicated.

Without a graph database, the connections between the data would not be represented in the database in a way that supports finding the chains in real time.  The performance factor is a requirement for active exchange markets where the quality of the chains is dependent on how fast they are processed.  Finding chains in real-time, when they are likely separated by multiple degrees, is not possible unless you use a specialized graph database solution like InfiniteGraph (see the comparison chart below).

Figure 5: Comparing Path Finding Performance (RDBMS vs GraphDB)

pathfinding

Moreover, the InfiniteGraph API for managing the data is extremely simple and reduces the complexity of an application that manages the interactions between traders.  No matter what the size, InfiniteGraph works as a scalable solution for an exchange design, because it is distributable.

In addition, creating an independent matching algorithm removes the tendency to overvalue objects.  It allows the system to independently find match chains while performing the extensive underlying work automatically.  If there are matches to be found in the data, then an exchange application built on top of a graph database will find them.

Since the transactions don’t have to be done physically like in a flea market, transactions done over the web through a real-time processing engine can engage a much broader audience.  This can also open up markets for the exchange of good or services that don’t currently exist.

As you can see, we have come a long way from exchanging stone tools.  My hope is that like Rainbow Dash, we can find a way to get what we need while at the same time live more minimally and consume fewer resources.  My belief is that through popular exchanges, we can open up new ways of finding things we need by trading away things we don’t.

For more information about Objectivity’s InfiniteGraph, visit our products page or contact us.  Be on the lookout for Part 3 of the Exchange Market Blog Series where I will be discussing how Big Data application built using our Information Fusion platform ThingSpan can support much greater data throughput for an enterprise-level exchange.

 

                                                                      

My Little Pony © 1999 Hasbro, Inc. All Rights Reserved.

[i] http://mlp.wikia.com/wiki/Trade_Ya!

 

 

Nick Quinn

Principal Architect of InfiniteGraph

Nick Quinn - Principal Architect

SHARE THIS POST
Share on FacebookTweet about this on TwitterShare on Google+Share on LinkedIn