Thuật toán ngẫu nhiên - Các thuật toán ngẫu nhiên dưới dạng lấy mẫu ngẫu nhiên và thiết kế chi tiết, được sử dụng để xử lý các luồng dữ liệu lớn, nhiều chiều. Nhu cầu ngẫu nhiên hóa dẫn đến các thuật toán đơn giản và hiệu quả hơn trái ngược với các thuật toán xác định đã biết.
Nếu một thuật toán ngẫu nhiên liên tục trả về câu trả lời đúng nhưng thời gian chạy thay đổi, nó được gọi là thuật toán Las Vegas. Ngược lại, thuật toán Monte Carlo có giới hạn về thời gian chạy nhưng không thể khôi phục kết quả thực. Nó thường có thể xem xét các thuật toán Monte Carlo. Tầm quan trọng của một thuật toán ngẫu nhiên chỉ đơn giản là một phân phối xác suất trên một nhóm các thuật toán xác định.
Cho rằng một thuật toán ngẫu nhiên khôi phục một biến ngẫu nhiên do kết quả, nó có khả năng có giới hạn đối với xác suất đuôi của biến ngẫu nhiên đó. Điều này cho chúng ta biết rằng xác suất biến ngẫu nhiên thay đổi so với giá trị kỳ vọng của nó là ngắn. Công cụ chính là Bất bình đẳng của Chebyshev.
Gọi X là một biến ngẫu nhiên với trung bình µ và độ lệch chuẩn σ (phương sai σ 2 ). Sự bất bình đẳng của Chebyshev nói lên điều đó
$$ \ mathrm {P (| X- \ mu |> k) <\ frac {\ sigma ^ 2} {k ^ 2}} $$
với bất kỳ số thực dương nào cho trước, k. Bất đẳng thức này được sử dụng để ràng buộc phương sai của một biến ngẫu nhiên. Trong một số trường hợp, nhiều biến ngẫu nhiên có thể được sử dụng để cải thiện độ tin cậy của kết quả này. Xem xét các biến ngẫu nhiên này là hoàn toàn độc lập, có thể sử dụng giới hạn Chernoff.
Hãy để X 1 X 2 … X n là các thử nghiệm Poisson độc lập. Trong một thử nghiệm Poisson, xác suất thành công thay đổi từ thử nghiệm này sang thử nghiệm khác. Nếu X là tổng của X 1 đến X n , sau đó một phiên bản yếu hơn của Chernoff ràng buộc cho chúng tôi biết rằng
$$ \ mathrm {P [X <(1+ \ delta) \ mu] trong đó δ ∈ (0, 1]. Điều này cho thấy rằng xác suất giảm theo cấp số nhân vì nó có thể di chuyển từ giá trị trung bình, điều này tạo ra các ước tính kém khó xảy ra hơn nhiều.
Hệ thống quản lý luồng dữ liệu - Trong Hệ thống quản lý luồng dữ liệu, có một số luồng dữ liệu. Chúng xuất hiện trực tuyến và là chuỗi liên tục, theo thời gian và có thể là vô hạn. Vì một thành phần từ luồng dữ liệu đã được xử lý nên nó sẽ bị loại bỏ hoặc được lưu trữ và không thể tìm nạp một cách đơn giản trừ khi nó được lưu trong bộ nhớ một cách rõ ràng.
Cấu trúc xử lý truy vấn dữ liệu luồng bao gồm ba phần tử như người dùng cuối, bộ xử lý truy vấn và không gian đầu (có thể bao gồm bộ nhớ chính và đĩa). Người dùng cuối quan tâm đến một truy vấn tới DSMS và bộ xử lý truy vấn nhận truy vấn, xử lý nó bằng cách sử dụng dữ liệu được lưu trong không gian đầu và khôi phục kết quả cho người dùng.
Truy vấn có thể là truy vấn một lần hoặc truy vấn liên tục. Truy vấn một lần được tính một lần qua ảnh chụp tại thời điểm của tập dữ liệu, với câu trả lời được khôi phục cho người dùng. Một truy vấn liên tục được tính liên tục khi các luồng dữ liệu tiếp tục xuất hiện.