date: 2024-12-23
title: BDA-Stream Data
status: DONE
author:
  - AllenYGY
tags:
  - NOTE
  - BDA
publish: True

BDA-Stream Data

Infinite Data

Filtering data streams
Queries on stream
Web advertising

Data Streams

In many data analytics situations, we do not know the entire data set in advance

Stream Management is important when the input rate is controlled externally:

Google queries
Twitter or Facebook status updates

We can think of the data as infinite and non-stationary (the distribution changes over time)

The Stream Model

Input elements enter at a rapid rate, at one or more input ports (i.e., streams)

We call elements of the stream tuples

The system cannot store the entire stream accessibly

Q: How do you make critical calculations about the stream using a limited amount of (secondary) memory?

Problems on Data Streams

Types of queries one wants on answer on a data stream: (we’ll do these today)

Sampling data from a stream
- Construct a random sample
Queries over sliding windows
- Number of items of type x in the last k elements of the stream
Filtering a data stream
- Select elements with property x from the stream
Counting distinct elements
- Number of distinct elements in the last k elements of the stream
Estimating moments
- Estimate avg./std. dev. of last k elements
Finding frequent elements

Sampling from a Data Stream: Sampling a fixed proportion

Sampling User

Solution: Sample Users

Pick th of users and take all their searches in the sample
Use a hash function that hashes the user name or user id uniformly into 10 buckets

通用采样过程

为了从数据流中采样 a/ba/ba/b 的比例，可以按照以下步骤进行：

哈希（Hashing）：
- 对每个元组的键应用一个均匀分布的哈希函数。
- 将键的哈希值映射到个桶中。
采样条件：
- 如果哈希值小于或等于 aaa，则选取该元组。

Sampling from a Data Stream: Sampling a fixed-size sample

在内存受限的情况下，从数据流中维护一个固定大小 sss 的随机采样集合 SSS。

Queries over a (long) Sliding Window

滑动窗口模型（Sliding Windows）

1. 背景

滑动窗口是一种常见的数据流处理模型。
核心思想：在数据流中，查询只关注最近接收到的 NN 个元素，这些元素组成了一个窗口（window）。

2. 特殊情况

窗口长度 NN 很大：
- 数据量可能大到无法完全存储在内存中，甚至无法存储在磁盘中。
- 或者有大量的独立数据流，每个流的窗口都无法完全存储。

3. 示例应用

电商场景（如 Amazon）：
- 数据流描述：
  - 对于每个商品，维护一个二进制流：
    - 如果商品在第 nn 次交易中售出，流中记录为 1。
    - 如果未售出，记录为 0。
- 查询需求：
  - 回答问题：商品在最近 kk 次销售中出现了多少次？

4. 滑动窗口模型的挑战

数据量限制：
- 随着的增加，存储窗口数据需要大量的内存或磁盘空间。
实时性：
- 需要快速处理数据流并实时更新窗口数据。
多流问题：
- 如果有多个数据流，每个流的窗口都需要独立维护，增加了计算复杂度。

5. 优化策略

近似计算：
- 在窗口数据量过大的情况下，使用近似算法（例如哈希或概率数据结构）来降低存储和计算需求。
分片存储：
- 只维护窗口的部分关键数据，而不是存储所有数据点。
滑动更新：
- 随着新数据点的到来，丢弃窗口中最旧的数据点，从而保持窗口的固定大小。

6. 实际应用场景

实时监控：
- 检测系统日志中最近一段时间的异常行为。
点击流分析：
- 分析最近 kk 次用户点击行为以优化推荐系统。
金融交易：
- 监控股票或商品价格的最近波动趋势。
网络流量分析：
- 在滑动窗口内计算特定 IP 地址的流量量级。