{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T19:26:42Z","timestamp":1793129202549,"version":"4.5.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>\n            Graphs are prevalent in many domains such as Bioinformatics, social networks, Web and cyber-security. Graph pattern mining has become an important tool in the management and analysis of complexly structured data, where example applications include indexing, clustering and classification. Existing graph mining algorithms have achieved great success by exploiting various properties in the\n            <jats:italic>pattern space<\/jats:italic>\n            . Unfortunately, due to the fundamental role subgraph isomorphism plays in these methods, they may all enter into a pitfall when the cost to enumerate a huge set of isomorphic embeddings blows up, especially in large graphs.\n          <\/jats:p>\n          <jats:p>\n            The solution we propose for this problem resorts to reduction on the\n            <jats:italic>data space<\/jats:italic>\n            . For each graph, we build a summary of it and mine this shrunk graph instead. Compared to other data reduction techniques that either reduce the number of transactions or compress between transactions, this new framework, called Summarize-Mine, suggests a third path by\n            <jats:italic>compressing within transactions<\/jats:italic>\n            . Summarize-Mine is effective in cutting down the size of graphs, thus decreasing the embedding enumeration cost. However, compression might lose patterns at the same time. We address this issue by generating\n            <jats:italic>randomized<\/jats:italic>\n            summaries and repeating the process for multiple rounds, where the main idea is that true patterns are unlikely to miss from all rounds. We provide strict probabilistic guarantees on pattern loss likelihood. Experiments on real malware trace data show that Summarize-Mine is very efficient, which can find interesting malware fingerprints that were not revealed previously.\n          <\/jats:p>","DOI":"10.14778\/1687627.1687711","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"742-753","source":"Crossref","is-referenced-by-count":46,"title":["Mining graph patterns efficiently via randomized summaries"],"prefix":"10.14778","volume":"2","author":[{"given":"Chen","family":"Chen","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cindy X.","family":"Lin","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matt","family":"Fredrikson","sequence":"additional","affiliation":[{"name":"University of Wisconsin at Madison"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mihai","family":"Christodorescu","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xifeng","family":"Yan","sequence":"additional","affiliation":[{"name":"University of California at Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiawei","family":"Han","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"487","volume-title":"VLDB","author":"Agrawal R.","year":"1994","unstructured":"R. Agrawal and R. Srikant . Fast algorithms for mining association rules in large databases . In VLDB , pages 487 -- 499 , 1994 . R. Agrawal and R. Srikant. Fast algorithms for mining association rules in large databases. In VLDB, pages 487--499, 1994."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132952.1132954"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.30"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150418"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1287624.1287628"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.127"},{"key":"e_1_2_1_7_1","volume-title":"VLDB","author":"Garofalakis M. N.","year":"2001","unstructured":"M. N. Garofalakis and P. B. Gibbons . Approximate query processing: Taming the terabytes (tutorial) . In VLDB , 2001 . M. N. Garofalakis and P. B. Gibbons. Approximate query processing: Taming the terabytes (tutorial). In VLDB, 2001."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335372"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2007.45"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2007.11"},{"key":"e_1_2_1_11_1","first-page":"169","volume-title":"KDD Workshop","author":"Holder L. B.","year":"1994","unstructured":"L. B. Holder , D. J. Cook , and S. Djoko . Substucture discovery in the subdue system . In KDD Workshop , pages 169 -- 180 , 1994 . L. B. Holder, D. J. Cook, and S. Djoko. Substucture discovery in the subdue system. In KDD Workshop, pages 169--180, 1994."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014123"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021726221443"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502533"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/645496.658027"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-005-0003-9"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453870"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376661"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081898"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166082"},{"key":"e_1_2_1_22_1","first-page":"405","volume-title":"ICDE","author":"Raghavan S.","year":"2003","unstructured":"S. Raghavan and H. Garcia-Molina . Representing web graphs . In ICDE , pages 405 -- 416 , 2003 . S. Raghavan and H. Garcia-Molina. Representing web graphs. In ICDE, pages 405--416, 2003."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2007.370404"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1135777.1135823"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376675"},{"key":"e_1_2_1_26_1","first-page":"134","volume-title":"VLDB","author":"Toivonen H.","year":"1996","unstructured":"H. Toivonen . Sampling large databases for association rules . In VLDB , pages 134 -- 145 , 1996 . H. Toivonen. Sampling large databases for association rules. In VLDB, pages 134--145, 1996."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376662"},{"key":"e_1_2_1_28_1","first-page":"721","volume-title":"ICDM","author":"Yan X.","year":"2002","unstructured":"X. Yan and J. Han . gSpan: Graph-based substructure pattern mining . In ICDM , pages 721 -- 724 , 2002 . X. Yan and J. Han. gSpan: Graph-based substructure pattern mining. In ICDM, pages 721--724, 2002."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007607"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/977401.978103"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687711","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:31:38Z","timestamp":1672227098000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687711"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687711"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687711","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}