Aot: pushing the efficiency boundary of main-memory triangle listing
- Publisher:
- Springer International Publishing
- Publication Type:
- Journal Article
- Citation:
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2020, 12113 LNCS, pp. 516-533
- Issue Date:
- 2020-01-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| Yu2020_Chapter_AOTPushingTheEfficiencyBoundar.pdf | Accepted version | 643.95 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© Springer Nature Switzerland AG 2020. Triangle listing is an important topic significant in many practical applications. Efficient algorithms exist for the task of triangle listing. Recent algorithms leverage an orientation framework, which can be thought of as mapping an undirected graph to a directed acylic graph, namely oriented graph, with respect to any global vertex order. In this paper, we propose an adaptive orientation technique that satisfies the orientation technique but refines it by traversing carefully based on the out-degree of the vertices in the oriented graph during the computation of triangles. Based on this adaptive orientation technique, we design a new algorithm, namely AOT, to enhance the edge-iterator listing paradigm. We also make improvements to the performance of AOT by exploiting the local order within the adjacent list of the vertices. We show that AOT is the first work which can achieve best performance in terms of both practical performance and theoretical time complexity. Our comprehensive experiments over 16 real-life large graphs show a superior performance of our AOT algorithm when compared against the state-of-the-art, especially for massive graphs with billions of edges. Theoretically, we show that our proposed algorithm has a time complexity of $$\varTheta (\sum _{ \langle u,v \rangle \in \mathbf {E} } \min \{ deg^{+}(u),deg^{+}(v)\}))$$, where $$\mathbf {E}$$ and $$deg^{+}(x)$$ denote the set of directed edges in an oriented graph and the out-degree of vertex x respectively. As to our best knowledge, this is the best time complexity among in-memory triangle listing algorithms.
Please use this identifier to cite or link to this item: