Thuật toán Tốt Nhất Mọi Thời Đại Được Phát hiện cho Dòng Dữ Liệu Khổng Lồ

Khó khăn khi đo lường nước từ một dây chảy lửa khi nó đang đánh vào bạn. Theo một khía cạnh, đó là thách thức của việc phân tích dữ liệu đồng truyền, đến với chúng ta như một dòng lớn và không bao giờ dừng lại. Nếu bạn đang trên Twitter theo dõi các tweet, bạn có thể muốn tuyên bố một thời gian ngắn, để bạn có thể hiểu được xu hướng là gì. Tuy nhiên, điều này không khả thi, vì vậy thay vào đó, bạn cần tìm cách đếm số hashtag ngay lập tức.

Các chương trình máy tính thực hiện những tính toán trên đường đi này được gọi là thuật toán truyền dữ liệu. Vì dữ liệu liên tục đến với họ và ở trong lượng lớn, họ cố gắng ghi lại bản chất của những gì họ đã thấy trong khi quên một cách chiến lược phần còn lại. Hơn 30 năm nay, các nhà khoa học máy tính đã nỗ lực xây dựng một thuật toán truyền dữ liệu tốt hơn. Mùa thu năm ngoái, một nhóm nghiên cứu đã phát minh ra một thuật toán gần như hoàn hảo.

“Chúng tôi đã phát triển một thuật toán mới đồng thời là tốt nhất” trên mọi khía cạnh hiệu suất, tuyên bố Jelani Nelson, một nhà khoa học máy tính tại Đại học Harvard và đồng tác giả của công trình với Kasper Green Larsen của Đại học Aarhus ở Đan Mạch, Huy Nguyen của Đại học Northeastern và Mikkel Thorup của Đại học Copenhagen.

Thuật toán truyền dữ liệu hàng đầu này hoạt động bằng cách ghi nhớ đủ để nói cho bạn biết những gì nó đã thấy nhiều nhất. Nó gợi ý rằng những sự hy sinh có vẻ là thiết yếu trong việc phân tích dữ liệu đồng truyền không thực sự cần thiết. Nó cũng mở đường cho một kỷ nguyên mới của việc quên chiến lược.

Phát Hiện Xu Hướng

Các thuật toán truyền dữ liệu hữu ích trong bất kỳ tình huống nào bạn đang theo dõi một cơ sở dữ liệu đang được cập nhật liên tục. Điều này có thể là AT&T giữ theo dõi các gói dữ liệu hoặc Google theo dõi luồng truy vấn tìm kiếm không ngừng. Trong những tình huống này, việc có một phương pháp để trả lời câu hỏi thời gian thực về dữ liệu mà không cần phải xem xét lại hoặc thậm chí nhớ mỗi mảnh dữ liệu bạn từng thấy là hữu ích, thậm chí là cần thiết.

Dưới đây là một ví dụ đơn giản. Hãy tưởng tượng bạn có một dòng liên tục các con số và bạn muốn biết tổng của tất cả các con số bạn đã thấy cho đến nay. Trong trường hợp này, rõ ràng là thay vì nhớ mỗi con số, bạn có thể sử dụng việc chỉ nhớ một con số: tổng chạy.

Thách thức trở nên khó khăn hơn, tuy nhiên, khi những câu hỏi bạn muốn đặt về dữ liệu của mình trở nên phức tạp hơn. Hãy tưởng tượng rằng thay vì tính tổng, bạn muốn có thể trả lời câu hỏi sau: Con số nào xuất hiện nhiều nhất? Không rõ ràng là bạn có thể sử dụng loại tắt nào để giữ câu trả lời sẵn sàng.

Câu đố cụ thể này được biết đến là vấn đề “mục xuất hiện thường xuyên” hoặc “người chiến thắng nặng nề”. Thuật toán đầu tiên giải quyết nó được phát triển vào đầu những năm 1980 bởi David Gries của Đại học Cornell và Jayadev Misra của Đại học Texas, Austin. Chương trình của họ hiệu quả ở nhiều cách, nhưng nó không thể xử lý điều được gọi là “phát hiện thay đổi”. Nó có thể cho bạn biết các từ khóa được tìm kiếm nhiều nhất, nhưng không biết từ khóa nào đang trở nên phổ biến. Trong trường hợp của Google, nó có thể xác định “Wikipedia” là một từ khóa tìm kiếm phổ biến mãi mãi, nhưng không thể tìm ra sự tăng đột ngột trong các tìm kiếm kèm theo một sự kiện lớn như Siêu bão Irma.

“Đó là một vấn đề mã hóa—bạn mã hóa thông tin xuống tóm tắt gọn nhẹ và cố gắng trích xuất thông tin giúp bạn khôi phục lại những gì đã được đưa vào ban đầu,” nói Graham Cormode, một nhà khoa học máy tính tại Đại học Warwick.

Trong hơn 30 năm tiếp theo, Cormode và các nhà khoa học máy tính khác đã cải tiến thuật toán của Gries và Misra. Một số thuật toán mới có thể phát hiện các từ khóa xu hướng, ví dụ như, trong khi những cái khác có thể làm việc với một định nghĩa tốt hơn về việc từ khóa nào được coi là thường xuyên. Tất cả những thuật toán đó đều đưa ra sự đánh đổi, như là hy sinh tốc độ để có độ chính xác hoặc tiêu thụ bộ nhớ để có độ tin cậy.

Dữ liệu Nhỏ

Các con số nhỏ dễ theo dõi hơn so với các con số lớn.

Hãy tưởng tượng, ví dụ, bạn đang theo dõi một dòng số từ 0 đến 50,000,000 (một công việc tương tự như đăng nhập người dùng internet bằng địa chỉ IP của họ). Bạn có thể theo dõi các số bằng cách sử dụng một chỉ số 50,000,000 số, nhưng khó khăn khi làm việc với một chỉ số có kích thước đó. Một cách tốt hơn là coi mỗi số có tám chữ số như bốn số hai chữ số liên kết với nhau.

Hãy nói bạn thấy số 12,345,678. Một cách tiết kiệm bộ nhớ để nhớ nó là chia nó thành bốn khối hai chữ số: 12, 34, 56, 78. Sau đó, bạn có thể gửi mỗi khối đến một thuật toán phụ tính tần suất: 12 đến bản sao một của thuật toán, 34 đến bản sao hai, 56 đến bản sao ba và 78 đến bản sao bốn.

Mỗi thuật toán phụ duy trì chỉ số riêng về những gì nó đã thấy, nhưng vì mỗi phiên bản chỉ nhìn thấy những con số có tối đa hai chữ số, mỗi chỉ số chỉ chạy từ 0 đến 99.

Một đặc điểm quan trọng của việc chia này là nếu số lớn - 12,345,678 - xuất hiện thường xuyên trong dòng dữ liệu tổng thể của bạn, các thành phần hai chữ số của nó cũng sẽ xuất hiện thường xuyên. Khi bạn yêu cầu mỗi thuật toán phụ xác định các số nó đã thấy nhiều nhất, bản sao một sẽ trả ra 12, bản sao hai sẽ trả ra 34, và cứ thế. Bạn sẽ có thể tìm thấy các thành viên thường xuyên nhất của một danh sách lớn chỉ bằng cách tìm kiếm các mục thường xuyên trong bốn danh sách ngắn hơn nhiều.

“Thay vì tiêu tốn 50 triệu đơn vị thời gian lặp qua toàn bộ vũ trụ, bạn chỉ có bốn thuật toán tiêu tốn 100 đơn vị thời gian,” Nelson nói.

Vấn đề chính của chiến lược chia và xử lý này là trong khi việc chia một số lớn thành các số nhỏ là dễ dàng, việc ngược lại khó hơn - khó khăn khi lấy ra những số nhỏ đúng để kết hợp lại và đưa ra số lớn đúng.

Tưởng tượng, ví dụ, rằng dòng dữ liệu của bạn thường xuyên bao gồm hai số có một số chữ số chung: 12,345,678 và 12,999,999. Cả hai bắt đầu với số 12. Thuật toán của bạn chia mỗi số thành bốn số nhỏ hơn, sau đó gửi mỗi số đó đến một thuật toán phụ. Sau đó, bạn hỏi mỗi thuật toán phụ, “Các số nào bạn đã thấy thường xuyên nhất?” Bản sao một sẽ nói, “Tôi đã thấy rất nhiều số 12.” Một thuật toán đang cố gắng xác định số có tám chữ số nào mà nó đã thấy thường xuyên nhất không thể biết nếu tất cả những số 12 này thuộc về một số tám chữ số hay, như trong trường hợp này, thuộc về hai số khác nhau.

“Thách thức là phải tìm ra những khối hai chữ số nào nên nối với những khối hai chữ số khác,” Nelson nói.

Những người viết công việc mới giải quyết khả năng bế tắc này bằng cách đóng gói mỗi khối hai chữ số với một thẻ nhỏ không chiếm nhiều bộ nhớ nhưng vẫn cho phép thuật toán ghép lại các phần hai chữ số theo cách đúng.

Để xem một cách tiếp cận đơn giản về cách gắn thẻ có thể hoạt động, bắt đầu với 12,345,678 và chia nó thành các khối hai chữ số. Nhưng lần này, trước khi gửi mỗi khối đến thuật toán phụ tương ứng của nó, đóng gói khối đó với một cặp số nhận dạng duy nhất có thể được sử dụng để ghép lại các khối. Thẻ đầu tiên trong những thẻ này phục vụ làm tên của khối, thẻ thứ hai làm liên kết. Đằng này, 12,345,678 trở thành:

