PadhaikoAll subjects

Algorithmic Applications and Emerging Topics

Advanced Algorithms (ENCT 467)

Open in the Padhaiko app

8.1 Algorithms for recommendation systems

Recommender systems predict a user's preference (rating or click probability) for unseen items from sparse interaction logs, combining item metadata with collective user behavior.

AspectContent-Based FilteringCollaborative Filtering
Signal UsedItem feature profiles (genre, keywords, TF-IDF vectors)Historical user–item rating/interaction matrix
SimilarityCosine similarity between user profile and item vectorUser–User or Item–Item Pearson / cosine similarity
Cold StartHandles new items immediately; struggles on new usersFails on both new users and new items (zero ratings)
SerendipityLow (tends to over-specialize within past genres)High (discovers cross-genre patterns via peer behavior)

Neighborhood Collaborative Filtering & Matrix Factorization

  1. User-Based / Item-Based Neighborhood CF: Compute cosine or centered Pearson similarity between users (or items) and predict rating as a similarity-weighted average of neighbors' deviations from their mean rating:

Item-item CF scales better in practice because item catalogs change more slowly than user tastes.

  1. Latent-Factor Matrix Factorization (SVD / ALS / SGD): Approximates the sparse rating matrix by low-rank user factors and item factors (), minimizing regularized squared error over observed entries :

Solved via Stochastic Gradient Descent (SGD) or Alternating Least Squares (ALS) (fixing makes optimizing convex and parallelizable across users, then vice versa).

Example 1

1

  1. Two items have rating vectors across two common users: and . Compute the cosine similarity .
  2. In item-based collaborative filtering, user rated two items similar to target item : (similarity ) and (similarity ). Compute the weighted-average predicted rating .

Cosine similarity between and :

Weighted-average rating prediction:

Answer:
  1. Cosine similarity is .
  2. The predicted rating is .

8.2 Algorithms in search engines

Modern web search engines combine crawling, inverted indexing, relevance ranking, link analysis, and near-duplicate detection to answer queries across billions of documents in milliseconds.

Architecture and Core Algorithms

  1. Inverted Index & Posting-List Intersection: Maps each normalized term (after tokenization, lowercasing, stop-word filtering, and stemming) to a sorted posting list of document IDs (docID, tf, positions). Multi-term Boolean AND queries intersect sorted posting lists using two-pointer merge in time, accelerated by skip pointers (spaced every entries) to jump past non-matching blocks.
  2. TF-IDF and Okapi BM25 Ranking:
    • TF-IDF: Balances term frequency against inverse document frequency .
    • BM25: Industry-standard probabilistic ranking saturating term frequency and normalizing document length relative to average length :
  1. Link Analysis (PageRank & HITS): Combines query-dependent text score with query-independent PageRank authority (or HITS Hub/Authority scores) and spam resistance.
  2. MinHash & Locality-Sensitive Hashing (LSH) for Near-Duplicate Detection: Represents each page by a set of -shingles, estimates Jaccard similarity in signature comparisons via MinHash (), and uses LSH banding to detect near-duplicates in sublinear time.
Example 2

2

In a corpus of documents, the term "algorithm" appears in documents. In document , "algorithm" occurs times. Using log-normalized term frequency and base- inverse document frequency , compute the TF-IDF weight of "algorithm" in document .

Compute sublinear term frequency and inverse document frequency :

Multiply to obtain TF-IDF weight:

Answer:

The log-scaled TF-IDF weight is (, ).


8.3 Algorithms for large-scale data analytics

When datasets reach terabytes or millions of dimensions, exact or high-dimensional algorithms become infeasible. Large-scale analytics relies on dimensionality reduction, approximate nearest neighbors, scalable clustering, and distributed execution engines.

