정적·동적 동치성과 백트래킹 프루닝을 이용한 부분그래프 매칭 연구

Subgraph Matching with Static/Dynamic Equivalences and Pruning

연구 내용

정적·동적 동치성과 시간 제약을 활용해 탐색 공간을 줄이고 연속 환경에서 패턴을 탐지하는 부분그래프 매칭 연구

그래프 데이터에서 질의 패턴을 찾는 subgraph matching을 동적·시간 제약 환경까지 확장합니다. 데이터 그래프와 질의 그래프 간 동치성을 정적/동적으로 분해하여 불필요한 매칭 후보를 제거하고, 연속 질의에서는 backtracking 과정에 temporal 정보 기반의 pruning을 적용합니다. time-constrained matchable edge 같은 필터링 기법을 통해 엄격한 부분순서를 만족하는 엣지 선택을 효율적으로 결정합니다. 또한 delta query compilation 관점에서 continuous subgraph matching 코드를 논리·물리 플랜에서 생성하여 구현 편차로 인한 비교 왜곡을 줄입니다. 이러한 접근은 evolving graph 상의 실시간 패턴 탐지에 직접 연결됩니다.

관련 프로젝트

5건

연구 흐름

초기에는 그래프 매칭에서 후보 감소를 위해 static and dynamic equivalences를 활용하는 방식으로 탐색 효율을 개선했습니다. 이후 연속 그래프 환경으로 확장하면서 시간 제약 조건을 만족하는 매칭을 실시간으로 갱신하는 알고리즘을 개발했습니다. 2024년에는 time-constrained pruning과 matchable edge 필터링을 결합하여 backtracking 탐색 공간을 줄이는 방향으로 구체화했습니다. 동시에 기존 연구의 성능 비교가 구현 최적화에 크게 좌우될 수 있음을 분석하고, delta query 기반 공통 컴파일 프레임워크로 CSM 코드 생성 과정을 표준화하여 원인-결과를 분해해 해석하는 연구를 수행했습니다.

활용 가능성

활용 가능성은 알앤디써클 특화 AI 에이전트가 생성한 내용으로, 실제 연구 가능 여부는 연구실과의 논의가 필요합니다.

static equivalence pruning
dynamic equivalence filtering
continuous subgraph pattern detection
time-constrained real-time matching
temporal backtracking pruning
delta query compilation
fair method comparison framework
evolving graph query processing
graph fraud pattern monitoring
large-scale graph pattern mining