آمار
| تعداد نشریات | 45 |
| تعداد شماره‌ها | 1,381 |
| تعداد مقالات | 16,906 |
| تعداد مشاهده مقاله | 54,422,185 |
| تعداد دریافت فایل اصل مقاله | 17,098,580 |
Space-Efficient Algorithms for Counting Triangles in Data Streams Using Trained Oracles | ||
| Computational Methods for Differential Equations | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 02 خرداد 1404 اصل مقاله (1.17 M) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22034/cmde.2025.65909.3060 | ||
| نویسندگان | ||
| Hossein Jowhari* ؛ Arash Rahmati | ||
| Faculty of Mathematics, Khajeh Nasir Toosi University of Technology, Tehran, Iran. | ||
| چکیده | ||
| In this paper we study data stream algorithms for approximating the number of triangles under the assumption that the algorithm has access to an oracle that answers certain queries about the input graph. Specifically we present algorithms that process the input graph given as a sequence of edges (or vertices) and output an estimate of the number of triangles in the given graph. We consider algorithms that, while processing the input stream, have access to a degree oracle (given a vertex, the oracle provides the degree of the queried vertex) or an edge-triangle oracle where the oracle answers whether an edge $(u,v)$ participates in a triangle or not. We implement two single-pass algorithms and the associated oracles in both the edge-arrival and the vertex-arrival models, and evaluate their performance on real-world datasets. Despite the inaccuracies of the oracles used in our experiments, our study shows that they can improve the performance of state-of-the-art triangle counting algorithms on some real-world graphs. | ||
| کلیدواژه‌ها | ||
| Counting Triangles؛ Data Stream Model؛ Learning-Augmented Algorithms | ||
|
آمار تعداد مشاهده مقاله: 112 تعداد دریافت فایل اصل مقاله: 113 |
||