Thuật toán ngẫu nhiên (Randomized Algorithms) − Thuật toán ngẫu nhiên dưới dạng lấy mẫu ngẫu nhiên và bản thiết kế (sketch), được dùng để xử lý luồng dữ liệu lớn, chiều cao. Nhu cầu ngẫu nhiên dẫn đến thuật toán đơn giản và hiệu quả hơn so với thuật toán xác định đã biết.
Nếu 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 thời gian chạy nhưng không thể khôi phục kết quả thực. Thường xem xét thuật toán Monte Carlo. Tầm quan trọng của thuật toán ngẫu nhiên đơn giản là phân phối xác suất trên nhóm thuật toán xác định.
Cho thuật toán ngẫu nhiên trả về biến ngẫu nhiên làm kết quả, có thể có giới hạn xác suất đuôi của biến ngẫu nhiên đó. Điều này cho chúng ta biết xác suất biến ngẫu nhiên lệch khỏi giá trị kỳ vọng là ngắn. Công cụ chính là Bất đẳng thức Chebyshev.
Cho X là biến ngẫu nhiên với trung bình μ và độ lệch chuẩn σ (phương sai σ²). Bất đẳng thức Chebyshev nói rằng:
P(|X - μ| > k) < σ² / k²
với bất kỳ số thực dương cho trước k. Bất đẳng thức này dùng để chặn phương sai biến ngẫu nhiên. Trong nhiều trường hợp, nhiều biến ngẫu nhiên có thể dùng để cải thiện niềm tin vào kết quả. Xét các biến ngẫu nhiên hoàn toàn độc lập, giới hạn Chernoff có thể dùng.
Cho X₁, X₂ … Xₙ là các thử nghiệm Poisson độc lập. Trong thử nghiệm Poisson, xác suất thành công thay đổi từ thử nghiệm đến thử nghiệm. Nếu X là tổng X₁ đến Xₙ, thì phiên bản yếu hơn của giới hạn Chernoff cho chúng ta biết:
P[X < (1+δ)μ] < e^(-μδ²)
với δ ∈ (0, 1]. Điều này hiển thị xác suất giảm theo cấp số nhân khi di chuyển từ trung bình, làm cho ước lượng kém trở nên ít có khả năng hơn.
Hệ thống quản lý luồng dữ liệu (Data Stream Management System) − Trong Hệ thống quản lý luồng dữ liệu, có nhiều luồng dữ liệu. Chúng xuất hiện trực tuyến và liên tục, chuỗi thời gian, và có thể vô hạn. Vì một thành phần từ luồng dữ liệu đã được xử lý, nó bị loại bỏ hoặc lưu trữ, và không thể đơn giản lấy lại trừ khi nó được lưu rõ ràng trong bộ nhớ.
Cấu trúc xử lý truy vấn dữ liệu luồng bao gồm ba yếu tố: người dùng cuối, bộ xử lý truy vấn, và không gian tạm (scratch space - có thể bao gồm bộ nhớ chính và đĩa). Người dùng cuối đặt truy vấn cho DSMS, bộ xử lý truy vấn nhận truy vấn, xử lý nó dùng dữ liệu lưu trong không gian tạm, và trả kết quả cho người dùng.
Truy vấn có thể là truy vấn một lần (one-time) hoặc truy vấn liên tục (continuous). Truy vấn một lần được tính một lần trên ảnh chụp thời điểm của tập dữ liệu, với câu trả lời trả về người dùng. Truy vấn liên tục được tính liên tục khi luồng dữ liệu tiếp tục xuất hiện.