epoch: 1274091914
Graph partitioning is known to be a hard problem and in algorithm theory many partitioning problems are NP-complete. With the raise of non-relational databases in general and graph databases in particular the partitioning problem nevertheless turns more and more into a practical challenge.
A search on a graph database is in essence the exploitation of a graph theoretical notion of structure or measure of a graph. One may think of two types of structure, global and local. A global property for example is the chromatic number of a graph. On the opposite, a given vertex of a graph may be a member of a certain cluster or community of that graph. This is a local property since even the definition of “community” is local - dependent of a notion of density making sense only in a local context.
In practical applications almost always only local searches based on traversals starting from a given node are useful. Determining global properties just takes too much time, at least for huge graphs such as social networks. Keeping that in mind, why not just partitioning a graph into local neighbourhoods big enough to solve a certain problem?
Such a partitioning scheme could not consist of disjoint parts but will probably be overlapping. And also, such a partitioning would be dependent on the particular problem. But this is a general feature of a graph database - one have to model the data into a hand crafted graph to solve a certain class of problems and the same model may not be well suited for another class.
Overlapping local partitionings or mappings are well known in mathematics such as the theory of manifolds where one have charts and atlases. The local structure is conserved in a chart but the global totality may only be visible over the whole atlas.
Most practical problems with graph partitionings occur when a traversal reaches a frontier or when one have to decide for an insert into which partition to place the new item. If overlappings are allowed these problems may be less important.
Overlapping partitionings might be a good strategy to organize data used to solve local problems. How to build up such partitionings and how to prevent them to grow to the size of the whole graph may be again dependent on the particular problem.
Powered by Tumblr; designed by Adam Lloyd and Ingo Schramm.
