PROJECT TITLE :

Improving I/O Complexity of Triangle Enumeration

ABSTRACT:

Many graph algorithms are now required to operate in external memory and deliver performance that does not significantly degrade with the scale of the problem in this era of big data. This is because performance should not be negatively impacted by the size of the problem. Triangle listing is an example of a specific field that frequently deals with graphs that are larger than RAM. In this field, the algorithms have to meticulously piece together edges from multiple partitions in order to identify cycles. Pagh and PCF are two competing proposals that have emerged in recent research; however, neither one of them is inherently superior to the other. Because so little is known about the I/O cost of PCF or how these methods stack up against one another, we have decided to conduct research into the properties of these algorithms, model their I/O cost, gain an understanding of their shortcomings, and shed light on the conditions under which one method is superior to the other. Because of this realization, we were able to design a novel framework that we have dubbed Trigon. Its I/O performance is superior to that of both of the techniques that came before it in all graphs and under all RAM conditions.