Over the last week we had our off campus meeting with a lot of communication training (very good and fruitful) as well as a special treatment for some PhD students called “massage your diss”. I was one of the lucky students who were able to discuss our research ideas with a post doc and other PhD candidates for more than 6 hours. This lead to the structure, todos and time table of my PhD proposal. This has to be finalized over the next couple days but I already want to share the structure in order to make it more real. You might also want to follow my article on a wish list of distributed graph data base technology

[TODO] 0. Find a template for the PhD proposal

That is straight forward. The task is just to look at other students PhD proposals also at some major conferences and see what kind of structure they use. A very common structure for papers is Jennifer Widom’s structure for writing a good research paper. This or a similar template will help to make the proposal readable in a good way. For this blog article I will follow Jennifer Widom more or less.

1. Write an Introduction

Here I will describe the use case(s) of a distributed graph data base. These could be

  • indexing the web graph for a general purpose search engine like Google, Bing, Baidu, Yandex…
  • running the backend of a social network like Facebook, Google+, Twitter, LinkedIn,…
  • storing web log files and click streams of users
  • doing information retrieval (recommender systems) in the above scenarios

There could also be very other use cases like graphs from

  • biology
  • finance
  • regular graphs 
  • geographic maps like road and traffic networks

2. Discuss all the related work

This is done to name all the existing approaches and challenges that come with a distributed graph data base. It is also important to set onself apart from existing frameworks like graph processing. Here I will name the at least the related work in the following fields:

  • graph processing (Signal Collect, Pregel,…)
  • graph theory (especially data structures and algorithms)
  • (dynamic/adaptive) graph partitioning
  • distributed computing / systems (MPI, Bulk Synchronous Parallel Programming, Map Reduce, P2P, distributed hash tables, distributed file systems…)
  • redundancy vs fault tolerance
  • network programming (protocols, latency vs bandwidth)
  • data bases (ACID, multiple user access, …)
  • graph data base query languages (SPARQL, Gremlin, Cypher,…)
  • Social Network and graph analysis and modelling.

3. Formalize the problem of distributed graph data bases

After describing the related work and knowing the standard terminology it makes sense to really formalize the problem. Several steps have to be taken: There needs to be notation for distributed graph data bases fixed. This has to respect two things:

a) the real – so far unknown – problems that will be solved during PhD. In this way fixing the notation and formalizing the (unknown) problem will be kind of hard.

b) The use cases: For the web use case this will probably translate to scale free small world network graphs with a very small diameter. Probably in order to respect other use cases than the web it will make sense to cite different graph models e.g. mathematical models to generate graphs with certain properties from the related work.

The important step here is that fixing a use case will also fix a notation and help to formalize the problem. The crucial part is to choose the use case still so general that all special cases and boarder line cases are included. Especially the use case should be a real extension to graph processing which should of course be possible with a distributed graph data base. 

One very important part of the formalization will lead to a first research question:

4. Graph Query languages – Graph Algebra

I think graph data bases are not really general purpose data bases. They exist to solve a certain class of problems in a certain range. They seem to be especially useful where information of a local neighborhood of data points is frequently needed. They also often seem to be useful when schemaless data is processed. This leads to the question of a query language. Obviously (?) the more general the query language the harder to have a very efficient solution. The model of a relational algebra was a very successful concept in relational data bases. I guess a similar graph algebra is needed as a mathmatical concept for distributed graph data bases as a foundation of their query languages. 

Remark that this chapter has nothing much to do with distributed graph data bases but with graph data bases in general.

The graph algebra I have in mind so far is pretty similar to neo4j and consists of some atomic CRUD operations. Once the results are known (ether as an answer from the related work or by own research) I will be able to run my first experiments in a distributed environment. 

5. Analysis of Basic graph data structures vs distribution strategies vs Basic CRUD operations

As expected the graph algebra will consist of some atomic CRUD operations those operations have to be tested against all different data structures one can think of in the different known distributed environments over several different real world data sets. This task will be rather straight forward. It will be possible to know the theoretical results of most implementations. The reason for this experiment is to collect experimental experiences in a distributed setting and to understand what is really happening and where the difficulties in a distributed setting are. Already in the evaluation of graphity I realized that there is a huge gap between theoretical predictions and the real results. In this way I am convinced that this experiment is a good step forward and the deep understanding of actually implementing all this will hopefully lead to:

6. Development of hybrid data structures (creative input)

It would be the first time in my life where I am running such an experiment without any new ideas coming up to tweak and tune. So I am expecting to have learnt a lot from the first experiment in order to have some creative ideas how to combine several data structures and distribution techniques in order to make a better (especially bigger scaling) distributed graph data base technology.

7. Analysis of multiple user access and ACID

One important fact of a distributed graph data base that was not in the focus of my research so far is the part that actually makes it a data base and sets it apart from some graph processing frame work. Even after finding a good data structure and distributed model there are new limitations coming once multiple user access and ACID  are introduced. These topics are to some degree orthogonal to the CRUD operations examined in my first planned experiment. I am pretty sure that the experiments from above and more reading on ACID in distributed computing will lead to more reasearch questions and ideas how to test several standard ACID strategies for several data structures in several distributed environments. In this sense this chapter will be an extension to the 5. paragraph.

8. Again creative input for multiple user access and ACID

After heaving learnt what the best data structures for basic query operations in a distributed setting are and also what the best methods to achieve ACID are it is time for more creative input. This will have the goal to find a solution (data structure and distribution mechanism) that respects both the speed of basic query operations and the ease for ACID. Once this done everything is straight forward again.

