อัลกอริทึมแบบสุ่ม − อัลกอริธึมแบบสุ่มในรูปแบบของสุ่มตัวอย่างและพิมพ์เขียว ใช้เพื่อจัดการกับสตรีมข้อมูลขนาดใหญ่ที่มีมิติสูง ความต้องการของการสุ่มทำให้อัลกอริธึมที่ง่ายขึ้นและมีประสิทธิภาพมากขึ้น ตรงกันข้ามกับอัลกอริธึมที่กำหนดขึ้นเองที่รู้จัก
หากอัลกอริธึมแบบสุ่มส่งกลับคำตอบที่ถูกต้องอย่างต่อเนื่อง แต่เวลาทำงานเปลี่ยนไป จะเรียกว่าอัลกอริธึมลาสเวกัส ในทางตรงกันข้าม อัลกอริธึมของ Monte Carlo มีขอบเขตของเวลาทำงาน แต่ไม่สามารถคืนค่าผลลัพธ์ที่แท้จริงได้ โดยปกติแล้วสามารถพิจารณาอัลกอริธึมของ Monte Carlo ได้ ความสำคัญของอัลกอริธึมแบบสุ่มเป็นเพียงการกระจายความน่าจะเป็นในกลุ่มของอัลกอริธึมที่กำหนดขึ้นเอง
เนื่องจากอัลกอริธึมสุ่มคืนค่าตัวแปรสุ่มเป็นผล จึงมีแนวโน้มว่าจะมีขอบเขตของความน่าจะเป็นส่วนท้ายของตัวแปรสุ่มนั้น สิ่งนี้บอกเราว่าความน่าจะเป็นที่ตัวแปรสุ่มแตกต่างจากค่าที่คาดไว้นั้นสั้น เครื่องมือหลักคืออสมการของ Chebyshev
ให้ X เป็นตัวแปรสุ่มที่มีค่าเฉลี่ย µ และค่าเบี่ยงเบนมาตรฐาน σ (ความแปรปรวน σ 2 ). ความไม่เท่าเทียมกันของ Chebyshev บอกว่า
$$\mathrm{P(|X-\mu|>k)<\frac{\sigma^2 }{k^2}}$$
สำหรับจำนวนจริงบวกใดๆ ที่กำหนด k ความไม่เท่าเทียมกันนี้ใช้เพื่อผูกความแปรปรวนของตัวแปรสุ่ม ในหลายกรณี สามารถใช้ตัวแปรสุ่มหลายตัวเพื่อเพิ่มความมั่นใจในผลลัพธ์นี้ได้ เมื่อพิจารณาว่าตัวแปรสุ่มเหล่านี้เป็นอิสระโดยสมบูรณ์ ขอบเขตของเชอร์นอฟก็สามารถใช้ได้
ให้ X1 X2 … Xn เป็นการทดลองปัวซองอิสระ ในการทดลองแบบปัวซอง ความน่าจะเป็นของความสำเร็จจะเปลี่ยนจากการทดลองเป็นแบบทดลอง ถ้า X คือผลรวมของ X1 ถึง Xn จากนั้นเวอร์ชันที่อ่อนแอกว่าของ Chernoff ที่ถูกผูกไว้จะบอกเราว่า
$$\mathrm{P[X<(1+\delta)\mu] โดยที่ δ ∈ (0, 1] แสดงว่าความน่าจะเป็นลดลงแบบทวีคูณเนื่องจากสามารถเคลื่อนจากค่าเฉลี่ยได้ ซึ่งสร้างค่าประมาณที่ต่ำซึ่งไม่น่าเป็นไปได้มาก
ระบบจัดการสตรีมข้อมูล - ในระบบการจัดการกระแสข้อมูล มีสตรีมข้อมูลหลายแบบ ปรากฏออนไลน์และต่อเนื่อง เป็นชุดชั่วคราว และอาจไม่มีที่สิ้นสุด เนื่องจากคอมโพเนนต์จากสตรีมข้อมูลได้รับการปฏิบัติแล้ว คอมโพเนนต์ดังกล่าวจึงถูกละทิ้งหรือเก็บถาวร และไม่สามารถดึงข้อมูลได้ง่ายๆ เว้นแต่จะบันทึกไว้ในหน่วยความจำอย่างชัดแจ้ง
โครงสร้างการประมวลผลการสืบค้นข้อมูลสตรีมประกอบด้วยองค์ประกอบสามอย่าง เช่น ผู้ใช้ปลายทาง ตัวประมวลผลการสืบค้น และพื้นที่เริ่มต้น (ซึ่งอาจรวมถึงหน่วยความจำหลักและดิสก์) ผู้ใช้ปลายทางเกี่ยวข้องกับการสืบค้น DSMS และตัวประมวลผลการสืบค้นจะใช้การสืบค้น ประมวลผลโดยใช้ข้อมูลที่บันทึกไว้ในพื้นที่เริ่มต้น และคืนค่าผลลัพธ์ให้กับผู้ใช้
แบบสอบถามอาจเป็นแบบสอบถามแบบครั้งเดียวหรือแบบสอบถามแบบต่อเนื่อง แบบสอบถามแบบครั้งเดียวจะถูกคำนวณหนึ่งครั้งบนภาพถ่ายจุดในช่วงเวลาของชุดข้อมูล โดยคำตอบจะคืนให้กับผู้ใช้ ระบบจะคำนวณการสืบค้นข้อมูลอย่างต่อเนื่องในขณะที่สตรีมข้อมูลยังคงปรากฏอยู่
