Luận án tiến sĩ: Khai thác tập mục hữu ích cao trên tính toán song song

Độ hữu ích được tính bằng tích của số lượng và đơn giá hạng mục. Công thức này áp dụng cho từng hạng mục trong giao dịch. Tổng độ hữu ích của tập mục là tổng độ hữu ích các thành phần. Ngưỡng tối thiểu được thiết lập để lọc kết quả. Chỉ các tập mục vượt ngưỡng này được coi là hữu ích cao. Phương pháp này cho phép đánh giá chính xác giá trị thực tế.

HUIM được ứng dụng rộng rãi trong phân tích giỏ hàng bán lẻ. Doanh nghiệp xác định được các combo sản phẩm sinh lời cao. Ngành tài chính sử dụng HUIM để phát hiện giao dịch có giá trị. Y tế áp dụng khai thác tập mục hữu ích trong phân tích điều trị. Marketing tận dụng HUIM để tối ưu chiến lược khuyến mãi. Các ứng dụng này đều yêu cầu xử lý dữ liệu lớn với tốc độ cao.

Không gian tìm kiếm của HUIM rất lớn và phức tạp. Tính chất downward closure không áp dụng như tập phổ biến. Tập con của tập hữu ích cao có thể không hữu ích cao. Điều này làm tăng độ phức tạp tính toán đáng kể. Chi phí quét cơ sở dữ liệu nhiều lần rất tốn kém. Yêu cầu bộ nhớ lớn để lưu trữ cấu trúc dữ liệu trung gian. Các thách thức này đòi hỏi giải pháp tối ưu và song song hóa.

CPU đa nhân cho phép thực thi nhiều tác vụ song song. Mỗi nhân xử lý một phần không gian tìm kiếm độc lập. Bộ nhớ cache được chia sẻ giữa các nhân tăng tốc truy xuất. Luồng xử lý được phân bổ tự động bởi hệ điều hành. Mô hình shared memory giúp đồng bộ dữ liệu hiệu quả. Kỹ thuật này phù hợp với CSDL vừa và nhỏ trên một máy chủ.

MapReduce chia nhỏ công việc thành giai đoạn Map và Reduce. Giai đoạn Map xử lý song song các phân vùng dữ liệu. Kết quả trung gian được shuffle và sắp xếp theo key. Giai đoạn Reduce tổng hợp kết quả từ các mapper. Framework này xử lý tốt dữ liệu quy mô lớn trên cluster. Hadoop triển khai MapReduce với khả năng chịu lỗi cao.

Spark cung cấp xử lý in-memory nhanh hơn MapReduce. RDD (Resilient Distributed Datasets) là cấu trúc dữ liệu cốt lõi. Các phép biến đổi trên RDD được thực thi song song. Spark hỗ trợ caching dữ liệu giữa các iteration. MLlib cung cấp thư viện data mining tối ưu. Spark thích hợp cho thuật toán HUIM lặp nhiều lần.

Độ hữu ích động cho phép giá trị hạng mục thay đổi theo giao dịch. Mỗi giao dịch có bảng giá riêng cho các hạng mục. Mô hình này phản ánh khuyến mãi, giảm giá theo thời điểm. Tính toán độ hữu ích phức tạp hơn mô hình tĩnh. Cấu trúc lưu trữ cần được thiết kế để truy xuất nhanh. Phương pháp này tăng tính thực tế của kết quả khai thác.

iEFIM-Closed mở rộng EFIM cho khai thác tập đóng. Tập đóng là tập không có tập cha nào có cùng độ hữu ích. Số lượng tập đóng nhỏ hơn nhiều so với tất cả tập hữu ích cao. Thuật toán sử dụng cấu trúc utility-bin-array cho tính toán nhanh. Chiến lược merge transaction giảm kích thước CSDL hiệu quả. Kết quả thu được ngắn gọn nhưng đầy đủ thông tin.

