Advanced Data Structures (Bloom Filter, HyperLogLog, Count-Min Sketch)

class BloomFilter {
  constructor(size = 1000, hashCount = 3) {
    this.size = size;
    this.hashCount = hashCount;
    this.bitArray = new Uint8Array(size); // All zeros initially
  }

  // Multiple hash functions using different seeds
  _hash(item, seed) {
    let hash = seed;
    for (let i = 0; i < item.length; i++) {
      hash = (hash * 31 + item.charCodeAt(i)) % this.size;
    }
    return Math.abs(hash);
  }

  // Add an element (set bits)
  add(item) {
    for (let i = 0; i < this.hashCount; i++) {
      const pos = this._hash(item, i * 0xdeadbeef);
      this.bitArray[pos] = 1;
    }
  }

  // Check if element might exist
  mightContain(item) {
    for (let i = 0; i < this.hashCount; i++) {
      const pos = this._hash(item, i * 0xdeadbeef);
      if (this.bitArray[pos] === 0) {
        return false; // Definitely NOT in set (100% certain)
      }
    }
    return true; // Probably in set (might be false positive)
  }

  // Memory usage in bytes
  memoryBytes() {
    return this.bitArray.byteLength;
  }
}

// Real-world use: Username availability check
const usernameFilter = new BloomFilter(100_000, 5);

// Pre-populate with existing usernames
['alice', 'bob', 'charlie', 'devripon', 'system_admin'].forEach(u =>
  usernameFilter.add(u)
);

// Check new username — avoid DB query if definitely not exists
function checkUsername(username) {
  if (!usernameFilter.mightContain(username)) {
    // Definitely available — no DB query needed!
    return { available: true, checkedDB: false };
  }
  // Might exist — check DB to confirm (avoids false negative)
  const existsInDB = queryDatabase(username); // actual DB check
  return { available: !existsInDB, checkedDB: true };
}

// Example:
console.log(checkUsername('xyzabc123')); // { available: true, checkedDB: false }
console.log(checkUsername('alice'));      // { available: false, checkedDB: true }

// Stats: 1 billion URLs → HashSet ~50 GB vs Bloom Filter ~1 MB (50,000x savings)
console.log(`Memory used: ${usernameFilter.memoryBytes()} bytes`);

# Redis HyperLogLog — Track unique website visitors

# Add visitors (PFADD — Probabilistic Frequency ADD)
PFADD daily_visitors:2026-05-08 "user:1001"
PFADD daily_visitors:2026-05-08 "user:1002"
PFADD daily_visitors:2026-05-08 "user:1001"  # duplicate — ignored
PFADD daily_visitors:2026-05-08 "user:1003"

# Count unique visitors (PFCOUNT — Probabilistic Frequency COUNT)
PFCOUNT daily_visitors:2026-05-08
# Returns: 3 (not 4, because user:1001 was added twice)

# Merge multiple HyperLogLogs (e.g., weekly unique visitors)
PFMERGE weekly_visitors:2026-W19   daily_visitors:2026-05-04   daily_visitors:2026-05-05   daily_visitors:2026-05-06   daily_visitors:2026-05-07   daily_visitors:2026-05-08

PFCOUNT weekly_visitors:2026-W19
# Returns: ~unique visitors for the whole week (12 KB memory!)

# ──────────────────────────────────────────────────────────
# Node.js example — YouTube view counter
# ──────────────────────────────────────────────────────────

const Redis = require('ioredis');
const redis = new Redis();

// Track unique video view
async function trackVideoView(videoId, userId) {
  const key = `video:views:${videoId}`;

  // HyperLogLog — O(1) memory regardless of views count
  await redis.pfadd(key, userId);

  // Get approximate unique view count
  const uniqueViews = await redis.pfcount(key);
  return uniqueViews;
}

// Get daily active users (DAU)
async function getDailyActiveUsers(date) {
  const key = `dau:${date}`;
  return redis.pfcount(key);
}

// Get weekly active users by merging daily HLLs
async function getWeeklyActiveUsers(weekDates) {
  const destKey = `wau:week`;
  const dailyKeys = weekDates.map(d => `dau:${d}`);

  await redis.pfmerge(destKey, ...dailyKeys);
  return redis.pfcount(destKey);
}

// Usage:
// trackVideoView('v_abc123', 'user_456') → returns unique view count
// Memory: ~12 KB regardless of 1M or 1B unique viewers!

// Real-world stats:
// YouTube: uses HyperLogLog for unique views
// LinkedIn: unique visitor counts per post
// Redis itself: PFADD / PFCOUNT built-in

import hashlib

