Real-time constrained cycle detection in large dynamic graphs

Publication Type:
Conference Proceeding
Citation:
Proceedings of the VLDB Endowment, 2018, 11 (12), pp. 1876 - 1888
Issue Date:
2018-01-01
Filename Description Size
p1876-qiu.pdfPublished version1.52 MB
Adobe PDF
Full metadata record
© 2018 VLDB Endowment. 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.
Please use this identifier to cite or link to this item: