Distributed tracing is crucial for modern observability, offering richer context than logs. However, the volume of tracing data can be overwhelming. Sampling addresses this by selectively retaining data, with two main approaches: head sampling (deciding upfront) and tail sampling (deciding after collecting all spans). Head sampling is simpler but can miss localized issues. Tail sampling, while more accurate, is complex to implement at scale, requiring buffering, stateful processing, and potentially impacting system resilience. Furthermore, sampling inherently affects the accuracy of RED metrics (request rate, error rate, duration), necessitating metric materialization *before* sampling.
This post introduces **GIST (Greedy Independent Set Thresholding)**, a new algorithm for selecting diverse and useful data subsets for machine learning. GIST tackles the NP-hard problem of balancing diversity (minimizing redundancy) and utility (relevance to the task) in large datasets.
**Key points:**
* **Approach:** GIST prioritizes minimum distance between selected data points (diversity) then uses a greedy algorithm to approximate the highest-utility subset within that constraint, testing various distance thresholds.
* **Guarantee:** GIST is guaranteed to find a subset with at least half the value of the optimal solution.
* **Performance:** Experiments demonstrate GIST outperforms existing methods (Random, Margin, k-center, Submod) in image classification and single-shot downsampling.
* **Application:** Already used to improve video recommendation diversity at YouTube.
**GIST provides a mathematically grounded and efficient solution for selecting high-quality data subsets for machine learning, crucial as datasets scale.**
.
**Key points:**
* **Approach:** GIST prioritizes minimum distance between selected data points (diversity) then uses a greedy algorithm to approximate the highest-utility subset within that constraint, testing various distance thresholds.
* **Guarantee:** GIST is guaranteed to find a subset with at least half the value of the optimal solution.
* **Performance:** Experiments demonstrate GIST outperforms existing methods (Random, Margin, k-center, Submod) in image classification and single-shot downsampling.
* **Application:** Already used to improve video recommendation diversity at YouTube.
**GIST provides a mathematically grounded and efficient solution for selecting high-quality data subsets for machine learning, crucial as datasets scale.**
.
