Projects per year
Abstract
Graph Pattern based Node Matching (GPNM) is to find all the matches of the nodes in a data graph GD based on a given pattern graph GP. GPNM has become increasingly important in many applications, e.g., group finding and expert recommendation. In real scenarios, both GP and GD are updated frequently. However, the existing GPNM methods either need to perform a new GPNM procedure from scratch to deliver the node matching results based on the updated GP and GD or incrementally perform the GPNM procedure for each of the updates, leading to low efficiency. Therefore, there is a pressing need for a new method to efficiently deliver the node matching results on the updated graphs. In this paper, we first analyze and detect the elimination relationships between the updates. Then, we construct an Elimination Hierarchy Tree (EH-Tree) to index these elimination relationships. In order to speed up the GPNM process, we propose a graph partition method and then propose a new updates-aware GPNM method, called UA-GPNM, considering the single-graph elimination relationships among the updates in a single graph of GP or GD, and also the cross-graph elimination relationships between the updates in GP and the updates in GD. UA-GPNM first delivers the GPNM result of an initial query, and then delivers the GPNM result of a subsequent query, based on the initial GPNM result and the multiple updates that occur between two queries. The experimental results on five real-world social graphs demonstrate that our proposed UA-GPNM is much more efficient than the state-of-the-art GPNM methods.
Original language | English |
---|---|
Title of host publication | Proceedings - 2020 IEEE 36th International Conference on Data Engineering, ICDE 2020 |
Place of Publication | Piscataway, NJ |
Publisher | Institute of Electrical and Electronics Engineers (IEEE) |
Pages | 697-708 |
Number of pages | 12 |
ISBN (Electronic) | 9781728129037 |
DOIs | |
Publication status | Published - 2020 |
Event | 36th IEEE International Conference on Data Engineering, ICDE 2020 - Dallas, United States Duration: 20 Apr 2020 → 24 Apr 2020 |
Publication series
Name | Proceedings - International Conference on Data Engineering |
---|---|
Volume | 2020-April |
ISSN (Print) | 1084-4627 |
Conference
Conference | 36th IEEE International Conference on Data Engineering, ICDE 2020 |
---|---|
Country/Territory | United States |
City | Dallas |
Period | 20/04/20 → 24/04/20 |
Keywords
- Pattern matching
- Indexes
- Social network services
- Collaboration
- Query processing
- Fans
- Periodic structures
Projects
- 1 Finished
-
Reputation-based Trust Management in Crowdsourcing Environments
Wang, Y., Sheng, M., Orgun, M., MQRES (International), M. & MQRES, M.
1/01/18 → 31/12/20
Project: Research