Today we continue reading the paper  "Horton: Online Query Execution Engine For Large Distributed Graphs" by Sarwat, Elnikety, He and Kliot.
This paper talks about large graphs that don't fit on a single server. The paper introduces Horton a graph query execution engine. We were reviewing its architecture.
It has four components  - the graph client library, the graph coordinator, graph partitions and the graph manager. We discussed the first three components. We now look at the Graph Manager. This provides an administrative interface to manage the graph such as loading a partitioned graph or adding and removing servers. It also assigns partitions to the servers by taking the output of  partitioning algorithm and placing nodes in the right partitions. Partitioning algorithms are external because they are not online. Any algorithm can be used such as a simple hashing that's based on node and edge attributes. If the partitions don't suffice in keeping graph access local, then the partitioning algorithm can be changed.
Horton is written in C# using the .Net framework and the asynchronous communication is implemented using sockets and task parallel library.Horton is built on top of Orleans which is a distributed runtime for cloud applications.
Some sample queries on the graph for Codebook using Horton include the following:
Who wrote this function ?
What libraries depend on this library ?
Whom should I contact to fix this bug ?
Adhoc queries can also be executed showing the flexibility of the query language and the effectiveness of the execution engine.
#codejam problem
We discussed compareTo between ominoes in the previous post that takes different orientations and then compares. Tanslations and different positions in the matrix can also make the ominoes look different. Implement compare for ominoes with same orientation

int compare(int[,] matrix1, int[,] matrix2, int rows, int columns)
{
int k = find_top_left_corner(matrix1);
int tr1 = k /columns;
int tc1 = k % columns;
int h = find_bottom_right_corner(matrix1);
int br1 = h/columns;
int bc1 = h%columns;

k = find_top_left_corner(matrix1);
int tr2 = k /columns;
int tc2 = k % columns;
h = find_bottom_right_corner(matrix1);
int br2 = h/columns;
int bc2 = h%columns;

for (int i = 0; i <= br1-tr1; i++)
  for (int j = 0; j <= bc1-tc1; j++)
       if (matrix1[br1+i,bc1+j] != matrix [br2+i, bc2+j])
           return matrix1[br1+i,bc1+j] - matrix [br2+i, bc2+j];

return 0;
}

In comparing the sequences of 1 and 0 for the portion containing the arrangementsame in the two matrices, we pick the diagonal corners of the bounding rectangle. To determine this we pick the
Min pair (r, c) and max pair  (r,c) from all those having value 1
Int r = k;
Int c = k;
For  (int I = 0; I < k; i++)
For (int j =0; j < k; j++)
If ( matrix1[i, j] == 1 ){
   If (I < r) r = i;
   If (j < c) c = j;
}