9. Comprehensive benchmark of my solution with existing frameworks

My own solution has to be benchmarked against all the standard technologies for distributed graph data bases and graph processing frameworks.

10. Conclusion of my PhD proposal

So the goal of my PhD is to analyse different data structures and distribution techniques for a realization of distributed graph data base. This will be done with respect to a good runtime of some basic graph queries (CRUD) respecting a standardized graph query algebra as well as muli user access and the paradigms of ACID. 

11 Timetable and mile stones

This is a rough schedual fixing some of the major mile stones.

  • 2012 / 04: hand in PhD proposal
  • 2012 / 07: graph query algebra is fixed. Maybe a paper is submitted
  • 2012 / 10: experiments of basic CRUD operations done
  • 2013 / 02: paper with results from basic CRUD operations done
  • 2013 / 07: preliminary results on ACID and multi user experiments are done and submitted to a conference
  • 2013 /08: min 3 month research internship  in a company benchmarking my system on real data
  • end of 2013: publishing the results
  • 2014: 9 months of writing my dissertation

For anyone who has input, knows of papers or can point me to similar research I am more than happy if you could contact me or start the discussion!

Thank you very much for reading so far!

If you like this post, you might like these related posts:

  1. Wishlist of features for a distributed graph data base technology I am just dreaming this does not exist and needs...
  2. Data structure for Social news streams on Graph data bases UPDATE: look at http://www.rene-pickhardt.de/graphity for a more scientific survey and...
  3. Related work of the Reading club on distributed graph data bases (Beehive, Scalable SPARQL Querying of Large RDF Graphs, memcached) Today we finally had our reading club and discussed several...
  4. From Graph (batch) processing towards a distributed graph data base Yesterdays meeting of the reading club was quite nice. We...
  5. Aurelius Titan graph enables realtime querying with 2400 concurrent users on a distributed graph database! Sorry to start with a conclusion first… To me Titan...

Sharing:

Tags: , , , , , , , , , , , , , , , ,

6 Comments on PhD proposal on distributed graph data bases

  1. René, I posted a note about your proposal at my blog in hopes of getting others to comment.

    In general I think the proposal needs to be revised, downward, to be smaller, more specific. Believe me when I say that I have gotten the same advice, on multiple occasions! It really isn’t necessary for a PhD dissertation to be your magnum opus in the field. That usually comes later.

    For example, when you talk about relational algebra and the need for a graph algebra. The development of relational algebra made SQL possible but they are independent fields, each of which has dissertations written on single parts of them. A graph algebra and graph query language aren’t any different.

    Or when you are going to survey the “related work.” See my blog for comments on that aspect of your proposal.

    In short, I think there are a number of dissertations here. You need to pick one of them.

    Hope you are having a great week!

    Patrick

    PS: Can you do something about that annoying newsletter popup that simply won’t go away? I have signed up for it but that doesn’t do any good.

  2. Max De Marzi says:

    René,

    Sounds awesome, but super ambitious. If you choose to build a Gremlin compatible system, it removes a bunch of work, makes it easier to benchmark against others, and lets you focus on the underlying system. It would also make it easier to gain adoption if you were to turn this into a real product at some point.

    Regards,
    Max

  3. [...] PhD proposal on distributed graph data bases by René Pickhardt. [...]

  4. Daniel says:

    Hi René,

    we talked about JGraLab this morning and you asked me to post the link here: https://github.com/jgralab

    Some more informations can be found on the official homepage:

    I’m sure, it is interesting for everybody working with graphs.

    Regards,
    Daniel

  5. Gerd says:

    Hi René,

    your proposal is quite challenging and it is
    probably to much for one thesis.
    In general, it is no problem if you target in your proposal a rather
    broad or general topic like distributed graph databases,
    and you will narrow your topic while working on your thesis.

    Details:

    Introduction:
    I also like the article of Jennifer Widom, especially for the introduction it is a valuable guideline.
    Thus, I would recommend to consider this structure
    (five points of an intro) also in your introduction.
    (Currently, is is only a use case description.)

    Related Work:
    You cover a large field of related work, which is important for a
    PhD thesis (and also for your research).

    Section 3 (Formalization)
    I consider this as an important part of a proposal since this should
    motivate your work, i.e., what is the problem?,
    what are the limitations of current approaches/state of the art?
    What is the gap you want to close with your work?
    As you mentioned, this is hard, but quite important and I have the
    feeling this should be further elaborated.
    (This is probably quite difficult at the moment since your topic is quite broad.)

    Sections 4, 5 and 6 (block: graph algebra, CRUD, hybrid DS)
    These three sections could be a thesis on their own.
    Regarding the content of these paragraphs,
    I agree with your problem statements and your research plan.
    (Personally, I like this (sub-) topic a lot.)
    I was wondering whether the structure could be like this:
    (1) analysis of basic CRUD operations
    (2) hybrid data structure (based on results of the analysis)
    (3) algebra and query language for a hybrid structure?

    Sections 7,8 and 9 (block: ACID)
    Section 7 reads like “making experiments and then recognize
    research questions”.
    I would suggest to be more precise and systematic, and formalize the
    particular problems: (1) ACID in general, (2) ACID in distributed systems,
    (3) ACID in graphs (graph data bases).
    Afterwards, the experiments are more focused and it might
    be easier to come up with the best data structure (in Sect. 8).

    Regards,
    Gerd

Leave a Reply

*

Close

Subscribe to my newsletter

You don't like mail?