Data locality poses a major performance requirement in graph databases, since it forms a basis for efficient caching and distribution. This vision paper presents a new approach to satisfy this requirement through n-body simulation. We describe our solution in detail and provide a theoretically complexity estimation of our method. To prove our concept, we conducted an evaluation using the DBpedia dataset data. The results are promising and show that n-body simulation is capable to improve data locality in graph databases significantly.
Recently the demand to manage high amounts of linked
data increased substantially. This development has its origin
in data, generated by social as well as linked knowledge
networks like Wikipedia [
Beside the exact internal concept, this (graph) database has to support query, update and remove operations of single nodes or complete sub graphs as fast as possible. Clearly this requirement influences all of the different sub components of a graph database and can be fulfilled through improvements on many different levels. However, there is no other property, which has as much influence on the performance and scalability of the overall system as data locality. In terms of graphs this means that any node stored has to be also physical near to its linked nodes in the memory. This seems to be a straightforward requirement, but it’s hard to fulfill practically. In theory, a graph describes a multidimensional data structure, which has to be managed by the computer. Unfortunately, since memory systems work on a fixed one-dimensional memory layout, this cannot be done directly. The common solution to this problem is to define a mapping from multidimensional data to less (one) dimensional space. Although it’s not a problem to find any kind of mapping, it’s hard to preserve data locality at the same time. Therefore data locality isn’t assured directly (Figure 1) and databases try to speed up operations using additional indexes or in the case of main memory systems, by providing cheap jumps through random access memory.
Despite the fact that this solutions work out quite well for the problem, they are always tied to additional costs and remaining limitations and don‘t solve the actual problem. For example, additional indices need space and have to be updated on every change. Main memory systems work well on one core and one computer. But since, frequent jumps between the cores memory or even worse, between computers, are orders of magnitudes costlier than jumps within main memory of one single thread, it’s hard to distribute them properly.
To come up with a new approach to improve this situation,
this paper suggests building a graph database whose nodes
are aligned in memory by a n-body simulation system.
Inspired by real world physics laws, links will be simulated as
springs causing nodes to arrange themselves automatically.
As a result, when the state of lowest energy is reached, a
maximum of data locality is provided at the same time
(Figure 2). In addition, n-body simulation systems are known
to be highly distributable and computational feasible [
Consequently the aim of this paper is to show through experimentation, that such a simulation will optimally place graph nodes in memory achieving improved data locality on global scale.
The remainder of this paper is structured as follows. Section 2 describes related papers in more detail. In section 3 we present our new method by a short introduction to nbody simulation idea, as well as some adjustments we had to make. To prove that our concept is feasible, we performed some preliminary evaluations which results are discussed in section 4. Section 5 sums up with an conclusion and future works. 1.1
Although there is, at best of our knowledge, no related approach solving the data locality problem of graph database using n-body simulation, papers exists which make use of this method for related problems.
The idea of n-body simulation to support graph alignment
has been already proposed in the 80s [
Store)
• use their own implementation (Native Triple Store)
To the group of In-Memory Stores belong GRIN [
Jena SDB [
Part of the third group, the native implementations, are the
adapted Jena TDB [
Finally Sesame [
Consequently there is no system yet using n-body simulation to improve data locality and it’s interesting if such an approach is able to improve the overall performance of graph databases. 2.
In contrast to existing methods to store graph data we suggest an algorithm, which achieves a high degree of data locality. This algorithm is based on the idea, that link length don’t come for free, making longer links to more distant data locations more expensive than shorter links. With this additional costing factor c, an optimal solution for the locality problem in databases can be defined as achieving the global minimum of the sum of this costs overall nodes n:
n Call = min X ci
i=0
This optimization process becomes quickly unsolvable using analytically methods, therefore a common n-body simulation approach is applied. Every edge is seen as a physical spring between two data nodes. Springs will add distance depended forces Fl to the connected links causing them to approach each other:
Fl = Fc ∗ D(l) Where Fc is the force constant and D(l) a distance function of linked node l. This distance function can be for example a linear function returning the distance to the linked node l or an exponential function causing forces to increase exponentially with the distance.
Since a node is influenced by all its linked nodes, all forces Fl have to summed up to achieve the final overall force Fn:
n Fn = X Fi
i=0 an = Fi/mn Δvn = an ∗ s
Now we can calculate the acceleration of the current node nusing its mass mn:
In our prototype we set mn to 1 but for later implementations this parameter may represent a ideal way to reduce the movement of big nodes using the number of links as mass.
This would cause big nodes to be moved less often. Finally we can use an to calculate the change of velocity 1
where s describes the used step size. For the sake of simplicity our prototype used a step size of 1. The simulation can now be formulated in three steps: 1. Calculate vn for all n. 2. Change vn according to Δvn and calculate new posi
tion. 3. Check if there is any movement . If yes then goto 1. 4. Simulation finished. nodes. Indeed for a complete graph, the n-body simulation 2.1 Adjustments cannot improve any locality, because energy equilibrium is
N-body simulation methods have been used widely and already reached and the simulation would terminate after
very successfully in many fields of physics over the past the first step. Assuming that n >> m the next important
decades. However some adjustments are necessary to make factor is snum, which depends on the dataset as well as the
the approach useful for locality calculations. used step size s. Consequently an increased step size would
As memory of all modern computers is accessed through dis- lead to less simulation steps. However too large steps sizes
crete addresses, the simulation has to take this into account also increase the computational error between steps and will
and have to operate on integers entirely. This approach has lead to an unstable simulation eventually. Fortunately, a
two advantages. In the first place it avoids the introduction variety of algorithms exist to minimize this approximation
of additional repulsion forces to keep nodes at a minimum error, using one step or multistep methods as well as
methdistance to each other and secondly, the calculations can be ods with variable step size at need [
Generally the complexity of n-body simulations can be
estimated as O(n ∗ m ∗ snum) where n describes the number
of nodes, m the number of links per node and s the number
of simulation steps needed until energy equilibrium.
Consequently for a complete graph, where n = m the complexity
raises to O(n2 ∗ snum). This wouldn’t be feasible for high
amounts of data. Fortunately [
To prove the suggested concept we implemented a prototype and made some preliminary evaluations. To get realistic results we chose a subset (first 200 000 triples = 110,205 nodes) of the DBpedia dataset. All tests were conducted on a single machine (Mac Pro Intel Xeon 2,26 GHz) using a simple single threaded process with 200 MiB of dedicated ram.
To get an visual impression how effective our method increases data locality, we visualize every data element as a pixel in an image. As we are working on a one-dimensional space, all values are simply wrapped at the end of image width to create a two dimensional image. Every pixel position corresponds to the actual position of a data node in the data space.
In Figure 5 the color of this pixel represents the maximum distance of a node to its linked neighbor nodes in the data space. Using a maximum value of n/2 (value red) this Figure shows the development over time until energy equilibrium is reached. At t = 0 the data is scattered randomly in the data space. There are plenty of nodes, which have to jump through the whole data space to access their linked nodes. At t = 0.5 the data distribution has improved already, but can be further enhanced until a state of minimum energy (no more movement of nodes) is reached (t = 1). The final result shows that all nodes have now arrived at a position, where they can access their most distant linked node with a minimum of locality change.
To get a better impression of the exact numbers, we created a histogram (Figure 7) for the same sample data. For better understanding, be aware of the logarithmic scaling on the vertical axis. Furthermore we moved the mid-term frame t = 0.5 to quarter time t = 0.25 to get a better impression of the progress over time. Similar to Figure 5, at t = 0 one can observe an almost equal distribution of nodes along the complete range of possible distances. As an important matter of fact, there is already a peak of values having very close linked nodes on the very left side (distance < 1, 000) of the diagram. Since it’s often the case that new nodes are introduced followed by their direct neighbors, the input file itself can be seen as origin of this peak. Of course this issue can only have a positive impact on local data locality and not on global scale, as we want to achieve. During the simulation over t = 0.25 to t = 1.0 one can observe a significant reduction of distances to about one quarter of the originally data space. In addition, the histogram points out that global data locality comes also at cost of local data locality, which is showed by the reduction of the red peak at t = 0 mentioned before to the blue one at t = 1.0. The cause of this reduction can be seen again in the mapping of multi dimensional data to less (in our case one) dimensional space, where different data nodes claim the same position (Figures 3 and 4).
Furthermore there are some small peaks (two nodes) remaining near distance 50, 000. These nodes couldn’t be aligned very well. Although we always expected problems with nodes that are highly linked to different other nodes and can’t be further optimized by means of location, this appears not to be the case here, as the number of links of the worst-case node where only about 300. Unfortunately, this remains a rather unsatisfied situation and has to be further investigated in future. However, as shown in our sample data set, these nodes can be considered as very rare (overall 8 nodes out of 110, 025 until distance of 26, 000). These problems apart, it’s most important that the global data locality improved substantially. As previously seen in Figure 5, the histogram shows that most nodes are far less distant to their linked nodes than at the start of simulation. In particular, the link length was reduced to 1/4 in the worst and to 1/10 in the average case.
Based on this data it should be possible to make efficient decisions how graph data can be separated in certain chunks, to be distributed on different cores as well as on different computers. To gather more insight into this, we used an access heat map. To create this map all data positions lying between a node and all it’s linked nodes are incremented by one. Of course in main memory we are able to randomly access every position at same speed, but in a distributed environment this model fits very well. When this is done for all nodes and their respective linked nodes, every position marks the number of accesses needed to visit every neighbor node within data space (Figure 6). This image gives an impression, where the data space can be separated best, choosing less dense (blue in the Figure) zones.
The aim of this paper was to show that a n-body
simulation can improve graph data locality significantly. After a
introduction to our suggested method, we evaluated a
experimental prototype using partial data of the DBpedia dataset
[
We theoretically showed that our n-body approach should scale well into millions of graph nodes. However, our prototype is currently not optimized for very large data sets like the complete DBpedia dataset, consisting of about 100 million triples. Hence our goal for future works will be to optimize the simulation by improving the algorithm and finding a way to distribute the simulation on many cores and computers. As a result of this development, we hope to provide practically evidence that our method is working on large real world graphs preserving computational feasibility. 5.