การค้นพบโครงสร้างย่อยที่พบบ่อยปกติประกอบด้วยสองขั้นตอน ขั้นแรก สร้างผู้สมัครโครงสร้างย่อยที่พบบ่อย ขั้นที่สอง ทดสอบความถี่ของทุกผู้สมัคร ส่วนใหญ่ของการศึกษาเกี่ยวกับการค้นพบโครงสร้างย่อยที่พบบ่อยเน้นที่การเพิ่มประสิทธิภาพขั้นตอนแรก เนื่องจากขั้นตอนที่สองเกี่ยวข้องกับการทดสอบ isomorphism ของ subgraph ที่ความซับซ้อนทางคำนวณสูงมาก (NP-complete)
มีหลายวิธีสำหรับการทำเหมืองโครงสร้างย่อยที่พบบ่อย ดังนี้:
แนวทางแบบ Apriori (Apriori-based Approach) — อัลกอริทึมการทำเหมืองโครงสร้างย่อยที่พบบ่อยแบบ Apriori มีลักษณะเหมือนกับอัลกอริทึมการทำเหมือง itemset ที่พบบ่อยแบบ Apriori การค้นหากราฟที่พบบ่อยเริ่มจากกราฟขนาด "เล็ก" และดำเนินต่อไปแบบ bottom-up โดยสร้างผู้สมัครที่มี vertex, edge, หรือ path เพิ่มขึ้น การแสดงขนาดกราฟขึ้นอยู่กับอัลกอริทึมที่ใช้
ความซับซ้อนหลักของการออกแบบอัลกอริทึมการทำเหมืองโครงสร้างย่อยแบบ Apriori คือขั้นตอนการสร้างผู้สมัคร (candidate generation) การสร้างผู้สมัครในการทำเหมือง itemset ที่พบบ่อยเป็นเรื่องตรงไปตรงมา ตัวอย่าง สมมติเรามี itemsets ที่พบบ่อยขนาด 3: (abc) และ (bcd) ผู้สมัคร itemset ขนาด 4 ที่สร้างจากพวกเขาคือ (abcd) ได้จาก join อย่างง่าย แต่ปัญหาการสร้างผู้สมัครในการทำเหมืองโครงสร้างย่อยที่พบบ่อยยากกว่าใน itemset มาก เนื่องจากมีหลายวิธีในการ join สองโครงสร้างย่อย
แนวทางการเติบโตของรูปแบบ (Pattern-Growth Approach) — แนวทาง Apriori ต้องใช้กลยุทธ์ breadth-first search (BFS) เนื่องจากการสร้างผู้สมัครแบบระดับต่อระดับ เพื่อตัดสินใจว่ากราฟขนาด (k+1) พบบ่อยหรือไม่ ต้องตรวจสอบ subgraphs ขนาด k ที่สอดคล้องทั้งหมดเพื่อหาขอบเขตบนของความถี่ ดังนั้น ก่อนทำเหมือง subgraph ขนาด (k+1) ใดๆ แนวทางแบบ Apriori มักต้องทำเหมือง subgraphs ขนาด k ให้เสร็จก่อน ดังนั้น BFS จำเป็นสำหรับแนวทางแบบ Apriori ในทางตรงข้าม วิธี pattern-growth ยืดหยุ่นมากกว่ากับวิธีค้นหา สามารถใช้ BFS และ depth-first search (DFS) ซึ่งใช้หน่วยความจำน้อยกว่า
Pattern Growth Graph เรียบง่ายแต่อไม่มีประสิทธิภาพ จุดคอขวดอยู่ที่การขยายกราฟที่ไม่มีประสิทธิภาพ กราฟเดียวกันอาจถูกค้นพบหลายครั้ง ตัวอย่าง อาจมีกราฟ (n-1)-edge n แบบต่างกันที่ขยายเป็นกราฟ n-edge เดียวกัน การค้นพบซ้ำของกราฟเดียวกันเป็นการคำนวณที่ไม่มีประสิทธิภาพ เราเรียกกราฟที่ถูกค้นพบครั้งที่สองว่า "กราฟซ้ำ" (duplicate graph)
เพื่อลดการสร้างกราฟซ้ำ แต่ละกราฟที่พบบ่อยควรขยายให้ conservative ที่สุดเท่าที่จะเป็นไปได้ หลักการนี้นำไปสู่การออกแบบอัลกอริทึมใหม่หลายตัว อัลกอริทึม spanning ออกแบบมาเพื่อลดการสร้างกราฟซ้ำ ไม่ต้องค้นหากราฟที่พบบ่อยก่อนหน้านี้เพื่อตรวจจับซ้ำ ไม่ขยายกราฟซ้ำใดๆ แต่ยังรับประกันการค้นพบชุดกราฟที่พบบ่อยครบถ้วน
