GSoC 2015 Application Pratik Kalshetti: NetworkX Alternative backends for storing graph data

About Me

Basic Information

Name: Pratik Kalshetti

University: Indian Institute of Technology Jodhpur, India

Email:: ug201210018@iitj.ac.in

Github: pmkalshetti

Blog: https://pmkalshetti.wordpress.com/

Background:

• What platform do you use to code? What editor do you prefer and why?

  I am quite accustomed with Linux (Ubuntu 14.04) for programming and use Windows for other documentation and gaming stuff. My favorite editor is Sublime text not just because of its wide scope of languages but also it provides a unique of multiple cursor which enables editing with great ease. Its color preferences just cruise in the beauty of coding.

• What is your experience programming? Tell us about something you have created.

  I have been enjoying the essence of programming since three years getting a crisp of many languages C/C++ (over 4000 lines of code), Python (over 3000), Java (around 1000), MySQL & PHP. Not just I have contributed to OpenCV library, but worked on numerous projects, few relevant are mentioned below.

  • Scheduler: The basic purpose of this software was to simulate the trains arriving at various platforms on a station & departing from that station.The software implementation in python using multi threading concepts preceded the making of the SRS Document following a prescribed set of stages while the software was being developed. SQLite served the backend for data storage, retrieval & manipulation.
  • [Model Graphs]: A basic implementation for generating Barabasi Albert model graphs and Watts-Strogatz small world model graph in python using networkx.
  • [Hierarchical Database Software]: I worked on Indian Government’s multi-tier Suggestions Portal and designed a hierarchical database model wherein documents could be processed securely via different ranked officers. It was created on ASP.NET framework with added security from SQL Injection.

• What is your experience with Python? What are your favorite features of Python that are lacking in most other common programming languages? What, in your opinion, is the most advanced Python language feature or standard library functionality that you have used?

  I have been using Python for computer vision applications (OpenCV), Graph models of Networks (networkx) and Software Projects (PyQt). The below made me fall in love with this language while working on these projects.

  1. No time-waste in declaring the types of arguments or variables
  2. Python's powerful polymorphic list and dictionary types, for which rich syntactic support is built straight into the language that helped me in my GUI for software projects
  3. The True/False-state for every variable - a boon for checking used variables.

• What is your favorite feature of NetworkX? Demonstrate it here with a cool example.

  My favorite feature of NetworkX is the visualization component that uses Matplotlib to draw the graphs in the layout we choose. It seems like a very handy feature to quickly visualize what we are working on. An example of this could be found here (link) which was used for generating random graph.

• Have you ever used git or another version control system?

  Yes I have been using GitHub for various team projects and keeping my code repositories open to community for feedback on improvement. Also I have contributed on OpenCV via pull requests on Git.

Project Idea

I would have a SQLite database having relations 'nodes', & 'edges'. The former will be used to store node_id (primary key), node_value (stored in string format), node_type (int/tuple/dictionary/list) which will help for various functions, etc. while the latter relation will consist of node_1, node_2 (both comprise of candidate key), attr (to store various types of attributes). Focus will be kept to maintain atleast 3NF for the database to resolve data redundancy and inconsistency issues.

• What do you want to achieve?

  I would like to achieve a scalable multiple storage backend for NetworkX. NetworkX seems limited in the current state that it only supports reading and writing from text files and is not good enough for larger graphs.

• What excites you about this project? Why did you choose it?

  I am excited about this project because I have used NetworkX before in my University lab sessions and I felt it is a serious drawback for not able to support data from multiple sources. I believe providing a generic interface for multiple storage backend would be really useful to the scientific community as well. I will write the backend for SQLite but presence of a generic interface means multiple backends can be added later.

• What have other people done on this idea? Has it been implemented before? Are there any papers or blog posts about it?

  Yes, Twitter used to have a Graph database represented as an SQL database before but they moved away from it. Their work even though deprecated can be found at https://github.com/twitter/flockdb. I want to take an inspiration from that model and want to model the graph through tables in SQLite.

• How much time do you plan to invest in the project before, during, and after the Summer of Code? (we expect full time 40h/week during GSoC, but better make this explicit) If you plan to take any vacations over the summer, let us know about it here.

I will be completely devotional towards GSoC and would be investing 40h/week. Before the Summer of Code I would be getting accustomed with the schema of databse and also design the various modules to be implemented for generic classes. After GSoC too, I would be continuously contributing since it would be my responibility and I would love to do the same.

• Please provide a schedule of how this time will be spent on sub-tasks of the project over the period of the summer. While this is only preliminary, we will use it to help monitor your progress throughout the program. Also understand that during the project you will issue weekly progress reports against that plan on your blog.

  • 05-25: Get aquainted with the code and coding style of networkx
  • 06-01: Design and test the schema using queries and sample graphs
  • 06-08: Design Generic Functions for manipulating the database
  • 06-15: Multi level - indexing of databse using B+ Trees for efficient handling in case of larger size of graph
  • 06-22: Cache Implementation
  • 06-29: ~Mid term evaluation.
  • 07-06: Fixes of mid term evaluation
  • 07-13: Fixes of mid term evaluation
  • 07-20: Evaluating the code and all the test cases.
  • 07-27: Evaluating the code and all the test cases.
  • 08-03: Free for fixes
  • 08-11: Free for fixes And evaluation
  • 08-18: Evaluation week