دانشگاه تبریز
فهرست نشریات دارای اعتبار وزارت علوم، تحقیقات و فناوری
پایگاه استنادی علوم جهان اسلام (ISC)

 آمار

تعداد نشریات45
تعداد شماره‌ها1,531
تعداد مقالات18,644
تعداد مشاهده مقاله61,332,652
تعداد دریافت فایل اصل مقاله22,090,947
Jowhari, Hossein, Rahmati, Arash. (1405). Space-efficient algorithms for counting triangles in data streams using trained oracles. سامانه مدیریت نشریات علمی, 14(3), 1267-1279. doi: 10.22034/cmde.2025.65909.3060
Hossein Jowhari; Arash Rahmati. "Space-efficient algorithms for counting triangles in data streams using trained oracles". سامانه مدیریت نشریات علمی, 14, 3, 1405, 1267-1279. doi: 10.22034/cmde.2025.65909.3060
Jowhari, Hossein, Rahmati, Arash. (1405). 'Space-efficient algorithms for counting triangles in data streams using trained oracles', سامانه مدیریت نشریات علمی, 14(3), pp. 1267-1279. doi: 10.22034/cmde.2025.65909.3060
Jowhari, Hossein, Rahmati, Arash. Space-efficient algorithms for counting triangles in data streams using trained oracles. سامانه مدیریت نشریات علمی, 1405; 14(3): 1267-1279. doi: 10.22034/cmde.2025.65909.3060

Space-efficient algorithms for counting triangles in data streams using trained oracles

Computational Methods for Differential Equations
مقاله 16، دوره 14، شماره 3، مهر 2026، صفحه 1267-1279    اصل مقاله (431.99 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22034/cmde.2025.65909.3060
نویسندگان
Hossein Jowhari* ؛ Arash Rahmati
Faculty of Mathematics, K. N. 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
مراجع
  • [1] M. Al Hasan and V. S. Dave, Triangle counting in large networks: a review, Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 8(2) (2018), e1226.
  • [2] N. Alon, R. Yuster, and U. Zwick, Finding and Counting Given Length Cycles, Algorithmica, 17(3) (1997), 209–223.
  • [3] Z. Bar-Yossef, R. Kumar, and D. Sivakumar, Reductions in streaming algorithms, with an application to counting triangles in graphs, in SODA, 2 (2002), 623–632.
  • [4] S. K. Bera and A. Chakrabarti, Towards tighter space bounds for counting triangles and other substructures in graph streams, in 34th Symposium on Theoretical Aspects of Computer Science, 2017.
  • [5] A. Chakrabarti, Data Stream Algorithms Lecture Notes, 2020.
  • [6] J. Y. Chen, T. Eden, P. Indyk, H. Lin, S. Narayanan, R. Rubinfeld, S. Silwal, T. Wagner, D. P. Woodruff, and M. Zhang, Triangle and four cycle counting with predictions in graph streams, arXiv preprint arXiv:2203.09572, 2022.
  • [7] G. Cormode and H. Jowhari, A second look at counting triangles in graph streams (corrected), Theoretical Computer Science, 683 (2017), 22–30.
  • [8] T. Eden, A. Levi, D. Ron, and C. Seshadhri, Approximately Counting Triangles in Sublinear Time, SIAM J. Comput., 46(5) (2017), 1603–1646.
  • [9] H. Fichtenberger and P. Peng, Approximately Counting Subgraphs in Data Streams, in Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, (2022), 413–425.
  • [10] R. Jayaram and J. Kallaugher, An optimal algorithm for triangle counting in the stream, arXiv preprint arXiv:2105.01785, 2021.
  • [11] H. Jowhari and M. Ghodsi, New streaming algorithms for counting triangles in graphs, in Computing and Com- binatorics: 11th Annual International Conference, COCOON 2005, (2005), 710–716.
  • [12] N. Kavassery–Parakkat, K. M. Hanjani, and A. Pavan, Improved triangle counting in graph streams: power of multi-sampling, in 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), (2018), 33–40.
  • [13] S. Kumar, W. L. Hamilton, J. Leskovec, and D. Jurafsky, Community interaction and conflict on the web, in Proceedings of the 2018 World Wide Web Conference on World Wide Web, (2018), 933–943.
  • [14] J. Leskovec, D. Huttenlocher, and J. Kleinberg, Governance in social media: A case study of the Wikipedia promotion process, in Proceedings of the International AAAI Conference on Web and Social Media, 4(1) (2010), 98–105.
  • [15] J. Leskovec, J. Kleinberg, and C. Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, in Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, (2005), 177–187.
  • [16] A. McGregor, S. Vorotnikova, and H. T. Vu, Better algorithms for counting triangles in data streams, in Pro- ceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, (2016), 401–411.
  • [17] R. A. Meyer, C. Musco, C. Musco, and D. P. Woodruff, Hutch++: Optimal Stochastic Trace Estimation, in 4th Symposium on Simplicity in Algorithms, SOSA 2021, (2021), 142–155.
  • [18] S. Muthukrishnan, Theory of data stream computing: where to go, in Proceedings of the 30th ACM SIGMOD- SIGACT-SIGART Symposium on Principles of Database Systems, (2011), 317–319.
  • [19] S. Muthukrishnan, Data streams: Algorithms and applications, Foundations and Trends in Theoretical Computer Science, 1(2) (2005), 117–236.
  • [20] R. Pagh and C. E. Tsourakakis, Colorful triangle counting and a mapreduce implementation, Information Processing Letters, 112(7) (2012), 277–281.
  • [21] A. Paranjape, A. R. Benson, and J. Leskovec, Motifs in temporal networks, in Proceedings of the tenth ACM international conference on web search and data mining, (2017), 601–610.
  • [22] A. Pavan, K. Tangwongsan, S. Tirthapura, and K.-L. Wu, Counting and Sampling Triangles from a Graph Stream, Proc. VLDB Endow., 6(14) (2013), 1870–1881.
  • [23] C. Seshadhri, A. Pinar, and T. G. Kolda, Fast triangle counting through wedge sampling, in Proceedings of the SIAM Conference on Data Mining, 4 (2013), 5.
  • [24] K. Shin, Wrs: Waiting room sampling for accurate triangle counting in real graph streams, in 2017 IEEE International Conference on Data Mining (ICDM), (2017), 1087–1092.
  • [25] K. Shin, J. Kim, B. Hooi, and C. Faloutsos, Think before you discard: Accurate triangle counting in graph streams with deletions, in Joint European Conference on Machine Learning and Knowledge Discovery in Databases, (2018), 141–157.
  • [26] L. D. Stefani, A. Epasto, M. Riondato, and E. Upfal, Triest: Counting local and global triangles in fully dynamic streams with fixed memory size, ACM Transactions on Knowledge Discovery from Data (TKDD), 11(4) (2017), 1–50.
  • [27] C. E. Tsourakakis, Fast Counting of Triangles in Large Real Networks without Counting: Algorithms and Laws, in Proceedings of the 8th IEEE International Conference on Data Mining (ICDM 2008), (2008), 608–617.
  • [28] J. S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), 11(1) (1985), 37–57.
آمار
تعداد مشاهده مقاله: 436
تعداد دریافت فایل اصل مقاله: 497


سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب