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

Solution: Sample Users

• Pick $\frac{1}{10}$ 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 的比例，可以按照以下步骤进行：

1. 哈希（Hashing）：
   • 对每个元组的键应用一个均匀分布的哈希函数。
   • 将键的哈希值映射到 $b$ 个桶中。
2. 采样条件：
   • 如果哈希值小于或等于 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）：
  • 数据流描述：
    • 对于每个商品 $X$，维护一个二进制流：
      • 如果商品在第 nn 次交易中售出，流中记录为 1。
      • 如果未售出，记录为 0。
  • 查询需求：
    • 回答问题：商品 $X$ 在最近 kk 次销售中出现了多少次？

4. 滑动窗口模型的挑战

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

5. 优化策略

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

6. 实际应用场景

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

[[BDA-DGIM]]