The Approximate Filter, Join, and GroupBy
summary
Introduces a practical pipeline that turns numeric or string arrays into hash signatures so arrays that are “close enough” collide, using locality-sensitive hashing and specifically cosine LSH implemented with random hyperplanes (matrix–vector products in Breeze, Java/Scala). Integrates MapReduce, Flink and HBase to process millions of domains, clusters about 200 known bad domains into botnet families, keeps false positives low, and reports successful production use at Cisco Umbrella to detect waves of botnets.
AI-written summary · about
chapters (23)
- 0:00Intro
- 1:29About Us
- 2:38Motivating Problem: group similar spikes
- 6:56Clickstream Counts
- 8:38Challenges
- 10:09CPU Usage
- 12:46Signal Clustering
- 14:17Questions
- 15:56Cosine Similarity
- 17:37Theta and Hashes
- 20:19Theta and Deltas
- 21:26p-Stable Hashes
- 22:21Finding the Number of Hyperplanes
- 25:28Hyperplane Generation - alternative
- 26:42Signal Clusters
- 27:32Traditional Pipelines
- 27:56Adversarial Pipelines
- 28:51Adversarial Join
- 30:04Architecture
- 32:21Signal Pre-Processing
- 33:07Detecting Botnets
- 34:10Outline: recap
- 43:22Bibliography
related talks
40mLeveraging Streaming-Based Outlier Detection and SliceLine to Stop Heavily Distributed Bot Attacks
52mDevil in the Haystack
42mWhen Hashes Met Wedges - A Distributed Algorithm for Finding High Similarity Vectors
39mSniffing Out the Strange — A Look at Anomaly Detection
49mA Real-World Example of Using Network Behaviour to Detect Cyber-Compromise
11mFinding Friends in High Dimensions...
18mClojure Versus the Botnets
49mFrom research to production at ebay