Việc khám phá các cấu trúc con thường xuyên bao gồm hai bước. Trong bước đầu tiên, nó có thể khiến các ứng viên thường xuyên tái cấu trúc. Tần suất của mọi ứng cử viên được kiểm tra trong bước thứ hai. Hầu hết các nghiên cứu về khám phá cấu trúc con thường xuyên tập trung vào việc tối ưu hóa bước đầu tiên vì bước thứ hai liên quan đến một bài kiểm tra đẳng cấu đồ thị con có độ phức tạp tính toán quá cao (tức là NP-đầy đủ).
Có nhiều phương pháp khác nhau để khai thác cấu trúc con thường xuyên như sau -
Phương pháp tiếp cận dựa trên Apriori - Các thuật toán khai thác cấu trúc con thường xuyên dựa trên Apriori gửi các tính năng tương tự với các thuật toán khai thác tập phổ biến thường xuyên dựa trên Apriori. Việc tìm kiếm đồ thị thường xuyên bắt đầu với đồ thị có “kích thước” nhỏ và tiến hành theo cách từ dưới lên bằng cách làm cho các ứng viên có thêm một đỉnh, cạnh hoặc đường dẫn. Việc biểu diễn kích thước đồ thị dựa trên thuật toán được sử dụng.
Độ phức tạp thiết kế chính của các thuật toán khai thác cấu trúc con dựa trên Apriori là bước tạo ứng viên. Sản lượng ứng viên trong khai thác tập phổ biến thường xuyên là trung thực. Ví dụ:giả sử chúng ta có hai tập phổ biến có kích thước-3:(abc) và (bcd).
Ứng cử viên tập phổ biến có kích thước-4 được tạo từ chúng dễ dàng (abcd), được thay đổi từ một phép nối. Tuy nhiên, vấn đề tạo ứng cử viên trong khai thác cấu trúc con thường xuyên khó hơn so với khai thác tập hợp vật phẩm thường xuyên, bởi vì có nhiều cách để kết hợp hai cấu trúc con.
Phương pháp tiếp cận theo mô hình tăng trưởng - Phương pháp dựa trên Apriori phải sử dụng chiến lược tìm kiếm trên hết (BFS) theo chiều rộng vì thế hệ ứng viên khôn ngoan ở cấp độ của nó. Để xác định xem một đồ thị size- (k + 1) có thường xuyên hay không, nó phải kiểm tra tất cả các đồ thị con size-k tương ứng của nó để có được giới hạn trên của tần suất của nó. Do đó, trước khi khai thác bất kỳ đồ thị con nào có kích thước- (k +1), phương pháp giống như Apriori thường phải hoàn thành việc khai thác các đồ thị con có kích thước-k.
Do đó, BFS là cần thiết cho cách tiếp cận giống như Apriori. Ngược lại, phương pháp tăng trưởng theo mẫu năng động hơn liên quan đến phương pháp tìm kiếm của nó. Nó có thể sử dụng tìm kiếm theo chiều rộng cũng như tìm kiếm theo chiều sâu (DFS), tìm kiếm thứ nhất tiêu tốn ít bộ nhớ hơn.
Biểu đồ tăng trưởng mô hình rất đơn giản, nhưng không hiệu quả. Nút thắt cổ chai nằm ở sự kém hiệu quả của việc mở rộng một đồ thị. Cùng một đồ thị có thể được tìm thấy nhiều lần. Ví dụ, có thể tồn tại n đồ thị (n - 1) -edge khác nhau có thể được mở rộng đến cùng một đồ thị n cạnh. Việc khám phá lặp lại cùng một đồ thị là không hiệu quả về mặt tính toán. Chúng tôi gọi một biểu đồ được phát hiện lần thứ hai là một biểu đồ trùng lặp.
Nó có thể giảm bớt việc tạo ra các đồ thị trùng lặp, mỗi đồ thị thường xuyên phải được mở rộng một cách thận trọng nhất có thể. Nguyên tắc này dẫn đến việc thiết kế một số thuật toán mới. Thuật toán bao trùm được thiết kế để giảm bớt việc tạo ra các đồ thị trùng lặp. Nó không cần phải tìm kiếm các đồ thị thường xuyên được phát hiện trước đó để phát hiện trùng lặp. Nó không mở rộng bất kỳ biểu đồ trùng lặp nào, nhưng vẫn đảm bảo việc phát hiện ra toàn bộ các biểu đồ thường xuyên.