Quét CSDL nhiều lần là chi phí lớn nhất trong HUIM. Phương pháp projection tạo CSDL con cho mỗi nhánh tìm kiếm. Utility-list lưu trữ thông tin cần thiết để tính độ hữu ích. Kỹ thuật này cho phép tính toán mà không cần quét lại CSDL. Transaction-weighted utilization làm upper-bound cho tỉa sớm. Các tối ưu này giảm đáng kể thời gian thực thi.

CSDL phân cấp tổ chức hạng mục theo taxonomy tree. Hạng mục mức thấp là con của hạng mục mức cao. Ví dụ: Dell Laptop là con của Laptop, là con của Electronics. Mỗi mức phân cấp cung cấp góc nhìn khác về dữ liệu. Khai thác đa mức tìm pattern ở tất cả các mức. Cấu trúc này phổ biến trong bán lẻ và phân loại sản phẩm.

Không gian tìm kiếm được phân chia thành các phân vùng độc lập. Mỗi luồng xử lý một phân vùng trên một nhân CPU. Thread pool quản lý tập luồng worker hiệu quả. Task queue lưu trữ các công việc chờ xử lý. Kết quả từ các luồng được merge trong giai đoạn cuối. Mô hình này tận dụng tối đa sức mạnh CPU đa nhân.

Work-stealing cho phép luồng nhàn lấy việc từ luồng bận. Mỗi luồng có hàng đợi công việc riêng (deque). Luồng lấy công việc từ đầu deque của mình. Luồng khác steal từ cuối deque khi hết việc. Kỹ thuật này giảm contention và tăng throughput. Cân bằng tải động cải thiện hiệu suất tổng thể.

CSDL được chia thành các phân vùng cho các luồng xử lý. Mỗi luồng quét phân vùng của mình để tính TWU cục bộ. Kết quả cục bộ được merge để có TWU toàn cục. Phân vùng dữ liệu cần cân bằng để tránh luồng nhàn rỗi. Lock-free data structure giảm contention khi merge. Giai đoạn này giảm thời gian quét đáng kể.

Utility-list của các hạng mục được xây dựng đồng thời. Mỗi luồng xử lý một tập hạng mục riêng biệt. Concurrent hash map lưu trữ utility-list an toàn. Memory allocation được tối ưu để giảm fragmentation. Parallel construction giảm thời gian chuẩn bị dữ liệu. Cấu trúc này sẵn sàng cho giai đoạn tìm kiếm.

Task scheduler ưu tiên công việc có chi phí lớn trước. Công việc nhỏ được gom lại để giảm overhead tạo luồng. Heuristic dựa trên kích thước projected database. Luồng được gán công việc dựa trên tải hiện tại. Adaptive scheduling điều chỉnh theo runtime statistics. Chiến lược này giảm thiểu thời gian chờ và tăng throughput.

Thời gian chạy là tiêu chí quan trọng nhất đánh giá hiệu năng. Mô hình song song giảm 60-80% thời gian so với tuần tự. Speedup đạt 3.5x với 4 nhân, 7.2x với 8 nhân. Hiệu quả song song giảm dần do overhead và synchronization. CSDL lớn hơn cho speedup tốt hơn do amortize overhead. Kết quả này chứng minh hiệu quả của song song hóa.

Bộ nhớ tăng tỷ lệ thuận với số luồng song song. Shared data structure giúp kiểm soát memory overhead. Peak memory chỉ tăng 20-30% so với phiên bản tuần tự. Garbage collection được tối ưu để giảm pause time. Memory pool technique tái sử dụng allocation hiệu quả. Trade-off giữa thời gian và bộ nhớ được cân bằng tốt.

Scalability đo khả năng tăng hiệu năng khi thêm tài nguyên. Strong scaling test với CSDL cố định, tăng số nhân. Weak scaling test với tăng cả CSDL và số nhân cùng tỷ lệ. Kết quả cho thấy strong scaling tốt đến 8-12 nhân. Weak scaling duy trì hiệu năng ổn định khi tăng quy mô. Mô hình phù hợp cho triển khai trên hệ thống lớn.