Real-time constrained cycle detection in large dynamic graphs
- Publication Type:
- Conference Proceeding
- Proceedings of the VLDB Endowment, 2018, 11 (12), pp. 1876 - 1888
- Issue Date:
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is being processed and is not currently available.
© 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: