Design a Trending Topics System

Exact Counting vs Count-Min Sketch

Evaluating trade-offs between memory efficiency and ranking precision, streaming engine architectures, personalization layers, and cross language deduplication determines the operational scalability of the trending platform.

Tracking exact counts for 10 million distinct topics per hour exhausts worker memory, whereas an approximate sketch dramatically reduces memory at the cost of bounded overestimation error. A hybrid sketch-and-promote architecture balances both approaches.

Exact Counting with Hash Maps:
  - Memory Complexity: O(N) where N represents unique topics per hour (10,000,000 topics).
  - Storage Demand: Requires approximately 2 GB of RAM per Flink worker node under the stated workload assumption.
  - Failure Risk: Unbounded cardinality spikes can trigger JVM garbage collection thrashing or OOM crashes.

Count-Min Sketch (Approximate Frequency Estimation):
  - Fixed Footprint: The design reserves 200 KB for 4 hash functions and an array width of 2,000 slots, plus implementation overhead.
  - Accuracy Bounds: Counts do not under-estimate true frequency, but additive overestimation depends on sketch width and traffic volume.
  - Production Tuning: Choose sketch width and depth from an explicit error budget rather than treating 200 KB as a universal accuracy setting.

Hybrid Sketch and Promote Architecture:
  1. Stream Ingestion: All 10,000,000 topics increment the compact 200 KB Count-Min Sketch.
  2. Promotion Threshold: When a topic's estimated frequency crosses the heavy-hitter threshold,
     it becomes eligible for promotion to an exact tracking hash map.
  3. Bounded State: Only roughly 10,000 candidate topics are maintained in exact memory at a time,
     with a hard cap that evicts the lowest estimated candidates when necessary.
  4. Leaderboard Precision: Top-K ranking runs exclusively on promoted exact counters.
  5. Memory Economy: Core sketch plus candidate counters are approximately 2.2 MB before auxiliary lifecycle,
     SimHash, and metadata state, preserving the original design estimate of roughly 1,000-fold reduction.

Flink vs Spark Structured Streaming vs Kafka Streams

Selecting the appropriate stream processing engine requires balancing latency requirements, windowing capabilities, and state management complexity across the pipeline.

Streaming Engine Architectural Comparison:

Feature             Apache Flink          Spark Structured      Kafka Streams
────────────────────────────────────────────────────────────────────────────────
Processing Model    True streaming        Micro-batch by        True streaming
                    execution             default, while        execution
                                          Continuous
                                          Processing is separate

Windowing Engine    Rich sliding,         Event-time windows    Event-time windows
                    session, and tumbling and watermarks        with grace periods

Keyed State         Managed keyed state   Stateful operators    Local RocksDB state
                    with Embedded        use state stores and  stores with changelog
                    RocksDB option       checkpointing         topics

Exactly-Once        Checkpointed state   Replayable sources,   exactly_once_v2 when
                    consistency, where   checkpointing, and     configured for
                    end-to-end depends   idempotent or         Kafka-native flows
                    on sink semantics    transactional sinks

Latency             Low latency,         Workload and trigger  Millisecond-scale
                    event-driven         dependent, where     event processing is
                    execution            micro-batch can       possible for common
                                         trade latency for     topologies
                                         throughput

Best Suited For     Complex event       Unified SQL/data      Kafka-centric
                    processing with     processing and        applications with
                    large keyed state   existing Spark stack  local state and joins

Selection Verdict:
Apache Flink is a strong fit for trending topics because it combines event time windows,
stateful streaming, and low latency execution with scalable keyed state.

Personalized Trends (Staff Extension)

Reordering trending topics for individual users risks introducing filter bubbles and complicates regional caching. Personalization should operate as an optional post scoring re-ranking phase applied to the top regional candidates rather than requiring an independent counting pipeline. This design keeps streaming state unified while allowing personalized blending based on user interest embeddings.

Personalized Trends Architecture (Staff Level Extension):

Global and Regional Baseline:
  Standard trending produces the top 20 topics for a geographic region, serving identical
  rankings to all users in that territory from Redis cache.

Personalization Layer:
  Blends broad regional news with individual user engagement history without fragmenting
  the underlying stream aggregation pipeline.

Algorithm:
  1. Profile Vectors: Offline Spark jobs generate 64-dimensional user interest vectors daily.
  2. Topic Embeddings: Trending topics receive category vectors generated from entity analysis.
  3. Real-Time Re-ranking:
     relevance = cosine_similarity(topic_embedding, user_interest_embedding)
     final_score = (w1 * velocity) + (w2 * relevance)
     Example weights: w1 = 0.0930769231, w2 = 2.0384615385

Concrete Example:
  User follows #Technology and #ArtificialIntelligence.
  - Global topic #WorldCup: velocity = 15.0, user relevance = 0.1 -> blended score = 1.6
  - Niche topic #GPT5Release: velocity = 5.0, user relevance = 0.9 -> blended score = 2.3
  Result: The personalized feed elevates #GPT5Release while retaining #WorldCup in view.

Latency Guardrail:
  Re-ranking evaluates only the top 50 regional candidates at query time, with a p99 target of under 10 ms.

Trend Category Auto-Classification

Categorizing topics into verticals such as Sports, Politics, and Entertainment enables vertical-specific trend filtering and enriches candidate ranking context without relying solely on manual taxonomy mapping.

Automated Topic Categorization Pipeline:

Objective:
  Assign broad taxonomy tags (Sports, Politics, Tech, Entertainment) to facilitate category-specific
  trend boards and provide context to downstream recommendation engines.

Multi-Stage Classification Flow:
  1. Named Entity Recognition (NER):
     Extract recognized proper nouns from post text (for example, "Taylor Swift" -> PERSON).
  2. Knowledge Graph Resolution:
     Map extracted entities to Wikidata or knowledge graph nodes ("Taylor Swift" -> Musician).
  3. Lightweight Topic Modeling:
     Run pre-trained embeddings or lightweight BERT classifiers across sample post clusters.
  4. Curated Hashtag Taxonomy:
     Direct keyword lookups for major recurring tags (for example, #WorldCup -> Sports).

Fallback Handling:
  Topics with ambiguous or unclassified signals default to the generic "Trending" category.

Multi-Language Trend Merging

Global events spark concurrent discussions across multiple languages and distinct hashtags. Resolving different linguistic variants to a shared entity identifier prevents identical news stories from fragmenting attention and crowding regional leaderboards.

Cross-Lingual Trend Entity Merging:

Challenge:
  A global event produces distinct language-specific hashtags:
  - Spanish: "#CopaDelMundo"
  - English: "#WorldCup"
  - Japanese: "#ワールドカップ"

Without Entity Resolution:
  The identical sporting event occupies three distinct positions on a global or bilingual leaderboard,
  diluting engagement volume and crowding out other newsworthy topics.

With Entity Resolution:
  1. Entity Dictionary: An offline dictionary maps multilingual synonyms to a canonical entity ID
     ("FIFA World Cup 2026").
  2. Aggregation Key: Flink partitions and counts by canonical entity_id rather than raw text.
  3. Localized Display: The serving layer displays the user's localized text variant while reporting
     the aggregated global volume (for example, displaying "2.3M posts").