class CountMinSketch:
    def __init__(self, width=1000, depth=5):
        """
        width: columns (counter array size)
        depth: rows (number of hash functions)
        Higher width/depth = more accuracy but more memory
        """
        self.width = width
        self.depth = depth
        self.table = [[0] * width for _ in range(depth)]

    def _hash(self, item, seed):
        """Hash item with seed to get column index"""
        h = hashlib.md5(f"{seed}:{item}".encode()).hexdigest()
        return int(h, 16) % self.width

    def increment(self, item, count=1):
        """Add item occurrence"""
        for row in range(self.depth):
            col = self._hash(item, row)
            self.table[row][col] += count

    def estimate(self, item):
        """Get estimated frequency — returns minimum across all rows"""
        return min(
            self.table[row][self._hash(item, row)]
            for row in range(self.depth)
        )

    def memory_bytes(self):
        return self.width * self.depth * 4  # 4 bytes per int


# Twitter Trending Topics Example
cms = CountMinSketch(width=10_000, depth=7)

# Simulate tweet stream
tweets = [
    "Bangladesh", "Cricket", "Bangladesh", "ICC",
    "Bangladesh", "World Cup", "Cricket", "Bangladesh",
    "Dhaka", "Bangladesh", "Cricket"
]

for word in tweets:
    cms.increment(word)

# Query frequencies
words = ["Bangladesh", "Cricket", "World Cup", "Dhaka", "Football"]
for word in words:
    freq = cms.estimate(word)
    print(f"{word}: ~{freq} occurrences")

# Bangladesh: ~5
# Cricket: ~3
# World Cup: ~1
# Dhaka: ~1
# Football: ~0  ← not in stream

# Heavy hitter detection (trending)
def get_trending(cms, candidates, threshold=2):
    return [w for w in candidates if cms.estimate(w) >= threshold]

print(get_trending(cms, words))
# Output: ['Bangladesh', 'Cricket']

print(f"Memory: {cms.memory_bytes()} bytes vs exact dict: huge")

# ═══════════════════════════════════════════════════════
# 1. BLOOM FILTER — BF commands (RedisBloom module)
# ═══════════════════════════════════════════════════════

# Create bloom filter (error rate 0.01 = 1%, capacity 1M items)
BF.RESERVE crawled_urls 0.01 1000000

# Add URLs
BF.ADD crawled_urls "https://google.com"
BF.ADD crawled_urls "https://facebook.com"

# Check if URL was crawled before
BF.EXISTS crawled_urls "https://google.com"   # → 1 (probably yes)
BF.EXISTS crawled_urls "https://unknown.com"  # → 0 (definitely no)

# Batch add/check
BF.MADD crawled_urls "https://a.com" "https://b.com" "https://c.com"
BF.MEXISTS crawled_urls "https://a.com" "https://xyz.com"
# → [1, 0]


# ═══════════════════════════════════════════════════════
# 2. HYPERLOGLOG — PF commands (built into Redis core)
# ═══════════════════════════════════════════════════════

PFADD unique_visitors:2026-05-08 "user:1001" "user:1002" "user:1003"
PFCOUNT unique_visitors:2026-05-08  # → ~3

# Merge for weekly count
PFMERGE weekly_visitors weekly_visitors:mon weekly_visitors:tue


# ═══════════════════════════════════════════════════════
# 3. COUNT-MIN SKETCH — CMS commands (RedisBloom module)
# ═══════════════════════════════════════════════════════

# Initialize CMS (width=2000, depth=7)
CMS.INITBYDIM trending_words 2000 7

# Increment word counts from tweet stream
CMS.INCRBY trending_words "Bangladesh" 1 "Cricket" 1 "Bangladesh" 1

# Query frequencies
CMS.QUERY trending_words "Bangladesh" "Cricket" "Football"
# → [2, 1, 0]

const Redis = require('ioredis');

// Redis Stack connection (includes RedisBloom module)
const redis = new Redis({
  host: 'localhost',
  port: 6379,
});

// ─── Bloom Filter ─────────────────────────────────────────
async function setupCrawler() {
  // Create bloom filter: 1% error rate, 10M capacity
  await redis.call('BF.RESERVE', 'crawled', '0.01', '10000000');

  async function shouldCrawl(url) {
    const exists = await redis.call('BF.EXISTS', 'crawled', url);
    if (exists === 0) {
      await redis.call('BF.ADD', 'crawled', url);
      return true; // Definitely new URL — crawl it
    }
    return false; // Probably already crawled — skip
  }

  return { shouldCrawl };
}

// ─── HyperLogLog ──────────────────────────────────────────
async function trackPageView(pageId, userId) {
  const key = `page:unique:${pageId}`;
  await redis.pfadd(key, userId);
  const uniqueViews = await redis.pfcount(key);
  return uniqueViews;
}

// ─── Count-Min Sketch ─────────────────────────────────────
async function trackHashtag(hashtag) {
  await redis.call('CMS.INCRBY', 'trending', hashtag, '1');
}

async function getHashtagFrequency(hashtag) {
  const result = await redis.call('CMS.QUERY', 'trending', hashtag);
  return result[0]; // Estimated count
}

// Usage:
// trackPageView('video_abc', 'user_123') → returns unique view count
// trackHashtag('#Bangladesh') → increments
// getHashtagFrequency('#Bangladesh') → returns ~frequency