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
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| p1876-qiu.pdf | Published version | 1.52 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not 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: