✨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 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 bằng 0. Mỗi lần nhận được một số mới từ dữ liệu vào, cộng vào . Đến cuối dòng dữ liệu, đú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 , tức là . Do đó, 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à , vẫn nhỏ hơn kích thước dữ liệu vào là 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ơ $\backslash mathbf\{a\}\; =\; (a\_1,\; \backslash dots,\; a\_n)$ ban đầu được khởi tạo bằng vectơ $\backslash mathbf\{0\}$, và dòng dữ liệu là một chuỗi các thay đổi của vectơ $\backslash mathbf\{a\}$. Mục tiêu của thuật toán là tính một số liệu thống kê về vectơ $\backslash mathbf\{a\}$ bằng bộ nhớ nhỏ hơn rất nhiều bộ nhớ cần thiết để lưu trữ vectơ $\backslash mathbf\{a\}$. 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ố $\backslash langle\; i,\; c\backslash rangle$, nghĩa là $a\_i$ được tăng lên $c$ đơn vị ($c$ là số dương). Một trường hợp đặc biệt hay được xem xét là $c\; =\; 1$ (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ố $\backslash langle\; i,\; c\backslash rangle$, nghĩa là $a\_i$ được cộng thêm số nguyên (có thể âm hoặc dương) $c$. Trong mô hình cửa xoay nghiêm ngặt, $a\_i$ 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.

Đánh giá

Hiệu quả của một thuật toán trên dòng dữ liệu được đánh giá bởi ba yếu tố cơ bản:

• Số lượt thuật toán đọc qua dòng dữ liệu.
• Lượng bộ nhớ cần dùng.
• Thời gian chạy của thuật toán. Các thuật toán này có nhiều điểm tương đồng với thuật toán trực tuyến do chúng đều phải đưa ra quyết định mà không được thấy hết toàn bộ dữ liệu vào nhưng cũng có nhiều điểm khác biệt. Thuật toán dòng dữ liệu tuy chỉ có bộ nhớ hữu hạn nhưng không phải quyết định ngay khi một phần tử mới xuất hiện trong dòng dữ liệu trong khi thuật toán trực tuyến không có giới hạn bộ nhớ nhưng phải quyết định ngay khi dữ liệu mới xuất hiện.

Ứ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ột vài bài toán dòng dữ liệu

Mô men tần số

Mô men tần số thứ $k$ của một tập hợp các tần số

Mô men thứ nhất $F\_1$ đơ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 $F$2 đượ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. $F${\infty} được định nghĩa là tần số của phần tử phổ biến nhất.

Bài báo của 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.

Phần tử phổ biến

Bài toán này yêu cầu tìm tất cả các phần tử xuất hiện nhiều lần trong dòng dữ liệu, chẳng hạn ít nhất 1% của toàn bộ dữ liệu. Một vài thuật toán cho bài toán này bao gồm

• Thuật toán
• Thuật toán Count-Min
• Thuật toán Count-sketch

Đế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 $F\_0$ 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ố $\backslash mathbf\{a\}$ được định nghĩa là $H(\backslash mathbf\{a\})\; =\; \backslash sum\_\{i=1\}^n\; \backslash frac\{a\_i\}\{m\}\backslash log\{a$i/m}, trong đó $m\; =\; \backslash sum${i=1}^n a_i.

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 hay .

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.