Sublinear computation paradigm : algorithmic revolution in the big data era

Abstract

Cuốn sách truy cập mở này cung cấp cái nhìn tổng quan về nghiên cứu một mô hình mới gọi là “mô hình tính toán tuyến tính”, được đề xuất trong dự án nghiên cứu học thuật lớn kéo dài nhiều năm “Nền tảng của các thuật toán đổi mới cho dữ liệu lớn”. Dự án đó được thực hiện từ tháng 10 năm 2014 đến tháng 3 năm 2020, tại Nhật Bản. Để xử lý sự bùng nổ chưa từng có của các tập dữ liệu lớn trong nghiên cứu, công nghiệp và các lĩnh vực khác của xã hội, nhu cầu cấp thiết là phát triển các phương pháp và cách tiếp cận mới để phân tích dữ liệu lớn. Để đáp ứng nhu cầu này, những thay đổi mang tính đổi mới trong lý thuyết thuật toán cho dữ liệu lớn đang được theo đuổi. Ví dụ, các thuật toán thời gian đa thức cho đến nay vẫn được coi là “nhanh”, nhưng nếu thuật toán thời gian bậc hai được áp dụng cho tập dữ liệu lớn có quy mô petabyte hoặc lớn hơn thì sẽ gặp phải các vấn đề về tài nguyên tính toán hoặc thời gian chạy. Để giải quyết nút thắt cổ chai tính toán và thuật toán quan trọng này, cần có các thuật toán tuyến tính, cận tuyến tính và thời gian không đổi. Mô hình tính toán tuyến tính được đề xuất ở đây nhằm hỗ trợ đổi mới trong kỷ nguyên dữ liệu lớn. Nền tảng của các thuật toán đổi mới đã được tạo ra bằng cách phát triển các quy trình tính toán, cấu trúc dữ liệu và kỹ thuật mô hình hóa cho dữ liệu lớn. Dự án được tổ chức thành ba nhóm tập trung vào các thuật toán tuyến tính, cấu trúc dữ liệu tuyến tính và mô hình tuyến tính. Công trình đã cung cấp các kết quả nghiên cứu học thuật cấp cao có tính toán và thuật toán đáng quan tâm, được trình bày trong cuốn sách này. Cuốn sách bao gồm năm phần: Phần I, Về khái niệm mô hình tính toán tuyến tính; Phần II, III và IV xem xét kết quả lần lượt về các thuật toán tuyến tính, cấu trúc dữ liệu tuyến tính và mô hình tuyến tính; Phần V trình bày kết quả ứng dụng. Thông tin được trình bày ở đây sẽ truyền cảm hứng cho các nhà nghiên cứu làm việc trong lĩnh vực thuật toán hiện đại.