MỘT THUẬT TOÁN HIỆU QUẢ ĐỂ TRÍCH XUẤT TẬP SKYLINE

Tóm tắt

Khai thác tập hữu ích phổ biến thuộc đường chân trời (Skyline frequent-utility patterns (SFUPs)) là việc khám phá các tập mặt hàng (itemset) vượt trội hơn các tập mặt hàng khác về cả tần số và độ hữu ích trong cơ sở dữ liệu giao dịch. Trong những năm gần đây, nhiều thuật toán đã được đề xuất nhằm khai thác tập hữu ích phổ biến thuộc đường chân trời, trong đó SkyFUP là thuật toán hiệu quả nhất. Tuy nhiên, thuật toán SkyFUP vẫn còn những hạn chế cả về thời gian thực thi và không gian lưu trữ. Trong bài báo này, nhóm tác giả đề xuất thuật toán SkyMiner để khai thác tập SFUPs hiệu quả hơn bằng cách sử dụng cấu trúc lưu trữ utility-list kết hợp với các chiến lược cắt tỉa nhằm làm giảm đáng kể số lượng các ứng viên cần phải tìm kiếm trong quá trình khai thác. Kết quả thực nghiệm cho thấy thuật toán SkyMiner có hiệu suất thực thi tốt hơn thuật toán mới nhất là SkyFUP về thời gian thực thi, bộ nhớ sử dụng và số lượng các ứng viên được tạo ra.