{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T07:12:20Z","timestamp":1784099540689,"version":"3.55.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,8]]},"abstract":"<jats:p>As graph data is prevalent for an increasing number of Internet applications, continuously monitoring structural patterns in dynamic graphs in order to generate real-time alerts and trigger prompt actions becomes critical for many applications. In this paper, we present a new system GraphS to efficiently detect constrained cycles in a dynamic graph, which is changing constantly, and return the satisfying cycles in real-time. A hot point based index is built and efficiently maintained for each query so as to greatly speed-up query time and achieve high system throughput. The GraphS system is developed at Alibaba to actively monitor various online fraudulent activities based on cycle detection. For a dynamic graph with hundreds of millions of edges and vertices, the system is capable to cope with a peak rate of tens of thousands of edge updates per second and find all the cycles with predefined constraints with a 99.9% latency of 20 milliseconds.<\/jats:p>","DOI":"10.14778\/3229863.3229874","type":"journal-article","created":{"date-parts":[[2018,9,10]],"date-time":"2018-09-10T12:12:28Z","timestamp":1536581548000},"page":"1876-1888","source":"Crossref","is-referenced-by-count":158,"title":["Real-time constrained cycle detection in large dynamic graphs"],"prefix":"10.14778","volume":"11","author":[{"given":"Xiafei","family":"Qiu","sequence":"first","affiliation":[{"name":"Alibaba Group"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wubin","family":"Cen","sequence":"additional","affiliation":[{"name":"Alibaba Group"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhengping","family":"Qian","sequence":"additional","affiliation":[{"name":"Alibaba Group"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"You","family":"Peng","sequence":"additional","affiliation":[{"name":"University of New South Wales"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Technology Sydney"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"University of New South Wales"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jingren","family":"Zhou","sequence":"additional","affiliation":[{"name":"Alibaba Group"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983712"},{"key":"e_1_2_1_3_1","unstructured":"Apache Flink. http:\/\/flink.apache.org\/.  Apache Flink. http:\/\/flink.apache.org\/."},{"key":"e_1_2_1_4_1","unstructured":"Apache Storm. http:\/\/storm.apache.org\/.  Apache Storm. http:\/\/storm.apache.org\/."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175268"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465286"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350247"},{"key":"e_1_2_1_8_1","first-page":"157","volume-title":"A selectivity based approach to continuous pattern detection in streaming graphs. In the proceeding of the International Conference on Extending Database Technology (EDBT)","author":"Choudhury S.","year":"2015","unstructured":"S. Choudhury , L. B. Holder , G. C. Jr., K. Agarwal , and J. Feo . A selectivity based approach to continuous pattern detection in streaming graphs. In the proceeding of the International Conference on Extending Database Technology (EDBT) , pages 157 -- 168 , 2015 . S. Choudhury, L. B. Holder, G. C. Jr., K. Agarwal, and J. Feo. A selectivity based approach to continuous pattern detection in streaming graphs. In the proceeding of the International Conference on Extending Database Technology (EDBT), pages 157--168, 2015."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989420"},{"key":"e_1_2_1_10_1","volume-title":"Matching structure and semantics: A survey on graph-based pattern matching. 6, 01","author":"Gallagher B.","year":"2006","unstructured":"B. Gallagher . Matching structure and semantics: A survey on graph-based pattern matching. 6, 01 2006 . B. Gallagher. Matching structure and semantics: A survey on graph-based pattern matching. 6, 01 2006."},{"key":"e_1_2_1_11_1","first-page":"599","volume-title":"Graphx: Graph processing in a distributed dataflow framework. In the proceeding of the USENIX Symposium on Operating Systems Design and Implementation (OSDI)","author":"Gonzalez J. E.","year":"2014","unstructured":"J. E. Gonzalez , R. S. Xin , A. Dave , D. Crankshaw , M. J. Franklin , and I. Stoica . Graphx: Graph processing in a distributed dataflow framework. In the proceeding of the USENIX Symposium on Operating Systems Design and Implementation (OSDI) , pages 599 -- 613 , 2014 . J. E. Gonzalez, R. S. Xin, A. Dave, D. Crankshaw, M. J. Franklin, and I. Stoica. Graphx: Graph processing in a distributed dataflow framework. In the proceeding of the USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 599--613, 2014."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732993"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556578"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056445"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1049\/el:19800212"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62251"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207218608920800"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00142"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1978.1084515"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544893"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90038-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2530531"},{"key":"e_1_2_1_24_1","unstructured":"The Rust Programming Language. https:\/\/www.rust-lang.org\/.  The Rust Programming Language. https:\/\/www.rust-lang.org\/."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732992"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920879"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_6"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035927"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612181"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3229863.3229874","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:15:11Z","timestamp":1672222511000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3229863.3229874"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8]]},"references-count":29,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["10.14778\/3229863.3229874"],"URL":"https:\/\/doi.org\/10.14778\/3229863.3229874","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,8]]}}}