I am looking for data structures to store power-law (hence mostly sparse, but few dense too) graphs whose structure is continuously being modified, including new vertices being added and edge weights being modified.

Any pointers on potential data structures and their speed/space complexity will be greatly helpful!

Background info: I will be running iterative variational inference algorithms on the graph - so speed is important. And will be running them on a GPU - so space is important. But I cant yet apriori quantify their ratio (speed:space). So will experiment with different data structures to see what works. My current solution is to use a database (SQL etc) which gets updated continuously on the side by a parallel routine that spits data in COO format, and at the time of running an algorithm, I fetch it into a CSR format. In this case, the graph is not being current and I am not sure if these formats are good for power-law graphs.

  • $\begingroup$ Can you quantify the order of magnitude of 'large'? If you need to run them on GPU then there is certain limit of size and you are most likely spending time on fetching your data from disk anyway. $\endgroup$ – Andrew Au Feb 4 '16 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.