Key Techniques for Big Data Analytics

  1. Dimensionality Reduction & Johnson–Lindenstrauss (JL) Lemma:
    • Truncated SVD / PCA: Projects -dimensional points onto the top orthogonal principal directions maximizing variance.
    • Random Projections (JL Lemma): Any set of points in can be projected onto a random -dimensional subspace with (completely independent of !) while preserving all pairwise Euclidean distances within with high probability.
  2. Approximate Nearest Neighbor (ANN) Search:
    • Exact -NN suffers from the curse of dimensionality (KD-trees degrade to linear scan when ).
    • Locality-Sensitive Hashing (LSH): Hashes similar points into the same bucket with high probability (e.g., random hyperplane hashing for cosine similarity, -stable distributions for ).
    • HNSW (Hierarchical Navigable Small World graphs): Multi-layer proximity graph delivering sub-millisecond ANN search at high recall.
  3. Scalable Clustering:
    • Mini-Batch -Means: Updates centroids using small random batches of size , reducing iteration cost from to .
    • -Means++ Initialization: Picks initial centers sequentially with probability proportional to (squared distance to nearest existing center), guaranteeing -competitive clustering objective in expectation.
    • BIRCH / CURE: Summarize dense clusters via Cluster Feature (CF) trees or representative points for single-pass disk-friendly clustering.
  4. Distributed Dataflow Engines (Apache Spark): Represent datasets as immutable partitioned RDDs (Resilient Distributed Datasets) and compile transformations into a DAG of narrow (map/filter, pipelined without shuffle) and wide (reduceByKey/join, requiring shuffle) stages, using lineage graphs for fault recovery.

8.4 Green computing

Green computing designs algorithms, data structures, and scheduling policies to minimize energy consumption (Joules), thermal dissipation, and carbon footprint while meeting performance requirements.

Definition

Power, Energy, and Energy-Delay Product (EDP)

For a processor operating at clock frequency and supply voltage with effective switched capacitance :

Algorithmic Strategies for Energy Efficiency

  1. Dynamic Voltage and Frequency Scaling (DVFS) — Pace vs. Race-to-Sleep:
    • Because while execution time , dynamic energy scales as : running slower at lower voltage drastically reduces dynamic energy!
    • However, static leakage power accumulates continuously over . When is high, race-to-sleep (finish fast at high , then enter deep sleep state) can beat running slowly. Optimal energy scheduling balances dynamic scaling against static leakage power.
  2. Minimizing Data Movement (Memory-Hierarchy Awareness):
    • Fetching bits from off-chip DRAM consumes more energy than a -bit floating-point ALU operation in registers/L1 cache.
    • Cache-oblivious, tiled, and compressed/streaming algorithms (Section 1.5 and Chapter 7) save far more energy by avoiding DRAM/network transfers than by shaving minor ALU instructions.
  3. Carbon-Aware and Workload-Consolidation Scheduling:
    • Server Consolidation / Bin Packing: Pack VMs/containers onto fewer active servers (turning idle machines off rather than running many servers at utilization where static power dominates).
    • Temporal/Spatial Carbon Shifting: Defer delay-tolerant batch jobs (ML training, ETL) to hours or data-center regions powered by surplus solar/wind renewable energy.
Example 3

3

A processor task takes at full frequency (normalized), where dynamic power is and constant static leakage power is . Assume dynamic power scales cubically with frequency () and execution time scales inversely (). Compare total energy (in Joules) and Energy-Delay Product (EDP) at:

  1. Full speed , and
  2. Half frequency via DVFS.

Case 1: Full frequency :

  • Execution time: .
  • Total power: .
  • Total energy: .
  • Energy-Delay Product: .

Case 2: Half frequency :

  • Execution time: .
  • Dynamic power drops by : .
  • Total power: .
  • Total energy: (saving energy!).
  • Energy-Delay Product: (also improves EDP by ).
Answer:

At , total energy is (). Halving frequency to cuts total energy to and lowers to .


Exercises

Practice Exercises — Algorithmic Applications and Emerging Topics

Question 1

Compare Content-Based Filtering, Collaborative Filtering, and Matrix Factorization (SVD/ALS) for recommendation systems, highlighting how each handles the cold-start problem and data sparsity. Also compute the predicted rating using centered item-based CF if user 's average rating is , neighbor items have averages , user rated them , and target item has with similarities , (compute the uncentered weighted average of and explain how centering adjusts for rating bias).

Comparison of recommendation approaches:

  • Content-Based Filtering matches item feature vectors against a user's profile; it recommends new items immediately (no item cold start) but struggles with new users and lacks cross-genre serendipity.
  • Collaborative Filtering uses peer user/item rating correlations for high serendipity, but fails on cold-start items/users with zero ratings and degrades on extreme sparsity.
  • Matrix Factorization (ALS/SGD) compresses sparse ratings into low-rank latent factors , generalizing well under sparsity while still needing side-features or popularity priors for pure cold starts.

Prediction and mean-centering explanation: Uncentered weighted average:

Mean-centering subtracts each item's baseline average () and adds target baseline :

correcting for overly harsh or generous baseline ratings across items.

Answer:

