{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T19:46:46Z","timestamp":1742932006034,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031226762"},{"type":"electronic","value":"9783031226779"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-22677-9_12","type":"book-chapter","created":{"date-parts":[[2023,1,10]],"date-time":"2023-01-10T09:04:32Z","timestamp":1673341472000},"page":"214-232","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["SPAC: Scalable Pattern Approximate Counting in\u00a0Graph Mining"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1802-5188","authenticated-orcid":false,"given":"Ruini","family":"Xue","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yijun","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shengbo","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yunxiang","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5551-9796","authenticated-orcid":false,"given":"Wenhong","family":"Tian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weimin","family":"Zheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,11]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Abou-Rjeili, A., Karypis, G.: Multilevel algorithms for partitioning power-law graphs. In: Proceedings of the 20th International Conference on Parallel and Distributed Processing. IPDPS 2006, p. 124. IEEE Computer Society, USA (2006)","DOI":"10.1109\/IPDPS.2006.1639360"},{"key":"12_CR2","doi-asserted-by":"publisher","unstructured":"Agarwal, S., Mozafari, B., Panda, A., Milner, H., Madden, S., Stoica, I.: BlinkDB: queries with bounded errors and bounded response times on very large data. In: Proceedings of the 8th ACM European Conference on Computer Systems. EuroSys 2013, pp. 29\u201342. Association for Computing Machinery, New York (2013). https:\/\/doi.org\/10.1145\/2465351.2465355","DOI":"10.1145\/2465351.2465355"},{"key":"12_CR3","doi-asserted-by":"publisher","unstructured":"Ahmed, N.K., Duffield, N., Neville, J., Kompella, R.: Graph sample and hold: a framework for big-graph analytics. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD 2014, pp. 1446\u20131455. Association for Computing Machinery, New York (2014). https:\/\/doi.org\/10.1145\/2623330.2623757","DOI":"10.1145\/2623330.2623757"},{"key":"12_CR4","unstructured":"Ananthanarayanan, G., Hung, M.C.C., Ren, X., Stoica, I., Wierman, A., Yu, M.: GRASS: trimming stragglers in approximation analytics. In: 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 14), pp. 289\u2013302. USENIX Association, Seattle, April 2014. https:\/\/www.usenix.org\/conference\/nsdi14\/technical-sessions\/presentation\/ananthanarayanan"},{"key":"12_CR5","unstructured":"Barab\u00e1si, A.L., P\u00f3sfai, M.: Network Science. Cambridge University Press, Cambridge (2016). http:\/\/barabasi.com\/networksciencebook\/"},{"key":"12_CR6","doi-asserted-by":"publisher","unstructured":"Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575\u2013577 (1973). https:\/\/doi.org\/10.1145\/362342.362367","DOI":"10.1145\/362342.362367"},{"issue":"1","key":"12_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s000260300002","volume":"7","author":"F Chung","year":"2003","unstructured":"Chung, F., Lu, L., Vu, V.: Eigenvalues of random power law graphs. Ann. Comb. 7(1), 21\u201333 (2003)","journal-title":"Ann. Comb."},{"key":"12_CR8","doi-asserted-by":"publisher","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing. STOC 1971, pp. 151\u2013158. Association for Computing Machinery, New York (1971). https:\/\/doi.org\/10.1145\/800157.805047","DOI":"10.1145\/800157.805047"},{"key":"12_CR9","doi-asserted-by":"publisher","unstructured":"Danisch, M., Balalau, O., Sozio, M.: Listing k-cliques in sparse real-world graphs*. In: Proceedings of the 2018 World Wide Web Conference. WWW 2018, pp. 589\u2013598. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE (2018). https:\/\/doi.org\/10.1145\/3178876.3186125","DOI":"10.1145\/3178876.3186125"},{"key":"12_CR10","doi-asserted-by":"publisher","unstructured":"Elseidy, M., Abdelhamid, E., Skiadopoulos, S., Kalnis, P.: Grami: frequent subgraph and pattern mining in a single large graph. Proc. VLDB Endow. 7(7), 517\u2013528 (2014). https:\/\/doi.org\/10.14778\/2732286.2732289","DOI":"10.14778\/2732286.2732289"},{"key":"12_CR11","doi-asserted-by":"publisher","unstructured":"Flajolet, P., Fusy, \u00c9., Gandouet, O., Meunier, F.: HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. In: Jacquet, P. (ed.) AofA: Analysis of Algorithms. DMTCS Proceedings, vol. DMTCS Proceedings, vol. AH, 2007 Conference on Analysis of Algorithms (AofA 2007), pp. 137\u2013156. Discrete Mathematics and Theoretical Computer Science, Juan les Pins, France, June 2007. https:\/\/doi.org\/10.46298\/dmtcs.3545, https:\/\/hal.inria.fr\/hal-00406166","DOI":"10.46298\/dmtcs.3545"},{"key":"12_CR12","doi-asserted-by":"publisher","unstructured":"Gao, P., van der Hofstad, R., Southwell, A., Stegehuis, C.: Counting triangles in power-law uniform random graphs (2018). https:\/\/doi.org\/10.48550\/ARXIV.1812.04289, https:\/\/arxiv.org\/abs\/1812.04289","DOI":"10.48550\/ARXIV.1812.04289"},{"key":"12_CR13","doi-asserted-by":"publisher","unstructured":"Gemulla, R., Lehner, W.: Sampling time-based sliding windows in bounded space. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. SIGMOD 2008, pp. 379\u2013392, Association for Computing Machinery, New York (2008). https:\/\/doi.org\/10.1145\/1376616.1376657","DOI":"10.1145\/1376616.1376657"},{"key":"12_CR14","unstructured":"Gonzalez, J.E., Xin, R.S., Dave, A., Crankshaw, D., Franklin, M.J., Stoica, I.: GraphX: graph processing in a distributed dataflow framework. In: 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2014), pp. 599\u2013613. USENIX Association, Broomfield, October 2014. https:\/\/www.usenix.org\/conference\/osdi14\/technical-sessions\/presentation\/gonzalez"},{"key":"12_CR15","doi-asserted-by":"publisher","unstructured":"Gou, X., Zou, L.: Sliding window-based approximate triangle counting over streaming graphs with duplicate edges. In: Proceedings of the 2021 International Conference on Management of Data. SIGMOD 2021, pp. 645\u2013657. Association for Computing Machinery, New York (2021). https:\/\/doi.org\/10.1145\/3448016.3452800","DOI":"10.1145\/3448016.3452800"},{"key":"12_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/978-3-540-71681-5_7","volume-title":"Research in Computational Molecular Biology","author":"JA Grochow","year":"2007","unstructured":"Grochow, J.A., Kellis, M.: Network motif discovery using subgraph enumeration and symmetry-breaking. In: Speed, T., Huang, H. (eds.) RECOMB 2007. LNCS, vol. 4453, pp. 92\u2013106. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-71681-5_7"},{"key":"12_CR17","unstructured":"Iyer, A.P., Liu, Z., Jin, X., Venkataraman, S., Braverman, V., Stoica, I.: ASAP: fast, approximate graph pattern mining at scale. In: 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2018), pp. 745\u2013761. USENIX Association, October 2018. https:\/\/www.usenix.org\/conference\/osdi18\/presentation\/iyer"},{"issue":"5","key":"12_CR18","doi-asserted-by":"publisher","first-page":"1225","DOI":"10.1007\/s10618-019-00630-6","volume":"33","author":"M Jung","year":"2019","unstructured":"Jung, M., Lim, Y., Lee, S., Kang, U.: FURL: fixed-memory and uncertainty reducing local triangle counting for multigraph streams. Data Min. Knowl. Disc. 33(5), 1225\u20131253 (2019). https:\/\/doi.org\/10.1007\/s10618-019-00630-6","journal-title":"Data Min. Knowl. Disc."},{"key":"12_CR19","doi-asserted-by":"publisher","unstructured":"Kashtan, N., Itzkovitz, S., Milo, R., Alon, U.: Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. Bioinformatics 20(11), 1746\u20131758 (2004). https:\/\/doi.org\/10.1093\/bioinformatics\/bth163","DOI":"10.1093\/bioinformatics\/bth163"},{"key":"12_CR20","doi-asserted-by":"publisher","unstructured":"Koutra, D., Jin, D., Ning, Y., Faloutsos, C.: Perseus: an interactive large-scale graph mining and visualization tool. Proc. VLDB Endow. 8(12), 1924\u20131927 (2015). https:\/\/doi.org\/10.14778\/2824032.2824102","DOI":"10.14778\/2824032.2824102"},{"issue":"1","key":"12_CR21","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1080\/15427951.2009.10129177","volume":"6","author":"J Leskovec","year":"2009","unstructured":"Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math. 6(1), 29\u2013123 (2009). https:\/\/doi.org\/10.1080\/15427951.2009.10129177","journal-title":"Internet Math."},{"key":"12_CR22","doi-asserted-by":"publisher","unstructured":"Lim, Y., Jung, M., Kang, U.: Memory-efficient and accurate sampling for counting local triangles in graph streams: from simple to multigraphs. ACM Trans. Knowl. Discov. Data 12(1) (2018). https:\/\/doi.org\/10.1145\/3022186","DOI":"10.1145\/3022186"},{"key":"12_CR23","unstructured":"McAuley, J., Leskovec, J.: Learning to discover social circles in ego networks. In: Proceedings of the 25th International Conference on Neural Information Processing Systems. NIPS 2012, vol. 1, pp. 539\u2013547. Curran Associates Inc., Red Hook (2012)"},{"issue":"5594","key":"12_CR24","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1126\/science.298.5594.824","volume":"298","author":"R Milo","year":"2002","unstructured":"Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network motifs: simple building blocks of complex networks. Science 298(5594), 824\u2013827 (2002). https:\/\/doi.org\/10.1126\/science.298.5594.824","journal-title":"Science"},{"key":"12_CR25","unstructured":"Montgomery, D.C., Peck, E.A., Vining, G.G.: Introduction to Linear Regression Analysis, 4th edn. Wiley, Hoboken (2006)"},{"key":"12_CR26","doi-asserted-by":"publisher","unstructured":"Pashanasangi, N., Seshadhri, C.: Faster and generalized temporal triangle counting, via degeneracy ordering. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. KDD 2021, pp. 1319\u20131328. Association for Computing Machinery, New York (2021). https:\/\/doi.org\/10.1145\/3447548.3467374","DOI":"10.1145\/3447548.3467374"},{"key":"12_CR27","doi-asserted-by":"publisher","unstructured":"Pr\u017eulj, N., Corneil, D.G., Jurisica, I.: Modeling interactome: scale-free or geometric? Bioinformatics 20(18), 3508\u20133515 (2004). https:\/\/doi.org\/10.1093\/bioinformatics\/bth436","DOI":"10.1093\/bioinformatics\/bth436"},{"key":"12_CR28","doi-asserted-by":"publisher","unstructured":"Ribeiro, P., Silva, F.: G-tries: an efficient data structure for discovering network motifs. In: Proceedings of the 2010 ACM Symposium on Applied Computing. SAC 2010, pp. 1559\u20131566. Association for Computing Machinery, New York (2010). https:\/\/doi.org\/10.1145\/1774088.1774422","DOI":"10.1145\/1774088.1774422"},{"key":"12_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/978-3-540-39718-2_23","volume-title":"The Semantic Web - ISWC 2003","author":"M Richardson","year":"2003","unstructured":"Richardson, M., Agrawal, R., Domingos, P.: Trust management for the semantic web. In: Fensel, D., Sycara, K., Mylopoulos, J. (eds.) ISWC 2003. LNCS, vol. 2870, pp. 351\u2013368. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-39718-2_23"},{"key":"12_CR30","doi-asserted-by":"publisher","unstructured":"Rozemberczki, B., Allen, C., Sarkar, R.: Multi-scale attributed node embedding (2019). https:\/\/doi.org\/10.48550\/ARXIV.1909.13021, https:\/\/arxiv.org\/abs\/1909.13021","DOI":"10.48550\/ARXIV.1909.13021"},{"key":"12_CR31","doi-asserted-by":"publisher","unstructured":"Rozemberczki, B., Sarkar, R.: Twitch gamers: a dataset for evaluating proximity preserving and structural role-based node embeddings (2021). https:\/\/doi.org\/10.48550\/ARXIV.2101.03091, https:\/\/arxiv.org\/abs\/2101.03091","DOI":"10.48550\/ARXIV.2101.03091"},{"key":"12_CR32","unstructured":"Takac, L., Z\u00e1bovsk\u00fd, M.: Data analysis in public social networks. In: International Scientific Conference and International Workshop Present Day Trends of Innovations, pp. 1\u20136, January 2012"},{"key":"12_CR33","doi-asserted-by":"publisher","unstructured":"Teixeira, C.H.C., Fonseca, A.J., Serafini, M., Siganos, G., Zaki, M.J., Aboulnaga, A.: Arabesque: a system for distributed graph mining. In: Proceedings of the 25th Symposium on Operating Systems Principles. SOSP 2015, pp. 425\u2013440. Association for Computing Machinery, New York (2015). https:\/\/doi.org\/10.1145\/2815400.2815410","DOI":"10.1145\/2815400.2815410"},{"key":"12_CR34","doi-asserted-by":"publisher","unstructured":"V\u00e1zquez, A., Pastor-Satorras, R., Vespignani, A.: Large-scale topological and dynamical properties of the internet. Phys. Rev. E 65, 066130 (2002). https:\/\/doi.org\/10.1103\/PhysRevE.65.066130, https:\/\/link.aps.org\/doi\/10.1103\/PhysRevE.65.066130","DOI":"10.1103\/PhysRevE.65.066130"},{"key":"12_CR35","doi-asserted-by":"publisher","unstructured":"Wang, P., Qi, Y., Sun, Y., Zhang, X., Tao, J., Guan, X.: Approximately counting triangles in large graph streams including edge duplicates with a fixed memory usage. Proc. VLDB Endow. 11(2), 162\u2013175 (2017). https:\/\/doi.org\/10.14778\/3149193.3149197","DOI":"10.14778\/3149193.3149197"},{"key":"12_CR36","doi-asserted-by":"publisher","unstructured":"Wu, M., et al.: Gram: scaling graph computation to the trillions. In: Proceedings of the Sixth ACM Symposium on Cloud Computing. SoCC 2015, pp. 408\u2013421. Association for Computing Machinery, New York (2015). https:\/\/doi.org\/10.1145\/2806777.2806849","DOI":"10.1145\/2806777.2806849"},{"key":"12_CR37","doi-asserted-by":"publisher","unstructured":"Yan, X., Han, J.: GSPAN: graph-based substructure pattern mining. In: 2002 IEEE International Conference on Data Mining, Proceedings, pp. 721\u2013724 (2002). https:\/\/doi.org\/10.1109\/ICDM.2002.1184038","DOI":"10.1109\/ICDM.2002.1184038"},{"issue":"1","key":"12_CR38","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s10115-013-0693-z","volume":"42","author":"J Yang","year":"2013","unstructured":"Yang, J., Leskovec, J.: Defining and evaluating network communities based on ground-truth. Knowl. Inf. Syst. 42(1), 181\u2013213 (2013). https:\/\/doi.org\/10.1007\/s10115-013-0693-z","journal-title":"Knowl. Inf. Syst."},{"key":"12_CR39","unstructured":"Zaharia, M., Chowdhury, M., Franklin, M.J., Shenker, S., Stoica, I.: Spark: cluster computing with working sets. In: Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing. HotCloud 2010, p. 10. USENIX Association, USA (2010)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Architectures for Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-22677-9_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,10]],"date-time":"2023-01-10T09:07:28Z","timestamp":1673341648000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-22677-9_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031226762","9783031226779"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-22677-9_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"11 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ICA3PP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Architectures for Parallel Processing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Copenhagen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Denmark","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 October 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 October 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ica3pp2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"91","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"36% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}