Randomized Algorithms (อัลกอริทึมแบบสุ่ม)
Randomized algorithms ในรูปของ random sampling (การสุ่มตัวอย่าง) และ blueprint (แผนผัง) ถูกใช้เพื่อจัดการกับ large, high-dimensional data streams (ข้อมูลสตรีมขนาดใหญ่ มิติสูง) ความจำเป็นของ randomization นำไปสู่อัลกอริทึมที่ง่ายกว่าและมีประสิทธิภาพมากกว่า (simpler and more effective algorithms) เทียบกับ deterministic algorithms (อัลกอริทึมแบบ 결정론) ที่รู้จัก
หาก randomized algorithm คืนคำตอบที่ถูกต้องตลอดเวลา แต่ running times เปลี่ยนแปลง เรียกว่า Las Vegas algorithm ในทางตรงข้าม Monte Carlo algorithm มี bounds (ขีดจำกัด) บน running time แต่ไม่สามารถคืนผลลัพธ์ที่แท้จริง (true result) ได้ โดยปกติพิจารณา Monte Carlo algorithms ความสำคัญของ randomized algorithm คือ เพียงแค่การกระจายความน่าจะเป็น (probability distribution) บนกลุ่ม deterministic algorithms
เนื่องจาก randomized algorithm คืน random variable เป็นผลลัพธ์ จึงเป็นไปได้ที่จะมี bounds บน tail probability ของ random variable นั้น สิ่งนี้บอกเราว่า ความน่าจะเป็นที่ random variable แตกต่างจาก expected value (ค่าคาดหวัง) ของมัน น้อยมาก เครื่องมือหลักคือ Chebyshev's Inequality (อสมการเชบิเชฟ)
ให้ X เป็น random variable ที่มี mean μ และ standard deviation σ (variance σ2) Chebyshev's inequality ระบุว่า
$$\mathrm{P(|X-\mu|>k)<\frac{\sigma^2 }{k^2}}$$
สำหรับ positive real number k ใดๆ อสมการนี้ใช้ bound (ขอบเขต) variance ของ random variable ในหลายกรณี หลาย random variables สามารถใช้เพื่อเพิ่มความเชื่อมั่น (confidence) ในผลลัพธ์นี้ โดยพิจารณา random variables เหล่านี้เป็นอิสระสมบูรณ์ (completely independent) Chernoff bounds สามารถใช้ได้
ให้ X1X2 … Xn เป็น independent Poisson trials ใน Poisson trial ความน่าจะเป็นของความสำเร็จเปลี่ยนแปลงจาก trial ไป trial หาก X เป็นผลรวมของ X1 ถึง Xn รุ่นอ่อน (weaker version) ของ Chernoff bound บอกเราว่า
$$\mathrm{P[X<(1+\delta)\mu]< e^{-\mu\delta^2}}$$
โดยที่ δ ∈ (0, 1] นี่แสดงให้เห็นว่า ความน่าจะเป็นลดลงแบบ exponential (exponentially) เมื่อเคลื่อนออกจาก mean ซึ่งทำให้ประมาณการที่แย่ (poor estimates) ไม่น่าจะเกิดขึ้นมาก
Data Stream Management System (DSMS)
ใน Data Stream Management System มี data streams หลายสตรีม พวกเขาปรากฏ on-line (ออนไลน์) และ continuous (ต่อเนื่อง), temporally series (ลำดับเวลา), และ อาจเป็น infinite (อนันต์) เนื่องจากองค์ประกอบจาก data stream ถูกประมวลผล (processed) มันจะถูกทิ้ง (discarded) หรือ archived (เก็บถาวร) และไม่สามารถดึงกลับมาได้ง่าย (simply fetched) เว้นแต่จะถูกจัดเก็บอย่างชัดเจนในหน่วยความจำ (explicitly saved in memory)
โครงสร้างการประมวลผลคิวรี่ข้อมูลสตรีม (stream data query processing structure) ประกอบด้วยสามองค์ประกอบ ได้แก่ end-user (ผู้ใช้ปลายทาง), query processor (ตัวประมวลผลคิวรี่), และ scratch space (พื้นที่ชั่วคราว) (ซึ่งอาจรวมถึง main memory และ disks) End user ส่งคิวรี่ไปยัง DSMS และ query processor รับคิวรี่ ประมวลผลมันโดยใช้ข้อมูลที่จัดเก็บใน scratch space และคืนผลลัพธ์ให้ผู้ใช้
คิวรี่สามารถเป็น one-time queries (คิวรี่ครั้งเดียว) หรือ continuous queries (คิวรี่ต่อเนื่อง) One-time query คำนวณครั้งเดียวบน point-in-time snapshot (ภาพถ่ายจุดในเวลา) ของชุดข้อมูล พร้อมคำตอบที่คืนให้ผู้ใช้ Continuous query คำนวณต่อเนื่องขณะที่ data streams ยังคงเข้ามา