Content-based handles new items, CF captures peer preferences, and Matrix Factorization handles sparse matrices via latent factors. The uncentered prediction is , while mean-centering removes item bias to give .

Question 2

Explain the role of skip pointers in an inverted index posting list and how MinHash + LSH banding detects near-duplicate web pages in sublinear time. If two web pages have Jaccard similarity and an LSH index uses bands of MinHash rows per band, compute the exact probability that the two pages become a candidate pair (collide in at least one band).

Skip pointers and MinHash + LSH:

  • Skip pointers (placed roughly every postings in a sorted posting list of length ) allow posting-list intersection to jump over large chunks of non-matching docIDs in per skip instead of scanning sequentially.
  • MinHash + LSH: Each document's shingle set is compressed into MinHash values where . Partitioning the signature into bands of rows hashes two documents into the same bucket in a given band iff all rows match (probability ), flagging candidate near-duplicates without pairwise comparisons.

Candidate-pair probability ():

  • Probability all rows match in one band: .
  • Probability a single band does not match: .
  • Probability none of the independent bands match: .
  • Probability of colliding in at least one band:
Answer:

Skip pointers accelerate posting-list intersections, while MinHash + LSH finds near-duplicates by banding signatures. For , the candidate collision probability is .

Question 3

Explain the Johnson–Lindenstrauss (JL) Lemma and why approximate nearest neighbor (ANN) algorithms such as LSH or HNSW replace KD-trees for high-dimensional large-scale data analytics. Also distinguish between narrow and wide transformations in Apache Spark's DAG execution model.

JL Lemma and ANN in high dimensions: The JL Lemma guarantees that any points in arbitrarily high dimension can be projected onto dimensions (independent of ) via a random matrix while preserving all pairwise Euclidean distances within factor . KD-trees fail above dimensions because query regions intersect nearly every hyperbox (curse of dimensionality), degrading to brute force; LSH and HNSW trade tiny recall loss for sublinear or query latency.

Narrow vs. wide transformations in Spark:

  • Narrow transformations (map, filter): each output partition depends on at most one parent partition, allowing pipelined execution in memory with zero network shuffle.
  • Wide transformations (groupByKey, reduceByKey, join): output partitions depend on multiple parent partitions, forcing a network shuffle boundary that splits the execution DAG into separate stages.
Answer:

JL random projections compress dimensions to while preserving distances, and LSH/HNSW avoid the curse of dimensionality that defeats KD-trees. In Spark, narrow operations pipeline locally without shuffles, whereas wide operations define stage boundaries requiring network shuffles.

Question 4

Explain why data movement (DRAM/network access) dominates energy consumption in modern algorithms compared to arithmetic ALU operations, and describe how -Means++ initialization improves large-scale clustering quality over random initialization.

Data movement vs. ALU energy: Fetching a -bit word from off-chip DRAM consumes roughly more energy than performing a -bit arithmetic operation inside CPU registers or L1 cache. Consequently, algorithms that maximize spatial/temporal cache locality (tiled matrix multiplication, streaming sketches, compressed representations) cut system energy dramatically even if they perform slightly more arithmetic.

-Means++ initialization: Uniform random initialization can place multiple initial centers in one dense cluster, trapping Lloyd's algorithm in poor local optima. -Means++ chooses the first center uniformly at random and selects each subsequent center with probability proportional to (where is distance to the nearest already-chosen center), spreading seeds across modes and guaranteeing an -competitive expected clustering cost.

Answer:

Off-chip DRAM transfers cost orders of magnitude more energy than ALU ops, making cache-locality optimization central to green algorithms. -Means++ spreads initial centroids with -weighted sampling to guarantee expected approximation quality.

Question 5

Explain the trade-off between DVFS slowdown and race-to-sleep in green computing. Re-evaluate the processor task from Example 3 (, ), except now static leakage power is much higher at (assuming the machine cannot sleep until the task completes, and enters deep sleep afterwards). Compare total energy at , , and to see which frequency minimizes energy.

DVFS slowdown vs. race-to-sleep trade-off: Slowing frequency shrinks dynamic energy quadratically (), but stretches runtime , increasing static leakage energy . When static power is large, running too slowly wastes more static energy than dynamic energy saved, favoring race-to-sleep (or an interior optimal frequency ).

Compare total energy :

  • : .
  • : .
  • : .

(Setting gives the exact minimum at , where !)

Answer:

High static leakage penalizes long runtimes, creating an optimal energy point balancing against . Among the three speeds, () beats () and (), with global minimum near ().

← Online and Streaming Algorithms