Thuật toán dòng dữ liệu

Trong khoa học máy tính, thuật toán dòng dữ liệu là thuật toán để xử lý các dòng dữ liệu trong đó dữ liệu vào được cung cấp dưới dạng một dãy các phần tử, và chỉ có thể đọc một vài lần (thông thường đúng một lần). Các thuật toán này có bộ nhớ giới hạn (thường nhỏ hơn kích thước dữ liệu vào rất nhiều) và thời gian xử lý mỗi phần tử cũng bị giới hạn.
Do các giới hạn trên nên thuật toán cho dòng dữ liệu thường đưa ra một lời giải xấp xỉ dựa trên một cấu trúc dữ liệu tóm tắt hay tổng kết dữ liệu vào.

Lịch sử

Mặc dù các thuật toán dòng dữ liệu đã được nghiên cứu bởi Munro và Paterson cũng như Flajolet và Martin, mô hình này được định nghĩa và phổ biến rộng rãi trong một bài báo của Noga Alon, Yossi Matias, và Mario Szegedy. Nhờ bài báo này, các tác giả trên đã đoạt giải Gödel năm 2005 "cho những đóng góp cơ bản của họ cho thuật toán dòng dữ liệu". Từ đó đến nay, đã có nhiều công trình nghiên cứu về thuật toán dòng dữ liệu cho nhiều lĩnh vực khác nhau trong khoa học máy tính như lý thuyết, cơ sở dữ liệu, mạng, và xử lý ngôn ngữ tự nhiên.

Ví dụ

Một ví dụ của thuật toán dòng dữ liệu là việc tìm số bị thiếu trong một dãy số. Giả sử dữ liệu vào là một hoán vị của các số từ 1 đến n nhưng bị thiếu đúng một số. Bài toán đặt ra là cần tìm số bị thiếu. Một thuật toán đơn giản cho bài toán này là như sau. Khởi tạo một biến s bằng 0. Mỗi lần nhận được một số mới x từ dữ liệu vào, cộng x vào s. Đến cuối dòng dữ liệu, s đúng bằng tổng tất cả các số trong dữ liệu vào. Nếu không có số nào bị thiếu thì tổng đó đúng bằng tổng các số từ 1 đến n, tức là n·(n+1)/2. Do đó, n·(n+1)/2 - s chính là số bị thiếu. Như vậy thuật toán chỉ cần lưu trữ đúng một giá trị mà vẫn có thể giải được bài toán đặt ra bất kể kích thước bài toán là bao nhiêu (nếu tính bộ nhớ theo số bit thì bộ nhớ cần dùng là O(log n), vẫn nhỏ hơn kích thước dữ liệu vào là O(n log n) rất nhiều).

Mô hình

Trong mô hình dòng dữ liệu, dữ liệu vào được cung cấp dưới dạng một hay nhiều dãy các phần tử chỉ có thể đọc theo thứ tự định sẵn đúng một lần hoặc một vài lần.
Một phần đáng kể các nghiên cứu về dòng dữ liệu tập trung vào việc tính các số liệu thống kê về tần số các phần tử trong dòng dữ liệu khi tập hợp các tần số này là quá lớn không thể lưu trữ hết trong bộ nhớ. Ở đây dữ liệu vào có thể được mô hình bởi một vectơ  ban đầu được khởi tạo bằng vectơ , và dòng dữ liệu là một chuỗi các thay đổi của vectơ . Mục tiêu của thuật toán là tính một số liệu thống kê về vectơ  bằng bộ nhớ nhỏ hơn rất nhiều bộ nhớ cần thiết để lưu trữ vectơ . Có hai mô hình phổ biến là mô hình "máy tính tiền" và mô hình "cửa xoay".
Trong mô hình máy tính tiền, mỗi lần thay đổi được xác định bởi một cặp số , nghĩa là  được tăng lên  đơn vị ( là số dương). Một trường hợp đặc biệt hay được xem xét là  (chỉ được phép tăng lên 1).
Trong mô hình cửa xoay, mỗi lần thay đổi được xác định bởi một cặp số , nghĩa là  được cộng thêm số nguyên (có thể âm hoặc dương) . Trong mô hình cửa xoay nghiêm ngặt,  luôn không âm tại mọi thời điểm.
Ngoài ra, một số bài báo nghiên cứu về mô hình "cửa sổ dịch chuyển". Trong mô hình này, hàm cần tính là hàm của một số lượng cố định các phần tử cuối cùng (gọi là cửa sổ) của dòng dữ liệu. Khi các phần tử mới xuất hiện trong dòng dữ liệu, chúng được thêm vào cửa sổ và các phần tử cũ nhất trong cửa sổ bị loại ra.
Bên cạnh các bài toán về tần số, nhiều bài toán khác cũng được xem xét trong mô hình dòng dữ liệu. Nhiều bài toán đồ thị có thể giải được trong mô hình này khi ma trận kề hoặc danh sách kề của đồ thị được cung cấp dưới dạng dòng dữ liệu theo một thứ tự bất kì. Cũng có những bài toán phụ thuộc vào thứ tự các phần tử trong dòng dữ liệu chẳng hạn như đếm số nghịch thế của một hoán vị hay tìm độ dài dãy con tăng dài nhất.

Ứng dụng

Thuật toán dòng dữ liệu có nhiều ứng dụng trong mạng máy tính như tìm các dòng lớn, đếm số dòng khác nhau, ước lượng phân bố kích thước các dòng,v.v. Chúng cũng có ứng dụng trong cơ sở dữ liệu, chẳng hạn như ước lượng kích thước join.

Mô men tần số

Mô men tần số thứ  của một tập hợp các tần số  được định nghĩa là .
Mô men thứ nhất  đơn giản là tổng tất cả các tần số (nghĩa là tổng toàn bộ). Mô men thứ hai  được dùng để tính nhiều chỉ số thống kê của dữ liệu, chẳng hạn như hệ số Gini.  được định nghĩa là tần số của phần tử phổ biến nhất.
Bài báo của Alon, Matias & Szegedy (1999) mở đầu nghiên cứu về việc ước lượng các mô men tần số của dòng dữ liệu.

Đếm số phần tử khác nhau

Bài toán này yêu cầu đếm số phần tử khác nhau xuất hiện trong dòng dữ liệu (đôi khi gọi là mô men  dù tên gọi này không chính xác về mặt toán học). Thuật toán đầu tiên cho bài toán này là của Flajolet và Martin, và thuật toán tốt nhất hiện nay về thời gian và bộ nhớ là của D. Kane, J. Nelson và D. Woodruff. Nó dùng bộ nhớ O(ε^2 + log d) và thời gian cập nhật là O(1) trong trường hợp xấu nhất.

Entropy

Entropy (thực nghiệm) của tập hợp các tần số  được định nghĩa là , trong đó .
Việc ước lượng hàm số này cho dòng dữ liệu là chủ đề của nhiều bài báo chẳng hạn như của Lall et al. (2006) hay Chakrabarti, Cormode & McGregor (2010).

Chặn dưới

Đã có nhiều nghiên cứu về chặn dưới cho lượng bộ nhớ cần dùng của các thuật toán dòng dữ liệu. Cho đến nay, kĩ thuật phổ biến nhất để tìm ra các chặn dưới này là thông qua độ phức tạp liên lạc.