.png){kind=icon}
.png){kind=icon}
Return
FastAGEDs+: Fast Approximate Graph Entity Dependency Discovery
.png){kind=icon}
PRE
AI
DOI：10.1111/exsy.70152.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper addresses the novel and challenging domain of graph entity dependencies (GEDs) discovery, which aims to identify dependencies in large graphs that are nearly satisfied despite the presence of errors, exceptions and ambiguities in real-world data. We propose a unique error measure specifically designed for GED semantics and innovatively adapts concepts of disagreement and necessary sets to the realm of graph dependencies. Furthermore, we introduce the FastAGEDs+ algorithm, which significantly enhances efficiency in discovering approximate GEDs, employing a depth-first search strategy for optimal candidate space traversal. Incorporating an innovative pruning strategy, FastAGEDs+ efficiently narrows down the search space, significantly reducing computational overhead while maintaining accuracy. Through extensive experimentation on real-world graphs, we demonstrate the feasibility and scalability of our approach, offering substantial improvements in data quality and management practices.
Keywords:
approximate dependency discovery
depth-first search
error measurement in graphs
pruning strategy
Journal
IF:
2.3
Papers:
2.5K
Citations:
3.8K
Organization
View more organizations