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ơ $\mathbf {a} =(a_{1},\dots ,a_{n})$ ban đầu được khởi tạo bằng vectơ $\mathbf {0}$, và dòng dữ liệu là một chuỗi các thay đổi của vectơ $\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ơ $\mathbf {a}$ bằng bộ nhớ nhỏ hơn rất nhiều bộ nhớ cần thiết để lưu trữ vectơ $\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ố $\langle i,c\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ố $\langle i,c\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ố $\mathbf {a}$ được định nghĩa là $F_{k}(\mathbf {a} )=\sum _{i=1}^{n}a_{i}^{k}$.

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

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 Karp, Papadimitriou & Shenker (2003)
• 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ố $\mathbf {a}$ được định nghĩa là $H(\mathbf {a} )=\sum _{i=1}^{n}{\frac {a_{i}}{m}}\log {a_{i}/m}$, trong đó $m=\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 Lall và đồng nghiệp (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.

Tham khảo

• Alon, Noga; Matias, Yossi; Szegedy, Mario (1999), “The space complexity of approximating the frequency moments”, Journal of Computer and System Sciences, 58 (1): 137–147, doi:10.1006/jcss.1997.1545, ISSN 0022-0000. First published as Alon, Noga; Matias, Yossi; Szegedy, Mario (1996), “The space complexity of approximating the frequency moments”, Proceedings of the 28th ACM Symposium on Theory of Computing (STOC 1996), tr. 20–29, CiteSeerX 10.1.1.131.4984, doi:10.1145/237814.237823, ISBN 978-0-89791-785-8, S2CID 1627911.
• Babcock, Brian; Babu, Shivnath; Datar, Mayur; Motwani, Rajeev; Widom, Jennifer (2002), “Models and issues in data stream systems”, Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2002) (PDF), tr. 1–16, CiteSeerX 10.1.1.138.190, doi:10.1145/543613.543615, ISBN 978-1581135077, S2CID 2071130, Bản gốc (PDF) lưu trữ ngày 9 tháng 7 năm 2017, truy cập ngày 8 tháng 8 năm 2022.
• Gilbert, A. C.; Kotidis, Y.; Muthukrishnan, S.; Strauss, M. J. (2001), “Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries” (PDF), Proceedings of the International Conference on Very Large Data Bases: 79–88.
• Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010). “An optimal algorithm for the distinct elements problem”. Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. PODS '10. New York, NY, USA: ACM. tr. 41–52. CiteSeerX 10.1.1.164.142. doi:10.1145/1807085.1807094. ISBN 978-1-4503-0033-9. S2CID 10006932..
• Karp, R. M.; Papadimitriou, C. H.; Shenker, S. (2003), “A simple algorithm for finding frequent elements in streams and bags”, ACM Transactions on Database Systems, 28 (1): 51–55, CiteSeerX 10.1.1.116.8530, doi:10.1145/762471.762473, S2CID 952840.
• Lall, Ashwin; Sekar, Vyas; Ogihara, Mitsunori; Xu, Jun; Zhang, Hui (2006), “Data streaming algorithms for estimating entropy of network traffic”, Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems (ACM SIGMETRICS 2006) (PDF), tr. 145, doi:10.1145/1140277.1140295, hdl:1802/2537, ISBN 978-1595933195, S2CID 240982.
• Xu, Jun (Jim) (2007), A Tutorial on Network Data Streaming (PDF).
• Heath, D., Kasif, S., Kosaraju, R., Salzberg, S., Sullivan, G., "Learning Nested Concepts With Limited Storage", Proceeding IJCAI'91 Proceedings of the 12th international joint conference on Artificial intelligence - Volume 2, Pages 777-782, Morgan Kaufmann Publishers Inc. San Francisco, CA, USA ©1991
• Morris, Robert (1978), “Counting large numbers of events in small registers”, Communications of the ACM, 21 (10): 840–842, doi:10.1145/359619.359627, S2CID 36226357.

Liên kết ngoài

• Bài giảng về streaming ở Princeton
• Thuật toán dòng dữ liệu cho các bài toán hình học, bởi Piotr Indyk, MIT
• Dagstuhl Workshop on Sublinear Algorithms
• IIT Kanpur Workshop on Data Streaming
• Danh sách các bài toán mở về dòng dữ liệu (tổng hợp bởi Andrew McGregor) từ thảo luận tại IITK Workshop on Algorithms for Data Streams, 2006.
• StreamIt - programming language and compilation infrastructure by MIT CSAIL Lưu trữ 2017-05-21 tại Wayback Machine
• IBM Spade - Stream Processing Application Declarative Engine
• IBM InfoSphere Streams

Hướng dẫn và bài báo tổng quan

• Data Stream Algorithms and Applications bởi S. Muthu Muthukrishnan
• Stanford STREAM project survey Lưu trữ 2012-02-22 tại Wayback Machine
• Ứng dụng trong mạng máy tính của bộ lọc Bloom, bởi Broder và Mitzenmacher
• Bài hướng dẫn của Xu tại SIGMETRICS 2007
• Bài giảng về dòng dữ liệu ở Barbados năm 2009, bởi Andrew McGregor và S. Muthu Muthukrishnan