12, 0, 1 / 34, 1, 2 / 56, 2, 3 / 78, 3, 4

Ở đây số 12 có tên là “0” và được liên kết với số có tên là “1.” Số 34 có tên là “1” và được liên kết với số có tên là “2.” Và cứ như vậy.

Bây giờ khi các thuật toán phụ trả về các khối hai chữ số mà chúng đã thấy thường xuyên nhất, 12 tìm số được gắn thẻ là “1” và tìm thấy 34, sau đó 34 tìm số được gắn thẻ là “2” và tìm thấy 56, và 56 tìm số được gắn thẻ là “3” và tìm thấy 78.

Như vậy, bạn có thể nghĩ về những khối hai chữ số như là các liên kết trong một chuỗi, với những liên kết được giữ chặt bởi những số nhận dạng bổ sung này.

Vấn đề của chuỗi, tất nhiên, là chúng chỉ mạnh như liên kết yếu nhất của chúng. Và những chuỗi này gần như chắc chắn sẽ bị đứt.

Xây Dựng Khối

Không có thuật toán nào hoạt động hoàn hảo mỗi khi bạn chạy nó - thậm chí những thuật toán tốt nhất cũng phát nổ một tỷ lệ nhỏ lỗi. Trong ví dụ mà chúng ta đã sử dụng, một lỗi có thể có nghĩa là khối hai chữ số thứ hai, 34, được gán một thẻ không chính xác và do đó, khi nó đi tìm khối mà nó nên được kết nối, nó không có thông tin cần thiết để tìm thấy 56. Và khi một liên kết trong chuỗi thất bại, toàn bộ nỗ lực sẽ đổ sụp.

Để tránh vấn đề này, các nghiên cứu sử dụng điều gọi là một “đồ thị mở rộng.” Trong một đồ thị mở rộng, mỗi khối hai chữ số tạo thành một điểm. Các điểm được kết nối bởi các đường (theo quy trình đánh thẻ mô tả ở trên) để tạo thành một cụm. Đặc điểm quan trọng của một đồ thị mở rộng là thay vì chỉ nối mỗi điểm với các khối liền kề của nó, bạn nối mỗi khối hai chữ số với nhiều khối khác. Ví dụ, với 12,345,678, bạn nối 12 với 34 nhưng cũng với 56, để bạn vẫn có thể nói rằng 12 và 56 thuộc cùng một số ngay cả khi liên kết giữa 12 và 34 thất bại.

Một biểu đồ mở rộng không luôn hoàn hảo. Đôi khi nó sẽ không kết nối hai khối mà nên được kết nối. Hoặc nó sẽ kết nối hai khối không thuộc về một nhóm. Để đối phó với xu hướng này, các nhà nghiên cứu đã phát triển bước cuối cùng của thuật toán của họ: một thuật toán con 'giữ cụm' có thể kiểm tra một biểu đồ mở rộng và xác định chính xác những điểm nào được phải được nhóm lại và những điểm nào không, ngay cả khi một số đường kết nối bị thiếu và những đường giả mạo được thêm vào.

“Điều này đảm bảo rằng tôi có thể khôi phục một cái gì đó giống như các nhóm ban đầu,” Thorup nói.

Và trong khi Twitter không sẽ triển khai biểu đồ mở rộng ngay mai, các kỹ thuật đằng sau nó có thể áp dụng cho một loạt các vấn đề khoa học máy tính rộng lớn hơn so với việc đếm tweet. Thuật toán cũng chứng minh rằng những hi sinh nhất định trước đây dường như cần thiết để giải quyết vấn đề các mục phổ biến không cần phải được thực hiện. Thuật toán trước đây luôn phải từ bỏ một cái gì đó — chúng chính xác nhưng tốn bộ nhớ, hoặc nhanh chóng nhưng không thể xác định được mục phổ biến nào đang trở nên phổ biến. Công việc mới này cho thấy rằng với cách đúng để mã hóa nhiều thông tin, bạn có thể có được tốt nhất của tất cả các thế giới có thể: Bạn có thể lưu trữ các mục phổ biến của bạn và nhớ lại chúng nhanh chóng.

Câu chuyện gốc được tái bản với sự cho phép từ Quanta Magazine, một tờ báo độc lập với biên tập của Quanta Magazine, một tổ chức của Simons Foundation với nhiệm vụ là nâng cao sự hiểu biết của công chúng về khoa học bằng cách theo dõi các phát triển nghiên cứu và xu hướng trong toán học và các ngành khoa học tự nhiên và đời sống.