Geo: 그래프 패턴 마이닝을 위한 쿼리 재작성 (Query Rewrite) 프레임워크

그래프 패턴 마이닝 (Graph pattern mining)은 그래프 데이터를 분석하는 데 있어 중요합니다. 그래프 마이닝 시스템은 일반적으로 NP-완전 (NP-complete) 문제인 부분 그래프 동형 이성 (subgraph isomorphism) 문제를 해결해야 하는 패턴 매칭 쿼리 (pattern matching queries)에 응답할 것을 요구합니다. 이를 해결하기 위해 도메인 전문가들은 서로 다른 패턴 간의 하위 구조적 유사성 (substructural similarities)을 활용하여 맞춤형 최적화 전략을 개발하곤 합니다. 이러한 최적화 도구들은 효과적일 수 있지만, 개발 과정이 까다롭기 때문에 서로 다른 최적화 전략 간의 상호작용을 탐색하는 데 한계가 있으며, 시간이 지남에 따라 추가적인 맞춤형 또는 일반적인 패턴 기반 등가성 (pattern-based equivalences)을 통합하는 등의 방식으로 최적화 도구를 지속적으로 개선하는 것을 제한합니다.

우리는 다양한 등가성 (equivalences) 간의 상호작용을 자동으로 관리하고, 최적화가 결과의 정확성을 유지하도록 보장하며, 하위 구조 등가성 (substructure equivalences) 관리를 단순화하는 Geo라고 불리는 프로그래밍 가능한 패턴 매칭 쿼리 최적화 도구를 제시합니다. Geo는 패턴 등가성을 재작성 규칙 (rewrite rules)으로 표현할 수 있는 단순하면서도 유연한 언어를 제공합니다. Geo는 등가성 포화 (equality saturation) 과정 동안 생성된 패턴의 정형 표현 (canonical representations)을 유지함으로써, 동형 패턴 (isomorphic patterns)의 구문론적 차이 (syntactic differences)로 인해 발생하는 문제를 방지합니다. 또한, 우리는 원하는 출력의 다양한 재구성 가능성 (reconstructability) 요구 사항을 보장하기 위해 등가성 전반에 걸쳐 출처 (provenance)를 추적하는 임베디드 재구성 가능성 (embedded reconstructability, EmRec)을 개발했습니다.

우리의 평가 결과에 따르면, Geo는 다양한 재작성 규칙의 복잡한 조합을 통해 새로운 쿼리 등가성을 발견할 수 있으며, 이를 통해 최적화된 쿼리가 이전 연구의 쿼리 대비 최대 99%의 비용 절감을 달성할 수 있음을 보여줍니다. 나아가 우리는 근사 패턴 매칭 (approximate pattern matching) 및 준클리크 마이닝 (quasi-clique mining)이라는 두 가지 대표적인 사례 연구에 Geo를 사용하여 실제 그래프 마이닝 문제의 속도를 높이는 효과를 테스트하였으며, 이러한 작업들을 최적화하는 데 매우 효과적이며 최대 71%의 비용 절감을 가능하게 함을 확인했습니다.