Advanced Algorithms · Lecture Notes
Chapter 8: Online Algorithms
Most of the algorithms in this course see their entire input before they start. A sorting algorithm holds the whole array, and Dijkstra's algorithm holds the whole graph. In real systems, however, input often arrives piece by piece. A cache must decide which page to evict without knowing the next page request. A trading program buys or sells today without knowing tomorrow's price. Such decisions cannot be undone once they are made. Online algorithms are the algorithms that work under these conditions. These notes first set up the online problem model and competitive analysis: an online algorithm is judged against the best solution that knows the future. Three classical problems follow: ski rental, paging, and list update. For each of them we prove both an algorithm and a lower bound that says no algorithm can do better. The second half of the notes turns to data streams. Moving averages, online median, reservoir sampling, and pattern search in a stream are algorithms that look at each item once and use little memory. The notes close with incremental learning and a general comparison of the topic.
Learning outcomes
- Model
- Distinguish the online and offline problem models, and explain irrevocable decisions with examples.
- Competitive analysis
- Define the competitive ratio and prove lower bounds with the adversary model. For ski rental, prove that the break-even strategy achieves the ratio 2 − 1/B and that this is the best possible value for deterministic algorithms.
- Paging and lists
- Compute page faults step by step under FIFO, LRU, and OPT; exhibit Belady's anomaly; interpret why LRU is k-competitive and why move-to-front is 2-competitive.
- Data streams
- Write moving average, online median, reservoir sampling, and rolling-hash pattern search in Java; analyze time per item and memory.
8.1The online problem model
An algorithm's input can arrive in two ways. In the first, the entire input is available before the algorithm starts. In the second, the input is revealed over time, piece by piece, and the algorithm must answer each piece immediately. This chapter studies the second setting. We first describe the model itself, and then how "a good algorithm" is measured in it.
8.1.1When information arrives piece by piece
Most everyday decisions are made with incomplete information. A chess player moves without knowing the opponent's next move. Once made, a move cannot be taken back. After the opponent replies, the player may think "I should have moved the other piece", but the position on the board does not change. A driver in a traffic jam likewise chooses which road to turn onto using only what is known at that moment, and learns that the road is closed ahead only on reaching it.
A traveler walking through a maze is a good example. The maze as a whole is invisible; the traveler sees only the corridor ahead. At each junction a direction is chosen from what has been seen so far. Someone with a bird's-eye map of the same maze finds the shortest path without ever going wrong, while the traveler is forced into some dead ends. The question an online algorithm asks is this: in the worst case, how much farther does the traveler without a map walk than the one with a map?
The same structure is common in computer systems. A program that controls traffic lights measures the density at the intersection in real time and adjusts the green phase accordingly. It does not know how many cars will arrive from which direction a minute later. Waiting is not an option either: the light has to show some color now. An online algorithm is an algorithm that works under these conditions.
An online algorithm receives its input as a sequence of requests σ = σ1, σ2, …, σn, one at a time. When σt arrives, the algorithm makes a decision. This decision depends only on the requests σ1, …, σt and cannot be changed afterwards. An offline algorithm, in contrast, sees the whole sequence from the start.
The two conditions in the definition matter together. First, the future is unknown: when σt arrives there is no information about σt+1. Second, a decision, once made, cannot be undone. With only the first condition, the algorithm could wait for the entire input and then decide. With only the second, an algorithm that knew the future would make the right decision every time. The difficulty comes from having both at once.
8.1.2Online versus offline
The difference between the two models lies not in the content of the input but in when the algorithm sees it. The same request sequence can be processed in either model. An offline algorithm looks at the whole sequence, computes the best decisions, and then carries them out. An online algorithm answers each request at the moment it arrives. Table 8.1 compares the two models along five dimensions.
| Offline | Online | |
|---|---|---|
| Input | Known in full from the start | Arrives piece by piece; when σt arrives, σt+1 is unknown |
| Decision | Made by looking at the whole input | Made the moment σt arrives, irrevocable |
| Examples | Sorting, Dijkstra, knapsack (dynamic programming) | Cache management, ski rental, stock trading |
| Optimal solution | OPT can be computed | OPT is known only in hindsight |
| Measure | Time and space complexity | Competitive ratio: ALG / OPT |
The last row of the table carries the main idea of the chapter. For an offline algorithm, "good" usually means "fast": the algorithm finds the optimal solution, and the question is how long it takes. An online algorithm often cannot find the optimal solution at all, because the optimum depends on the future. Here the question is how far the total cost of the decisions made is from the optimum. The number that measures this distance is called the competitive ratio.
The word "online" here has nothing to do with an internet connection. It describes the input being revealed over time. Even a sorting algorithm can be online or not, and two familiar sorting algorithms are enough to see this.
Question. Numbers arrive one at a time: 5, 2, 8, 1. After each number arrives, the sorted version of the numbers so far must be ready. Can insertion sort and selection sort satisfy this requirement?
Solution. Insertion sort places each new number into the sorted part. When 5 arrives the array is [5]. When 2 arrives, 5 shifts one place right and the array is [2, 5]. When 8 arrives the comparison ends at the first step: [2, 5, 8]. When 1 arrives, three items shift: [1, 2, 5, 8]. At every step the array is sorted, and the algorithm never needs to know the future. Selection sort, in contrast, picks the minimum of the whole input in its first pass. When 5 arrives it cannot write it to the first position, because it does not know whether a smaller number will come. Indeed, the smallest number (1) arrives last. Insertion sort can run online; selection sort cannot. Merge sort and quicksort also need the whole input to split it in two.
8.1.3Bounded memory and work per item
The most common practical form of the online model is continuously arriving data. Sensors produce thousands of measurements per second, and millions of packets pass through a network router every second. Storing all of this data is usually impossible. Figure 8.1 shows the situation: data keeps arriving at the algorithm, the algorithm works with a small buffer, and it produces output immediately.
If the buffer cannot hold the whole input, the past can be kept only as a summary. A summary may be a sum, a counter, two heaps, or a small sample. Choosing the right summary is the heart of stream algorithm design. A summary needs two properties. First, it must be quickly updatable when a new item arrives. Second, the question being asked must be answerable from the summary. For example, to answer "what is the average so far?", the item count and the sum are enough. With each new item, the sum and the counter are each updated once, and the average is obtained with one division.
For this reason two costs are measured in stream algorithms: work per item and memory. We usually want the work per item to be O(1) or O(log n). An algorithm that does O(n) work per item does O(n²) work in total after n items arrive. In a stream delivering a million items per second this is unacceptable. Memory, too, must be independent of the stream length or very small relative to it.
8.1.4Application areas
Online problems appear in almost every area of computer science. Table 8.2 collects the main examples. They share three features: the environment is dynamic, decisions are made in real time, and information about the future is incomplete.
| Area | Online decision |
|---|---|
| Stock market | Buy or sell according to the current price; the future price is unknown. |
| Caching | Which page stays in memory in a processor, an operating system, or a web cache. |
| Routing | Which path a packet takes in a network whose links keep changing. |
| Resource allocation | Dynamic sharing of bandwidth and processor time. |
| Scheduling | Assigning arriving jobs to machines (job scheduling). |
| Advertising and recommendation | Which advertisement or product to show when a user enters a page. |
| Machine learning | Updating a model with every new example (incremental learning). |
| Security | Catching fraud and distributed denial-of-service (DDoS) attacks on the stream. |
| Autonomous vehicles | Real-time decisions as sensor data arrives. |
In some of these areas the decision is irrevocable, and in others undoing it is expensive. A page evicted from a cache can be loaded back, but loading has a cost. A displayed advertisement cannot be undone; the ad slot cannot be given to another ad. The model is always the same: every decision has a cost, and we want to minimize the total cost.
8.1.5Strengths and weaknesses
The greatest strength of online algorithms is that they do not wait. They do not wait for the input to end, and they work in dynamic environments. Because decisions are made on the spot, latency is low. With little memory they can process very large, even infinite, streams. Thanks to the competitive ratio, a worst-case guarantee can also be given: for example, "whatever happens, the cost never exceeds twice the optimum."
The weaknesses come from the same place. A wrong decision in the early steps affects later steps. In chess, a single bad move can lose the game. An online algorithm does not guarantee finding the best global solution. It is sensitive to the initial input: the same algorithm may do very well on one sequence and badly on another. Its design and analysis are also harder than those of offline algorithms, since the analysis has to evaluate the algorithm's behavior against every possible future not yet seen.
8.1.6Design approaches
Online algorithms are built on a few common ideas. They are not mutually exclusive; an algorithm may use several together.
- Greedy approach: serve the arriving request in the way that looks best at that moment, without considering global effects. Assigning each arriving request to the nearest idle server is of this kind.
- Summarization: instead of storing the entire past, keep a small summary. A moving average keeps a sum and a queue, an online median keeps two heaps, and reservoir sampling keeps a fixed-size sample.
- Adaptive approach: learn from past requests and change behavior over time. An LRU cache keeps recently used pages. The move-to-front rule brings frequently requested items to the head of the list. Incremental learning updates the model with every new example.
- Deterministic approach: always make the same decision on the same input. This predictability is also a weakness. A malicious input generator that knows the algorithm, an adversary, can easily trap it.
- Randomized approach: add chance to the decisions. The adversary cannot know in advance what the algorithm will do. Reservoir sampling and the randomized marking algorithm are of this kind.
The difference between deterministic and randomized approaches shows up in numbers in competitive analysis. In ski rental the best deterministic ratio is close to 2, while a randomized strategy comes down to about 1.58. In paging the deterministic ratio is k, while that of the randomized marking algorithm is around 2 ln k.
8.2Competitive analysis
For offline algorithms the usual measure is time complexity. For online algorithms this measure is not enough. A cache policy may do O(1) work per request and still produce a large number of unnecessary page faults. What really needs to be measured is the quality of the decisions. Measuring quality requires a point of comparison. That point is the best algorithm that knows the future.
8.2.1The competitive ratio
Let a request sequence σ be given. The total cost of the online algorithm on this sequence is denoted ALG(σ). The cost of the best offline algorithm, which knows the whole sequence in advance, is denoted OPT(σ). OPT is less an algorithm than a yardstick: it gives the smallest cost attainable on each sequence. Whatever the online algorithm does, its cost cannot be below OPT. The question is how much larger than OPT it can be.
In a cost-minimization problem, an online algorithm ALG is c-competitive if, for every request sequence σ,
ALG(σ) ≤ c · OPT(σ) + α
holds. Here α is a constant independent of σ. If α = 0, the algorithm is strictly c-competitive. The smallest c satisfying this condition is called the algorithm's competitive ratio. When α = 0, the ratio is the supremum of ALG(σ) / OPT(σ) over all sequences.
Three aspects of the definition deserve emphasis. First, the condition must hold for every sequence. Competitive analysis is a worst-case analysis; it contains no average-case or probabilistic assumption. Saying "it usually works well on real sequences" does not give a competitive ratio. Second, the closer the ratio is to 1, the less the lack of knowledge about the future hurts. An online algorithm with ratio 1 is as good as an algorithm that knows the future. Third, the additive constant α leaves start-up effects out. For example, if the cache is initially empty, the first few faults occur in every algorithm. These faults are insignificant on long sequences, and α absorbs them.
The definition is for cost problems: the goal is to minimize cost, and the ratio is always c ≥ 1. In some problems, however, a gain is maximized. In ad placement, for example, total revenue is to be increased. For gain problems the ratio is defined by inverting it, as OPT / ALG, so the ratio is again at least 1.
Question. An online algorithm costs 12, 30, 8, and 50 on four request sequences; on the same sequences OPT costs 6, 20, 8, and 25. If these were the only four sequences, what would the algorithm's competitive ratio be? What do these numbers say about the true ratio?
Solution. The ratios are 12/6 = 2, 30/20 = 1.5, 8/8 = 1, and 50/25 = 2. Because the competitive ratio measures the worst case, we look at the maximum rather than the average: 2. Although the average ratio is 1.625, this number gives no guarantee. The true competitive ratio is defined over all possible sequences. These four sequences show that the ratio is at least 2. To show that it does not exceed 2, a proof valid for every sequence is required.
8.2.2The adversary model
To show that an algorithm's competitive ratio is at least c, a single bad sequence suffices. Showing that no algorithm can do better than c is harder: a separate bad sequence must be constructed against every algorithm. The tool that organizes this construction is the adversary model. The adversary is an imaginary opponent playing against the algorithm. It generates the request sequence and also solves the same sequence with OPT. Its goal is to make the ratio ALG(σ) / OPT(σ) as large as possible.
What the adversary knows depends on the type of algorithm being analyzed.
- The adversary against a deterministic algorithm knows the algorithm's code. Because the algorithm is deterministic, the adversary can compute in advance what it will do at each step. At each step it generates the request that hurts the algorithm most.
- The oblivious adversary is used against randomized algorithms. It knows the algorithm's code but cannot see the coin flips. It therefore chooses the sequence in advance. The algorithm's expected cost is measured.
- The adaptive adversary sees the algorithm's random decisions and chooses the next request accordingly. Against this adversary, most of the benefit of randomization is lost.
Lower-bound proofs always follow the same pattern. To say "no deterministic algorithm can be better than c", take an arbitrary ALG. Against this ALG, construct a sequence σ with ALG(σ) / OPT(σ) ≥ c. Because ALG was arbitrary, the result holds for all deterministic algorithms. The power of the pattern comes from the adversary knowing ALG. A deterministic algorithm cannot hide what it will do in the next step, and the adversary exploits exactly that step. In ski rental, the adversary ends the season on the day the algorithm buys the skis. In paging, it requests the page that is not in the algorithm's cache.
Confusing the competitive ratio with average-case behavior. The inference "LRU gives results very close to OPT on real programs, so its ratio is close to 1" is wrong. The competitive ratio is defined by the worst sequence. LRU's ratio is k, because there is a sequence that makes it fault on every request. Good performance on real sequences is a separate observation; it comes from locality and is not a guarantee.
8.3Ski rental
Ski rental is the simplest example of an online algorithm. There is a single decision: when to buy. Even so, the problem contains every part of competitive analysis: an OPT that knows the future, a simple strategy, an upper bound for that strategy, and a lower bound that no strategy can beat.
8.3.1The problem
A skier goes to the ski resort every morning throughout the season. A set of skis can be rented for 1 TL per day or bought for B TL. Bought skis are free for the rest of the season. The skier does not know how long the season will last. Each morning the skier learns only the answer to "will I ski today too?" If the weather turns bad one day, the season ends that day. The total number of skiing days is denoted d.
The ski rental problem: renting costs 1 per day, buying costs B units. At the start of each skiing day the algorithm chooses one of two options: rent for that day, or buy. After buying there is no further cost. The number of days d is not known in advance. The goal is to minimize the total cost.
For OPT, which knows the future, the problem is easy. If d is known, the two options are compared. Renting every day costs d, and buying on the first day costs B. Buying on some day in between is never better: paying rent for a few days and buying later costs more than buying on day one. Therefore
OPT(d) = min(d, B)
holds. If d < B, OPT always rents; if d ≥ B, it buys on the first day. The online algorithm, however, does not know d. Whichever day it picks, the adversary can end the season in the way that is worst for it. Figure 8.2 shows OPT's cost for B = 10 together with the cost of the break-even strategy examined below.
The structure of the problem is not limited to skiing. A cloud server can be rented by the hour or bought for a year. A TCP connection can be kept open, or closed and reopened when needed. Keeping it open costs a little every second, while reopening is a single large cost. A thread can spin while waiting for a lock to be released, or go to sleep. Spinning is like renting; sleeping and being woken up is like buying. In all of them the question is the same: how long should the small recurring cost be paid, and when should we switch to the large one-time cost?
8.3.2The cost of three strategies
A deterministic strategy is defined by a single number: the buying day k. The strategy rents for k − 1 days and buys on day k if the skier is still skiing. If the season ends before day k, it never buys. This family has three natural members.
- Always rent (k = ∞): the cost is always d. As d grows, OPT stays fixed at B while the cost increases without bound. The ratio is d / B, which goes to infinity as d → ∞. This strategy is not competitive.
- Buy on day one (k = 1): the cost is always B. But if the season lasts a single day, OPT is 1. The ratio is B. If B is large, this is very bad.
- Break-even (k = B): rent for B − 1 days and buy on day B. It buys at the moment the total paid in rent approaches the purchase price.
Figure 8.3 plots the cost of these three strategies together with OPT as a function of the number of days, for B = 10. Table 8.3 gives the same values numerically for a few values of d.
| d | OPT | Always rent | Buy on day 1 | Break-even |
|---|---|---|---|---|
| 1 | 1 | 1 (1) | 10 (10) | 1 (1) |
| 5 | 5 | 5 (1) | 10 (2) | 5 (1) |
| 9 | 9 | 9 (1) | 10 (1.11) | 9 (1) |
| 10 | 10 | 10 (1) | 10 (1) | 19 (1.9) |
| 15 | 10 | 15 (1.5) | 10 (1) | 19 (1.9) |
| 50 | 10 | 50 (5) | 10 (1) | 19 (1.9) |
| 1000 | 10 | 1000 (100) | 10 (1) | 19 (1.9) |
The table shows the weaknesses of the strategies clearly. Always-rent is perfect on short seasons and a disaster on long ones. Buy-on-day-one is perfect on long seasons and B times worse on short ones. Break-even is never perfect, but it is never worse than 1.9 times optimal. Competitive analysis looks for exactly this kind of balance: the strategy that makes the worst case best.
8.3.3The break-even strategy: code and trace
The Java code of the break-even strategy is below. The method takes the actual season length d as a parameter. This is for simulation only: the algorithm does not know d. At the start of each day the loop only "sees" whether skiing happens that day; it makes no decision based on the value of d.
int breakEven(int B, int d) { // d is unknown
int cost = 0;
for (int day = 1; day <= d; day++) {
if (day < B) {
cost += 1; // rent
} else {
cost += B; // buy
break; // no more fees
}
}
return cost;
}The code works line by line as follows. cost starts at zero. The loop runs from day 1 to day d; each iteration stands for one skiing day. If day < B, the skis are rented for that day and the cost grows by 1. The first time day equals B, the else branch runs: B is added to the cost and break leaves the loop. The skis now belong to the skier; the remaining days are free. If the season ends before day B, the loop ends on its own and no purchase is made.
The method's time is O(min(d, B)): the loop runs at most B times. Memory is O(1). For online algorithms, though, the interesting quantity is not this running time but the ratio of the returned cost to OPT. Table 8.4 gives a trace of the code for B = 4 and d = 6. Figure 8.4 shows the final state of the same run.
day | day < B | Decision | cost |
|---|---|---|---|
| 1 | true | rent | 1 |
| 2 | true | rent | 2 |
| 3 | true | rent | 3 |
| 4 | false | buy, break | 3 + 4 = 7 |
| 5 | — | loop ended; skis are free | 7 |
| 6 | — | loop ended; skis are free | 7 |
The result is ALG = 7. Because OPT knows the season will last 6 days, it buys on the first day and pays 4. The ratio is 7/4 = 1.75, which equals 2 − 1/4. Had the season ended on day 4, ALG would still be 7 and OPT 4. Had it ended on day 3, ALG would be 3, and OPT would also pay 3. A general version of the code takes the buying day as a separate parameter:
int skiCost(int B, int k, int d) {
int cost = 0;
for (int day = 1; day <= d; day++) {
if (day == k) { cost += B; break; } // buy
cost += 1; // rent
}
return cost;
}This method computes the cost of the strategy that buys on day k. skiCost(B, B, d) gives the same value as breakEven(B, d) for every B and d. The two methods were run and compared for 1 ≤ B ≤ 15 and 1 ≤ d ≤ 40; all values were equal.
Forgetting break. Without break in the else branch the loop continues, and after day B another B is added every day. The skier ends up buying a new set of skis every morning. For B = 4 and d = 6 the cost comes out as 3 + 4 + 4 + 4 = 15; as d grows the ratio grows without bound. Writing the condition as day <= B is also an off-by-one error. The strategy then rents for B days and buys on day B + 1. For d = B + 1 the cost is 2B and OPT is B, so the ratio rises to 2 instead of 2 − 1/B.
8.3.4Upper bound: the ratio of break-even
The ratio in the trace is no coincidence. The ratio of the break-even strategy never exceeds 2 − 1/B for any d.
The strategy that rents for B − 1 days and buys on day B is strictly (2 − 1/B)-competitive. That is, ALG(d) ≤ (2 − 1/B) · OPT(d) for every d ≥ 1, with equality when d ≥ B.
There are two cases. If d < B, the strategy never buys; it rents for d days and pays d. OPT also pays min(d, B) = d. The ratio is 1. If d ≥ B, the strategy pays B − 1 days of rent and buys on day B: ALG = (B − 1) + B = 2B − 1. OPT buys on the first day and pays B. The ratio is (2B − 1)/B = 2 − 1/B. In both cases the ratio does not exceed 2 − 1/B. □
The proof also explains why the break-even idea works. Up to the moment of buying, the algorithm never pays more than OPT would. At the moment of buying, it pays in total at most "one rent and one purchase", each of which is at most OPT. Therefore the total cannot exceed twice OPT. This same "at most twice" idea appears in many online problems.
8.3.5Lower bound: why nothing does better
The break-even strategy achieves the ratio 2 − 1/B. Could a cleverer deterministic strategy lower it? The adversary model shows that this is impossible.
For the ski rental problem, no deterministic online algorithm has a competitive ratio smaller than 2 − 1/B.
Every deterministic strategy is defined by a buying day k. The strategy that never buys is k = ∞; its ratio is unbounded. The adversary knows the strategy and ends the season exactly on the buying day: d = k. The algorithm then pays k − 1 days of rent and one purchase: ALG = (k − 1) + B. OPT pays min(k, B). There are two cases.
If k < B, the ratio is (k − 1 + B)/k = 1 + (B − 1)/k. Since k ≤ B − 1, we have (B − 1)/k ≥ 1, so the ratio is at least 2. That is greater than 2 − 1/B.
If k ≥ B, the ratio is (k − 1 + B)/B. The numerator grows with k; the smallest value occurs at k = B: (2B − 1)/B = 2 − 1/B.
For every k, the ratio on the adversary's chosen sequence is at least 2 − 1/B. □
Table 8.5 gives the ratio the adversary obtains against different buying days for B = 10. Buying too early and buying too late are both bad; the worst-case ratio is smallest exactly at k = B.
| k | Rent | ALG | OPT | Ratio |
|---|---|---|---|---|
| 1 | 0 | 10 | 1 | 10 |
| 2 | 1 | 11 | 2 | 5.5 |
| 5 | 4 | 14 | 5 | 2.8 |
| 9 | 8 | 18 | 9 | 2 |
| 10 | 9 | 19 | 10 | 1.9 |
| 11 | 10 | 20 | 10 | 2 |
| 15 | 14 | 24 | 10 | 2.4 |
| 20 | 19 | 29 | 10 | 2.9 |
The adversary's choice d = k really is the worst choice. If d < k, the algorithm never buys and pays only rent; the ratio is at most 1. If d > k, the algorithm's cost does not change while OPT's cost may grow or stay the same; the ratio does not grow. This observation was also verified by simulation. For B = 10, the strategies k = 3, 5, 10, 14 were run for d = 1, …, 60. In each, the worst ratio occurred at d = k: 4, 2.8, 1.9, and 2.3 respectively.
Question. In ski rental, B = 20. What is the competitive ratio of the break-even strategy? What is the worst ratio of the strategy that buys on day 5?
Solution. The ratio of the break-even strategy is 2 − 1/20 = 1.95. The adversary ends the season on day 20: ALG = 19 + 20 = 39, OPT = 20, ratio 39/20 = 1.95. Against the strategy that buys on day 5, the adversary picks d = 5. The algorithm pays 4 days of rent and a purchase: 4 + 20 = 24. Because OPT knows the season lasts 5 days, it rents throughout and pays 5. The ratio is 24/5 = 4.8. The early-buying strategy is about 2.5 times worse than break-even.
8.3.6A randomized strategy
The power of the lower-bound proof comes from the adversary knowing the buying day. If the algorithm picks its buying day at random, the adversary loses this information. The oblivious adversary must choose the sequence, that is, d, in advance. The algorithm's expected cost is measured.
Question. Let B = 2. The ratio of the deterministic break-even strategy is 2 − 1/2 = 1.5. If the algorithm buys on day 1 with probability p and on day 2 with probability 1 − p, what is the expected ratio? What is the best p?
Solution. The adversary has two meaningful choices. If it picks d = 1, the strategy that buys on day 1 pays 2 and the one that buys on day 2 pays 1; OPT is 1. The expected ratio is 2p + (1 − p) = 1 + p. If it picks d ≥ 2, the day-1 buyer pays 2 and the other pays 1 + 2 = 3; OPT is 2. The expected ratio is (2p + 3(1 − p))/2 = (3 − p)/2. The adversary picks the larger. The algorithm minimizes the worst case by equating the two values: 1 + p = (3 − p)/2, so p = 1/3. The expected ratio is 4/3 ≈ 1.33. Randomization lowered the ratio from 1.5 to 1.33. p = 0 is the deterministic break-even strategy, with worst ratio 1.5; p = 1/2 also gives 1.5.
The same idea generalizes to every B. Karlin, Manasse, McGeoch, and Owicki (1994) found the best randomized strategy. In this strategy, the probability of buying on day i is proportional to ((B − 1)/B)B − i; that is, later days get larger probability. The resulting expected ratio is
1 / (1 − (1 − 1/B)B)
For B = 2 this formula gives 1/(1 − 1/4) = 4/3, matching the value in the example. As B grows, (1 − 1/B)B approaches 1/e, and the ratio goes to e/(e − 1) ≈ 1.58. Table 8.6 compares the deterministic and randomized ratios.
| B | Deterministic 2 − 1/B | Randomized (expected) |
|---|---|---|
| 2 | 1.5 | 1.333 |
| 3 | 1.667 | 1.421 |
| 4 | 1.75 | 1.463 |
| 10 | 1.9 | 1.535 |
| 100 | 1.99 | 1.577 |
| B → ∞ | 2 | e/(e − 1) ≈ 1.582 |
For B = 10, the probabilities increase from 0.059 on day 1 to 0.154 on day 10. With this distribution the expected ratio was computed for every d; the worst value came out as 1.535. Randomization takes away the adversary's strongest weapon, knowing when the algorithm will buy. But there is a limit to this too. Karlin et al. showed that these ratios are also the best possible for randomized strategies. For large B, no randomized strategy can do noticeably better than e/(e − 1).
8.4Paging
Paging is the most studied online problem. It appears everywhere in the memory organization of computers: in the processor cache, in the operating system's virtual memory, in the database buffer, and in the web browser's cache. In all of them a small, fast memory holds part of a large, slow memory. Which part to keep is decided without knowing future requests.
8.4.1The problem
Consider a two-level memory. The fast memory, the cache, can hold k pages at a time. The slow memory is unbounded and contains all pages. The processor requests pages one after another. If the requested page is in the cache, this is a hit and costs 0. If the page is not in the cache, a page fault occurs. The page is loaded from slow memory and the cost is 1. If the cache is full, a page must be evicted to make room for the new one. Figure 8.5 shows this moment.
The paging problem: given a cache of k pages and a sequence σ of page requests. Each request is either a hit (cost 0) or a page fault (cost 1). On a fault, if the cache is full, the algorithm chooses the page to evict. The goal is to minimize the total number of page faults. The rule that chooses the page to evict is called the eviction policy.
In this model only faults are counted. In a real system a hit also has a small cost, but loading from slow memory is hundreds or even millions of times more expensive. Reading a page from disk takes milliseconds, and reading from memory takes nanoseconds. For this reason the number of faults is the main determinant of performance. The model also loads a page only on a fault; there is no prefetching. This restriction does not lose generality: any algorithm that prefetches can be converted into one that postpones loading until it is really needed, without increasing the number of faults.
The problem is a typical online problem. Which page should be evicted depends on future requests. If we knew which page would be requested next, the right choice would be easy. But the algorithm sees only the past.
8.4.2Eviction policies
Eviction policies use different pieces of information from the past. Table 8.7 lists the main ones with their competitive ratios.
| Policy | Which page does it evict? | Online? | Competitive ratio |
|---|---|---|---|
| FIFO | The page loaded into the cache earliest (a queue) | yes | k |
| LRU | The page unused for the longest time (least recently used) | yes | k |
| FWF | Flushes everything on a fault when the cache is full (flush when full) | yes | k |
| LFU | The least frequently used page | yes | unbounded |
| LIFO | The most recently loaded page | yes | unbounded |
| OPT (MIN) | The page whose next use is farthest in the future (Belady, 1966) | no | 1 |
FIFO (first in, first out) manages the cache like a queue. The page at the head of the queue, that is, the one loaded earliest, is evicted. It ignores how often a page is used. LRU tracks the last use time of each page and evicts the oldest. It assumes that a page used in the recent past will soon be used again. FWF is a crude policy. If a fault occurs while the cache is full, it discards all pages and starts over. Crude as it looks, its competitive ratio is the same as that of FIFO and LRU: k.
LFU and LIFO, on the other hand, are not competitive. Why LIFO is bad can be seen on a small sequence. For k = 3, consider the sequence 1 2 3 4 3 4 3 4 …. The first three requests fill the cache. When 4 arrives, LIFO evicts 3, the most recently loaded. Then 3 is requested, and this time 4, the most recently loaded, is evicted. As the sequence continues like this, every request is a fault. OPT, in contrast, evicts 1 when 4 arrives, since 1 will never be requested again, and then never faults. As the sequence grows, LIFO's fault count grows while OPT's stays at 4. The ratio grows without bound. LFU is trapped in a similar way. If pages 1 and 2 are requested m times and then 3 and 4 are requested alternately, LFU keeps 1 and 2, whose counters are large. Pages 3 and 4 evict each other until their counters approach m. As m grows, so does the ratio.
OPT is the policy Belady defined in 1966; it is also known as MIN or "longest forward distance". On a fault it looks at the next use of every page in the cache and evicts the one used farthest in the future. If some page will never be used, it is evicted first. OPT requires knowing the future, so it cannot be implemented in a real system. But it is indispensable as a yardstick. It is proven to give the fewest page faults on every sequence. This is exactly the OPT in the competitive ratio.
8.4.3FIFO step by step
To compare the three policies on the same sequence we use the request sequence 7 0 1 2 0 3 0 4 2 3 0 3 2 and k = 3. In this sequence page 0 is requested often and the other pages rarely. Figure 8.6 shows FIFO's slot contents after each request; S1, S2, and S3 are the three slots of the cache. A newly loaded page is written into the slot of the evicted page, so positions within the slots do not show the loading order. The loading order is in the queue column of Table 8.8.
| # | Request | Result | Evicted | Queue | Fault |
|---|---|---|---|---|---|
| 1 | 7 | F | — | [7] | 1 |
| 2 | 0 | F | — | [7, 0] | 2 |
| 3 | 1 | F | — | [7, 0, 1] | 3 |
| 4 | 2 | F | 7 | [0, 1, 2] | 4 |
| 5 | 0 | ✓ | — | [0, 1, 2] | 4 |
| 6 | 3 | F | 0 | [1, 2, 3] | 5 |
| 7 | 0 | F | 1 | [2, 3, 0] | 6 |
| 8 | 4 | F | 2 | [3, 0, 4] | 7 |
| 9 | 2 | F | 3 | [0, 4, 2] | 8 |
| 10 | 3 | F | 0 | [4, 2, 3] | 9 |
| 11 | 0 | F | 4 | [2, 3, 0] | 10 |
| 12 | 3 | ✓ | — | [2, 3, 0] | 10 |
| 13 | 2 | ✓ | — | [2, 3, 0] | 10 |
The critical moment in the trace is the 6th request. Page 0 had just been used, at the 5th request. FIFO does not take this into account. Because 0 is at the head of the queue, it is evicted. Right after that, at the 7th request, 0 is requested again and an unnecessary fault occurs. The same happens at the 11th request: 0 was evicted at the 10th request and requested again one request later. FIFO makes 10 faults in total.
8.4.4LRU step by step
On every hit, LRU updates the page's last use time. This small difference keeps frequently used pages in the cache. Figure 8.7 shows how LRU processes the same sequence, and Table 8.9 shows the usage order at each step.
| # | Request | Result | Evicted | Usage order | Fault |
|---|---|---|---|---|---|
| 1 | 7 | F | — | [7] | 1 |
| 2 | 0 | F | — | [7, 0] | 2 |
| 3 | 1 | F | — | [7, 0, 1] | 3 |
| 4 | 2 | F | 7 | [0, 1, 2] | 4 |
| 5 | 0 | ✓ | — | [1, 2, 0] | 4 |
| 6 | 3 | F | 1 | [2, 0, 3] | 5 |
| 7 | 0 | ✓ | — | [2, 3, 0] | 5 |
| 8 | 4 | F | 2 | [3, 0, 4] | 6 |
| 9 | 2 | F | 3 | [0, 4, 2] | 7 |
| 10 | 3 | F | 0 | [4, 2, 3] | 8 |
| 11 | 0 | F | 4 | [2, 3, 0] | 9 |
| 12 | 3 | ✓ | — | [2, 0, 3] | 9 |
| 13 | 2 | ✓ | — | [0, 3, 2] | 9 |
The difference starts at the 5th request. When 0 gets a hit, LRU moves it to the end of the order. At the 6th request, the evicted page is no longer 0 but 1, which has gone unused the longest. At the 7th request 0 gets a hit again. The unnecessary faults FIFO made at these two requests do not occur in LRU. There are moments when LRU is also helpless. At the 10th request 0 is the least recently used page and is evicted; at the 11th request it is requested again. LRU makes 9 faults in total.
8.4.5OPT step by step
OPT looks to the future at every fault. For each page in the cache it finds the position of the next request, and evicts the farthest one. Figure 8.8 shows OPT's slots, and Table 8.10 gives the next-use positions computed at each eviction.
| # | Request | Cache | Next use | Evicted | Fault |
|---|---|---|---|---|---|
| 4 | 2 | {7, 0, 1} | 7: none, 0: 5th, 1: none | 7 | 4 |
| 6 | 3 | {2, 0, 1} | 2: 9th, 0: 7th, 1: none | 1 | 5 |
| 8 | 4 | {2, 0, 3} | 2: 9., 0: 11., 3: 10. | 0 | 6 |
| 11 | 0 | {2, 4, 3} | 2: 13th, 4: none, 3: 12th | 4 | 7 |
The first three requests are compulsory faults. At the 4th request the cache holds 7, 0, and 1. Neither 7 nor 1 is ever requested again; either can be evicted. OPT evicts 7. Evicting 1 would give the same number of faults: 1 would be evicted at the 6th request anyway. The decision at the 8th request is the most instructive. Page 0 is the most frequently requested page in the sequence, but its next use is the farthest away: the 11th request. OPT evicts it. Pages 2 and 3 get hits at the 9th and 10th requests. LRU had evicted 2 at the same moment and made two faults. OPT makes 7 faults in total.
Understanding OPT as "evict the page that will be used least". OPT looks not at how many times a page will be used in the future but at when its next use is. In the sequence above, page 0 is requested once more in the future and 4 never again. Even so, 0 is evicted at the 8th request, because the candidates in the cache are 2, 0, and 3; 4 is not in the cache at that moment. Among the candidates, 0 has the farthest next use.
8.4.6Comparing the three policies
Table 8.11 gives the results of the three policies together.
| Policy | Page faults | Hits | ALG / OPT | Information needed |
|---|---|---|---|---|
| FIFO | 10 | 3 | 1.43 | Loading order (queue) |
| LRU | 9 | 4 | 1.29 | Last use time |
| OPT | 7 | 6 | 1 | All future requests |
The first k = 3 faults cannot be avoided in any policy. The cache is initially empty, and the first three distinct pages must be loaded no matter what. These faults are called compulsory misses or cold misses. Even OPT cannot make zero faults. The constant α in the definition of the competitive ratio exists precisely to absorb start-up effects like these.
The reason LRU beats FIFO is locality of reference. Programs do not access memory at random. A loop accesses the same variables again and again; an array is read from consecutive addresses. A page used in the recent past will be used again soon. LRU exploits this regularity, and FIFO does not. In the example sequence, because page 0 is requested often, FIFO evicted it twice unnecessarily.
In real systems LRU itself is expensive. Updating a timestamp on every memory access is a heavy burden for hardware. For this reason operating systems use cheap approximations close to LRU. The best known is the clock algorithm, also called second chance. Each page has a "referenced" bit; the hardware sets the bit to 1 when the page is accessed. Pages sit in a circular list, and a hand sweeps around it. When an eviction is needed, the hand clears the bit of a page whose bit is 1 and moves on, and evicts the first page whose bit is 0. Recently used pages thus get one more round of grace.
8.4.7Java code and trace for LRU
The most direct implementation of LRU uses a linked list. The head of the list is the least recently used page and the tail the most recently used. The method takes the request sequence and the cache size and returns the total number of page faults.
int lruFaults(int[] requests, int k) {
var cache = new LinkedList<Integer>();
int faults = 0;
for (int page : requests) {
if (cache.remove((Integer) page)) {
cache.addLast(page); // make newest
} else {
faults++;
if (cache.size() == k)
cache.removeFirst(); // drop oldest
cache.addLast(page);
}
}
return faults;
}The core of the code is the call cache.remove((Integer) page). This call does two jobs at once. If the page is in the list, it removes it and returns true; otherwise it returns false. In the true case the page was a hit. addLast puts it back at the end of the list, in the "newest" position. In the false case there is a page fault. The fault counter increases. If the cache is full, removeFirst drops the page at the head of the list, the least recently used. Finally the new page is appended at the end.
Table 8.12 traces the code with the sequence 1 2 3 1 4 2 and k = 3.
page | remove | Action | cache | faults |
|---|---|---|---|---|
| 1 | false | room left; append | [1] | 1 |
| 2 | false | room left; append | [1, 2] | 2 |
| 3 | false | room left; append | [1, 2, 3] | 3 |
| 1 | true | hit; append | [2, 3, 1] | 3 |
| 4 | false | full; drop the head, 2 | [3, 1, 4] | 4 |
| 2 | false | full; drop the head, 3 | [1, 4, 2] | 5 |
The method returns 5 (Figure 8.9). The hit at the 4th request is important: 1 moves from the head of the list to the tail. Because of this, at the 5th request 2 is dropped, not 1. FIFO would have dropped 1 at the same point.
The cost of the code comes from the remove call. LinkedList.remove(Object) scans the list from the head and looks at no more than k items. Each request therefore takes O(k), and a sequence of n requests takes O(n · k) time. Memory is O(k). This suffices for small k. For caches of thousands of pages, O(1) per request is needed.
Omitting the (Integer) cast. If you write cache.remove(page), Java picks the remove(int index) overload because page is an int. The call deletes the item at position page, not the item whose value is page. When page 1 is requested, the second item of the list is deleted. When page 7 is requested, IndexOutOfBoundsException is thrown. The cast (Integer) page makes Java call the remove(Object) overload.
8.4.8An O(1) LRU cache
For O(1) per request, two structures are used together. A hash table finds in O(1) whether a page is in the cache and where it sits in the list. A doubly linked list keeps the pages in usage order. Because the node's position is known, removing it from the list and moving it to the end is O(1). Java's LinkedHashMap class is exactly this combination.
class LruCache<K, V>
extends LinkedHashMap<K, V> {
private final int cap;
LruCache(int cap) {
super(16, 0.75f, true); // access order
this.cap = cap;
}
@Override
protected boolean removeEldestEntry(
Map.Entry<K, V> eldest) {
return size() > cap; // drop when over cap
}
}The third parameter of the constructor call super(16, 0.75f, true) is accessOrder. When true is passed, every get and put moves the accessed item to the end of the list. The head of the list is therefore always the least recently used item. The first two parameters are the initial capacity and the load factor; their default values are given here. The method removeEldestEntry is called after every insertion. If it returns true, the class deletes the item at the head of the list on its own. Here it returns true when the size exceeds cap. Find, move, and delete are all O(1); memory is O(cap).
Question. On a new LruCache<Integer, String>(3) object, put(1), put(2), put(3), get(1), put(4), and put(2) are applied in order (the values are unimportant). What does keySet() print after each step?
Solution. After the three insertions the order is [1, 2, 3]. get(1) moves 1 to the end: [2, 3, 1]. After put(4) the size is 4, removeEldestEntry returns true, and the head, 2, is deleted: [3, 1, 4]. After put(2) the head, 3, is deleted: [1, 4, 2]. This is the same sequence as 1 2 3 1 4 2 in the earlier trace, and the final state agrees with Table 8.12. The code was run to verify this.
If the same class is constructed with accessOrder set to false, it becomes a FIFO cache. The list then keeps insertion order, and an access does not change the order. A single parameter separates the two policies: does a hit update the order or not?
8.4.9Java code for FIFO and Belady's sequence
The Java code for FIFO is written with a queue and a set. The queue keeps the loading order. The set answers "is this page in the cache?" in O(1).
int fifoFaults(int[] requests, int k) {
Queue<Integer> queue = new LinkedList<>();
Set<Integer> inCache = new HashSet<>();
int faults = 0;
for (int p : requests) {
if (inCache.contains(p)) continue; // hit
faults++;
if (inCache.size() == k)
inCache.remove(queue.poll()); // oldest
queue.offer(p); inCache.add(p);
}
return faults;
}For each page the loop first checks the set. If the page is in the set, it is a hit, and continue moves to the next request. In FIFO a hit changes nothing. On a fault the counter increases. If the cache is full, queue.poll() takes the oldest page at the head of the queue and inCache.remove deletes it from the set too. Finally the new page is added both to the end of the queue and to the set. Each request is O(1); memory is O(k).
This time the code is traced with the sequence 1 2 3 4 1 2 5 1 2 3 4 5 and k = 3 (Table 8.13). This sequence is the classic example of Belady's anomaly.
p | Result | Evicted | queue | faults |
|---|---|---|---|---|
| 1 | F (compulsory) | — | [1] | 1 |
| 2 | F (compulsory) | — | [1, 2] | 2 |
| 3 | F (compulsory) | — | [1, 2, 3] | 3 |
| 4 | F | 1 | [2, 3, 4] | 4 |
| 1 | F | 2 | [3, 4, 1] | 5 |
| 2 | F | 3 | [4, 1, 2] | 6 |
| 5 | F | 4 | [1, 2, 5] | 7 |
| 1 | ✓ | — | [1, 2, 5] | 7 |
| 2 | ✓ | — | [1, 2, 5] | 7 |
| 3 | F | 1 | [2, 5, 3] | 8 |
| 4 | F | 2 | [5, 3, 4] | 9 |
| 5 | ✓ | — | [5, 3, 4] | 9 |
The method returns 9 (Figure 8.10). Run with k = 4, the same code returns 10. The cache grew, and the number of faults went up.
8.4.10Belady's anomaly
Enlarging the cache should reduce the number of faults. This expectation looks so natural that it went unquestioned until the late 1960s. In 1969 Belady and his colleagues showed that FIFO can violate it. Figure 8.11 processes the same sequence with FIFO, first with 3 and then with 4 slots.
Belady's anomaly: for a page eviction policy, the number of page faults on the same request sequence increases even though the number of slots increases.
The cause of the anomaly is visible in the 4-slot run. With 4 slots the first four requests fill the cache, and 1 and 2 get hits. When 5 arrives, FIFO evicts 1 from the head of the queue. But 1 is requested right afterwards. Loading 1 evicts 2, loading 2 evicts 3, and the chain continues. Every page is evicted just before it is requested. In the 3-slot run the loading order is different. When 5 is loaded, 1 and 2 remain in the cache, and the next two requests are hits.
This anomaly never occurs in LRU or OPT. On the same sequence LRU makes 10 faults with 3 slots and 8 with 4 slots. OPT makes 7 and 6. What the two policies have in common is that both are stack algorithms. In a stack algorithm, at every moment the pages in a cache of k slots are a subset of the pages in a cache of k + 1 slots. For LRU the reason is clear. LRU with k slots keeps the k most recently used distinct pages, and LRU with k + 1 slots keeps the k + 1 most recently used distinct pages. The first set lies inside the second. Every request that hits in the small cache also hits in the large one. So the fault count cannot increase when the number of slots grows.
FIFO is not a stack algorithm. After the 7th request, the cache is {5, 2, 3, 4} in the 4-slot run and {5, 1, 2} in the 3-slot run. Page 1 is in the small cache but not in the large one. The 8th request is for 1; the small cache gets a hit and the large cache faults.
Question. On the sequence 1 2 3 4 1 2 5 1 2 3 4 5, what are the fault counts of FIFO, LRU, and OPT for k = 1, …, 5? At which value of k does the anomaly occur?
Solution. All three policies were run in Java. For k = 1 all three make 12 faults: no page is requested twice in a row. For k = 2, FIFO and LRU make 12 faults and OPT makes 9. For k = 3, FIFO makes 9, LRU 10, and OPT 7. For k = 4, FIFO makes 10, LRU 8, and OPT 6. For k = 5 all five distinct pages fit, and only 5 compulsory faults remain. The fault counts of LRU and OPT never increase as k grows. FIFO's rises from 9 to 10 in going from 3 to 4. There is also an interesting detail: at k = 3, FIFO is better than LRU. A single result on one sequence does not determine the general ranking among policies.
8.4.11Deterministic lower bound: k
On the example sequence, LRU was only 1.29 times worse than OPT. Does this ratio hold on every sequence? No. The adversary can construct a sequence that makes any deterministic policy k times worse.
No deterministic paging algorithm working with a cache of k pages has a competitive ratio smaller than k.
The adversary uses only k + 1 distinct pages. Because the cache holds k pages, at least one of these pages is outside the cache at every moment. Since the adversary knows the algorithm's code, it can compute at every step which page is outside. At each step it requests exactly that page. The algorithm therefore faults on every request: n faults in n requests.
Let OPT process the same sequence. When OPT faults, it evicts the page whose next use is farthest away. Each of the other k − 1 pages remaining in the cache will be requested before the evicted page. The evicted page is the only page outside the cache. So all requests up to the next request of the evicted page are hits. During this time all of the other k − 1 pages are requested. That is, there are at least k − 1 hits between two faults of OPT. OPT faults at most once in every k requests; the total number of faults is at most about n / k.
The ratio is ALG / OPT ≥ n / (n/k) = k. As n grows, the additive constant becomes negligible; ALG ≤ c · OPT + α cannot hold with a smaller c. □
Figure 8.12 gives a concrete example of this proof for k = 3 and LRU. The sequence 1 2 3 4 1 2 3 4 1 2 3 4, built from 4 pages, requests exactly the page LRU has just evicted every time.
LRU makes 12 faults in 12 requests, while OPT makes 6. If the first three compulsory faults are set aside, the ratio is 9 to 3, exactly k = 3. OPT behaves as in the proof. At the 4th request the cache is {1, 2, 3}, and 3, which will be requested farthest in the future, is evicted. Then 1 and 2 get hits. When 3 arrives at the 7th request, among 1, 2, and 4 in the cache, 2, which will be requested farthest in the future, is evicted. Two hits follow every fault.
FIFO also makes 12 faults on the same sequence. On this sequence FIFO and LRU behave identically, because there are no hits at all. As the sequence grows, the ratio approaches k. For example, with 5 pages and k = 4, if the sequence 1 2 3 4 5 is repeated three times, LRU makes 15 faults and OPT makes 7.
8.4.12Upper bound: LRU is k-competitive
The lower bound says that no deterministic algorithm can do better than k. LRU and FIFO reach this bound. The proof divides the request sequence into phases.
The request sequence is divided from left to right into phases. Each phase is the longest segment containing at most k distinct pages. The first new page requested after k distinct pages have been requested in a phase, that is, the (k + 1)-th distinct page, starts a new phase.
For every request sequence σ, LRU(σ) ≤ k · OPT(σ) + k. The same inequality holds for FIFO.
Divide the sequence into m phases. The proof has two steps.
LRU makes at most k faults in a phase. Let p be a page requested in the phase. At the moment p is requested, it is the most recently used page. Until the phase ends, at most k distinct pages are requested. So at most k − 1 pages can have been used more recently than p. When the cache is full and p is in it, there is always at least one page used less recently than p. LRU therefore does not evict p before the phase ends. In a phase each distinct page faults at most once. Because a phase has at most k distinct pages, there are at most k faults.
OPT makes at least 1 fault per two consecutive phases. Consider the segment from the second request of phase i to the first request of phase (i + 1). Let q be the first request of phase i. At the start of the segment q is in the cache, because it has just been requested. In the segment at least k pages different from q are requested: the remaining k − 1 pages of phase i and the page that starts the new phase. Apart from q, the cache has room for only k − 1 pages. At least one of these k pages faults within the segment. Since the segments are disjoint, over m phases OPT makes at least m − 1 faults.
Combining the two steps gives LRU ≤ k · m and OPT ≥ m − 1. From these, LRU ≤ k · (OPT + 1) = k · OPT + k. For FIFO the first step is shown as follows. A page that faults in the phase enters at the tail of the queue. For it to reach the head and be evicted, k more new pages must be loaded behind it. Because a phase has at most k distinct pages, this cannot happen before the phase ends. The second step concerns OPT and holds unchanged. □
The proof can also be checked on the example sequence. The sequence in Figure 8.13 has 4 phases. LRU's 9 faults do not exceed k · m = 3 · 4 = 12. OPT's fault count must be at least m − 1 = 3; 7 faults satisfy this bound. As we see, the theory bounds only the worst case. On real sequences, thanks to locality, LRU is much closer to OPT than this bound suggests.
8.4.13Randomized paging: marking
The key to the deterministic lower-bound proof is that the adversary knows the algorithm's cache. If the algorithm chooses the page to evict at random, an oblivious adversary cannot know which page is outside. This idea leads to the marking algorithm.
The marking algorithm keeps a mark bit for each page in the cache and works as follows:
- At the start of a phase, the marks of all pages are cleared.
- The requested page is marked, whether the request is a hit or a fault.
- On a fault with a full cache, one of the unmarked pages is chosen at random and evicted.
- If at the moment of a fault all pages in the cache are marked, a new phase begins and we return to step 1.
A marked page is a page that has been requested in this phase. The algorithm protects the pages requested in this phase and chooses only among the unmarked ones. The notion of phase is the same as in the LRU proof. Figure 8.14 shows the phases of the example sequence and the sets of pages requested in each phase.
Fiat, Karp, Luby, McGeoch, Sleator, and Young (1991) showed that the randomized marking algorithm is 2Hk-competitive against an oblivious adversary. Here Hk is the k-th harmonic number:
Hk = 1 + 1/2 + 1/3 + … + 1/k ≈ ln k
The same work also shows that no randomized algorithm can do better than Hk. Table 8.14 compares the deterministic and randomized ratios. The gap widens as k grows: the deterministic ratio grows linearly, the randomized ratio logarithmically.
| k | Deterministic (LRU, FIFO) | Hk (randomized lower bound) | 2Hk (marking) |
|---|---|---|---|
| 2 | 2 | 1.5 | 3 |
| 3 | 3 | 1.83 | 3.67 |
| 8 | 8 | 2.72 | 5.44 |
| 16 | 16 | 3.38 | 6.76 |
| 100 | 100 | 5.19 | 10.37 |
For small k, 2Hk can be larger than the deterministic ratio. At k = 2, 2H2 = 3 while the deterministic ratio is 2. But at k = 8, marking, at 5.44, beats the deterministic ratio. Because real caches hold thousands of pages, the gap is large. LRU is also a marking algorithm: the least recently used page that LRU evicts is always an unmarked page. LRU picks the oldest among the unmarked pages rather than a random one. Randomness defeats the adversary's strategy of "request the page that is not in the algorithm's cache"; the adversary cannot know which page was evicted.
8.4.14Code trace of the marking algorithm
The Java code of the marking algorithm uses two sets: cache holds the pages in the cache and marked holds the marked pages. rnd is a Random object.
int marking(int[] requests, int k) {
Set<Integer> cache = new HashSet<>();
Set<Integer> marked = new HashSet<>();
int faults = 0;
for (int p : requests) {
if (!cache.contains(p)) {
faults++;
if (cache.size() == k) {
if (marked.size() == k) marked.clear(); // new phase
List<Integer> cand = new ArrayList<>(cache);
cand.removeAll(marked); // unmarked
int i = rnd.nextInt(cand.size());
cache.remove(cand.get(i));
}
cache.add(p);
}
marked.add(p);
}
return faults;
}If the page is not in the cache, the fault counter increases. If the cache is full, the phase is checked first: if the number of marked pages equals k, every page in the cache is marked. A new phase starts and marked.clear() erases all marks. Then the list cand is built: the marked pages are removed from the pages in the cache. rnd.nextInt(cand.size()) picks a random index from this list, and that page is evicted from the cache. The new page is added to the cache. The last line, marked.add(p), marks the requested page whether it was a hit or a fault.
Because the algorithm is random, a trace can be given only for particular draws. Table 8.15 gives one run on the example sequence step by step. The code was run with a fixed random number generator that returned the draws shown in this table, and it returned 9.
p | Result | New phase? | Candidates | Evicted | Cache | faults |
|---|---|---|---|---|---|---|
| 7 | F | — | — | — | 7• | 1 |
| 0 | F | — | — | — | 0• 7• | 2 |
| 1 | F | — | — | — | 0• 1• 7• | 3 |
| 2 | F | yes | [0, 1, 7] | 7 | 0 1 2• | 4 |
| 0 | ✓ | — | — | — | 0• 1 2• | 4 |
| 3 | F | no | [1] | 1 | 0• 2• 3• | 5 |
| 0 | ✓ | — | — | — | 0• 2• 3• | 5 |
| 4 | F | yes | [0, 2, 3] | 3 | 0 2 4• | 6 |
| 2 | ✓ | — | — | — | 0 2• 4• | 6 |
| 3 | F | no | [0] | 0 | 2• 3• 4• | 7 |
| 0 | F | yes | [2, 3, 4] | 2 | 0• 3 4 | 8 |
| 3 | ✓ | — | — | — | 0• 3• 4 | 8 |
| 2 | F | no | [4] | 4 | 0• 2• 3• | 9 |
In some rows of the table the choice is forced. If the candidate list has a single item, randomness changes nothing: as in rows 6, 10, and 13. Real choices are made only at the first fault of a new phase. With these draws the algorithm made 9 faults (Figure 8.15). On the same sequence LRU had made 9, FIFO 10, and OPT 7. With other draws the result changes. The code was run with 200,000 different seeds. The fault count varied between 7 and 12; the average came out at about 9.0.
Setting marks only on a fault. If the line marked.add(p) is moved inside the if block, pages that get hits are not marked. A page just used in this phase stays unmarked and can be evicted by the random choice. The algorithm loses its property of protecting recently used pages. In the trace above, after the hit at row 5, 0 would remain unmarked. At row 6 the candidate list would be [0, 1] and 0 could be evicted; 0 is requested again right after.
8.5List update
In paging the cost was binary: hit or fault. In the list update problem, the cost depends on the item's position in the list. The problem rests on an old but still used idea: if frequently requested items are kept near the front of the list, searches become cheaper. Since it is not known in advance which items will be requested often, the problem is online.
8.5.1The problem and three rules
Let a linked list of n items be given. To access an item, the list is scanned from the front. Accessing the item at position i costs i. After the access, the accessed item may be moved toward the front of the list for free. Exchanging two adjacent items in any other way costs 1 unit; such swaps are called paid exchanges.
The list update problem: given a list of n items and a sequence of access requests. Accessing the item at position i costs i units. The accessed item may be moved to the front for free; other swaps cost one unit each. After each access the algorithm decides how to rearrange the list without knowing the future. The goal is to minimize the total cost.
There are three natural rules.
- Move-to-front (MTF): the accessed item is brought to the front of the list.
- Transpose: the accessed item is swapped with the item in front of it.
- Frequency count: an access count is kept for each item, and the list is kept in decreasing order of these counts.
Lists that follow these rules are called self-organizing lists. Their uses are wide. In a chained hash table the chain of each bucket is a short linked list, and move-to-front brings frequently searched keys to the head of the chain. Data compression uses the move-to-front transform: each symbol is encoded by its position in the current list and then moved to the front. The bzip2 compressor uses this transform. Consecutive repeats turn into small numbers, mostly 0, which compress well in the next stage. For example, the word "banana" with the alphabet a, b, n is encoded as 1, 1, 2, 1, 1, 1.
The Java code of the move-to-front rule is short with a linked list:
int mtfCost(LinkedList<Character> list, char[] requests) {
int total = 0;
for (char x : requests) {
int pos = list.indexOf(x) + 1; // 1-based
total += pos;
list.remove((Character) x);
list.addFirst(x); // move to front
}
return total;
}indexOf finds the item's 0-based position; adding 1 gives the cost. remove((Character) x) removes the item from the list and addFirst puts it at the front. The (Character) cast here too makes Java call the remove(Object) overload instead of remove(int index). Because indexOf and remove scan the list, each request takes O(n). This time is consistent with the problem's own cost model: an access already costs as much as the position.
8.5.2Move-to-front step by step
Let the initial list be A B C D E and the requests E D E A D E. Table 8.16 gives every step of move-to-front.
| Request | Position (cost) | Total | List after |
|---|---|---|---|
| E | 5 | 5 | E A B C D |
| D | 5 | 10 | D E A B C |
| E | 2 | 12 | E D A B C |
| A | 3 | 15 | A E D B C |
| D | 3 | 18 | D A E B C |
| E | 3 | 21 | E D A B C |
On the same sequence the other rules pay more (Table 8.17). The list that never moves anything pays 5 for every E and 4 for every D. Transpose does very badly on this sequence. E and D keep trading places at the end of the list: when E moves forward D drops back, and when D moves forward E drops back. Both are always requested from position 5.
| Strategy | E | D | E | A | D | E | Total |
|---|---|---|---|---|---|---|---|
| Move-to-front | 5 | 5 | 2 | 3 | 3 | 3 | 21 |
| No moves | 5 | 4 | 5 | 1 | 4 | 5 | 24 |
| Transpose | 5 | 5 | 5 | 1 | 5 | 5 | 26 |
An algorithm that knows the future pays even less. By trying all lists and paid exchanges, the best cost on this small example was computed: 17. This cost is reached as follows: at the start the list is turned into E D A B C with 7 paid exchanges. Then the accesses cost 1 + 2 + 1 + 3 + 2 + 1 = 10.
Question. On the list A B C D, what is the total cost of the requests D C D A under move-to-front?
Solution. D is at position 4: cost 4, list D A B C. C is at position 4: cost 4, list C D A B. D is at position 2: cost 2, list D C A B. A is at position 3: cost 3, list A D C B. The total is 4 + 4 + 2 + 3 = 13. The list that never moves would have paid 4 + 3 + 4 + 1 = 12. Move-to-front is not better than not moving on every sequence; on this one it is slightly worse.
8.5.3Move-to-front is 2-competitive
Sleator and Tarjan showed in 1985 that the competitive ratio of move-to-front is 2. The same paper contains the result k for paging. Together they are regarded as the starting point of competitive analysis.
For every algorithm A starting from the same list and every sequence σ of m requests, MTF(σ) ≤ 2 · A(σ) − m. A's cost includes its paid exchanges. In particular, MTF(σ) ≤ 2 · OPT(σ) − m.
The proof rests on amortized analysis. The actual cost of an operation may fluctuate. Expensive operations are paid for by the "credit" that cheap operations accumulated. Credit is measured by a potential function Φ. The amortized cost of an operation is its actual cost plus the change in potential: actual + ΔΦ. If the potential is never negative and starts at 0, the sum of amortized costs cannot be smaller than the sum of actual costs.
The potential is the number of inversions between the MTF list and A's list. An inversion is a pair of items that appear in different orders in the two lists. At the start the two lists are identical and Φ = 0.
Let the requested item be x. Split the items that precede x in the MTF list into two groups. Let a be the number of those that also precede x in A's list, and b the number of those that come after x in A's list. MTF's actual cost is a + b + 1. If x's position in A is i, then i ≥ a + 1.
MTF moves x to the front. The inversions between the b items and x disappear. New inversions arise between the a items and x. Hence ΔΦ ≤ a − b. The amortized cost is (a + b + 1) + (a − b) = 2a + 1 ≤ 2i − 1.
A's own moves also change the potential. If A moves x to the front for free, x is already at the front of the MTF list; each such step destroys one inversion. A paid exchange raises the potential by at most 1 and costs A 1 unit. Summing over all requests, MTF(σ) ≤ Σ(2i − 1) + P = 2C − m + P. Here C is A's access cost and P is the number of paid exchanges. Since 2C + P ≤ 2(C + P) = 2 · A(σ), the result follows. □
The inequality in the proof can be followed step by step on the example sequence. Table 8.18 takes as A the list A B C D E that never moves anything. At every step the amortized cost does not exceed 2i − 1. In total, 21 ≤ 2 · 24 − 6 = 42. The bound also holds against the true OPT: 21 ≤ 2 · 17 − 6 = 28.
| Request | MTF cost | i in the fixed list | Φ before → after | Amortized | 2i − 1 |
|---|---|---|---|---|---|
| E | 5 | 5 | 0 → 4 | 9 | 9 |
| D | 5 | 4 | 4 → 6 | 7 | 7 |
| E | 2 | 5 | 6 → 7 | 3 | 9 |
| A | 3 | 1 | 7 → 5 | 1 | 1 |
| D | 3 | 4 | 5 → 5 | 3 | 7 |
| E | 3 | 5 | 5 → 7 | 5 | 9 |
Row 4 shows the power of the proof. Accessing A costs MTF 3 units but the fixed list only 1. By actual cost, MTF is 3 times worse at this step. But moving A to the front destroys two inversions and the potential drops by 2. The amortized cost falls to 1. The credit accumulated in earlier steps pays for this expensive step.
8.5.4Why are transpose and frequency count not competitive?
The transpose rule looks cautious because it moves an item only one step. But the adversary exploits this caution. It requests the last two items of the list in alternation: xn, xn−1, xn, xn−1, … Each access swaps the two items, but both stay in positions n and (n − 1). The requested item is at position n every time. The cost per request is n. MTF, in contrast, keeps the two items at the front of the list after the first two accesses and pays 2 per request. This sequence was run with n = 5 and 20 requests: transpose paid 100, MTF 46, and the list that never moves 90. As n grows the ratio goes to n/2; it is unbounded.
Frequency count is also trapped. First item x1 is requested n times, item x2 n − 1 times, and so on. Then the same items are requested in reverse order, in larger numbers. The counters keep the old order for a long time. The new frequent items stay at the end of the list until the counters catch up. On the list A B C D, A was requested four times, B three, C two, and D once, followed by D five, C six, B seven, and A nine times. Frequency count paid 81 and MTF paid 49. On long lists the cost can be worse by a factor of Θ(n).
Reading "2-competitive" as "it pays less than twice on every sequence, so it is always good". The theorem compares MTF with the algorithm that knows the future. On some sequences MTF is worse even than the list that never moves anything. For example, on the list A B C D with the requests C A C D B A, MTF pays 19 and the non-moving list pays 14. The guarantee is only this: on no sequence does it exceed twice the best algorithm.
8.6Data streams
In the earlier problems the online algorithm's trouble was making wrong decisions. In data streams the trouble is different: the input is so large that it cannot be stored. The algorithm looks at each item once and keeps a small summary. A question can be asked at any moment, and the answer must be given from the summary alone.
8.6.1The data stream model
In the data stream model, items x1, x2, … arrive one at a time. The stream may be very long or infinite. Each item is looked at once (single pass), and the past cannot be stored in full. At every moment the answer to a question such as "what is the average, median, or sample so far?" must be ready.
Table 8.19 gives the problems treated in this section, the summary stored for each, and the costs.
| Problem | Stored summary | Per item | Memory |
|---|---|---|---|
| Moving average (last k) | Queue and sum | O(1) | O(k) |
| Online median | Max-heap and min-heap | O(log n) | O(n) |
| Reservoir sampling | Sample of k items | O(1) | O(k) |
| Pattern search in a stream | Last m characters and a rolling hash | O(1) | O(m) |
| Running mean | n and μ | O(1) | O(1) |
The online median is the exception in the table: its memory grows with the stream. For an exact median this is unavoidable. Every item in the stream is a candidate for becoming the median later. For very large streams, summaries that give an approximate median are therefore used.
8.6.2Moving average
The moving average is the average of the last k items in the stream. It is used to smooth noisy sensor data. The 50-day average in the stock market is also a moving average. The naive method re-sums the last k items at every new item: O(k). The better method is the sliding window. The sum is kept in a variable. When a new item enters, it is added to the sum, and when the oldest item leaves the window, it is subtracted:
sum ← sum − xt−k + xt, average = sum / min(t, k)
class MovingAverage {
private final int k;
private final Queue<Integer> window
= new LinkedList<>();
private int sum = 0;
MovingAverage(int k) { this.k = k; }
double next(int value) {
if (window.size() == k)
sum -= window.poll();
window.offer(value);
sum += value;
return sum / (double) window.size();
}
}The window is a queue. The next method first checks whether the window is full. If it is, poll takes the oldest item from the queue and subtracts it from the sum. Then the new item is added to the queue and to the sum. The average is the sum divided by the window size. If the window is not yet full, the divisor is the current number of items rather than k. The (double) cast prevents integer division. Each call is O(1); memory is O(k). Table 8.20 traces the stream 4, 8, 6, 2, 10 with k = 3.
value | Evicted | window | sum | Returned average |
|---|---|---|---|---|
| 4 | — | [4] | 4 | 4 / 1 = 4 |
| 8 | — | [4, 8] | 12 | 12 / 2 = 6 |
| 6 | — | [4, 8, 6] | 18 | 18 / 3 = 6 |
| 2 | 4 | [8, 6, 2] | 18 − 4 + 2 = 16 | 16 / 3 ≈ 5.33 |
| 10 | 8 | [6, 2, 10] | 16 − 8 + 10 = 18 | 18 / 3 = 6 |
Mixing up the order of removing and adding. If we add first and then check window.size() > k, the code still works correctly. But if we add first and then check size() == k, the window is shrunk before it ever reaches k. Then only the average of the last k − 1 items is taken. Another mistake is keeping sum as a double. On long streams, adding and subtracting accumulates rounding error; for integer data the sum should be kept as an integer.
8.6.3Online median
After every new item, the median of the items so far is requested. Sorting each time takes O(n log n), and inserting into a sorted array takes O(n). With two heaps, insertion drops to O(log n) and reading the median to O(1). This method is called the running median.
The idea is as follows. The items are split into two halves. The smaller half is kept in a max-heap, called left. The larger half is kept in a min-heap, called right. The median lies at the boundary of the two halves. The items at this boundary are exactly the heap tops. Two invariants are maintained:
- Every item in
leftis less than or equal to every item inright. - The sizes are either equal or
lefthas one more: |left| = |right| or |left| = |right| + 1.
left (max-heap) holds 5, 3, 1; right (min-heap) holds 8, 15. Because the item count is odd, the median is the top of left: 5.If the item count is odd, the median is the top of left. If it is even, it is the average of the two tops. In Java, PriorityQueue is a min-heap by default; a max-heap is built with a reversed comparator:
PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> b - a); // max-heap
PriorityQueue<Integer> right = new PriorityQueue<>(); // min-heapvoid add(int x) {
if (left.isEmpty() || x <= left.peek())
left.offer(x); // smaller half
else
right.offer(x); // larger half
if (left.size() > right.size() + 1)
right.offer(left.poll());
else if (right.size() > left.size())
left.offer(right.poll());
}
double median() {
if (left.size() == right.size())
return (left.peek() + right.peek()) / 2.0;
return left.peek();
}add works in two stages. First the item is put in the correct half: if left is empty or the item is not greater than the top of left, it goes to the smaller half; otherwise to the larger half. This step preserves the first invariant. Then the balance is restored. If left has become two larger, its top is moved to right. If right has become larger, its top is moved to left. The moved item is always an item at the boundary of one half, so the move does not break the first invariant. Each insertion does at most three heap operations: O(log n). median looks only at the tops: O(1). Table 8.21 traces the stream 5, 15, 1, 3, 8, 7.
x | Half entered | Rebalance | left | right | Median |
|---|---|---|---|---|---|
| 5 | left (empty) | ok | 5 | — | 5 |
| 15 | right (15 > 5) | ok | 5 | 15 | (5 + 15)/2 = 10 |
| 1 | left (1 ≤ 5) | ok | 5, 1 | 15 | 5 |
| 3 | left (3 ≤ 5) | 3 > 1 + 1: 5 → right | 3, 1 | 5, 15 | (3 + 5)/2 = 4 |
| 8 | right (8 > 3) | 3 > 2: 5 → left | 5, 3, 1 | 8, 15 | 5 |
| 7 | right (7 > 5) | ok | 5, 3, 1 | 7, 8, 15 | (5 + 7)/2 = 6 |
left 5, 3, 1; right 7, 8, 15; median 6.The fourth and fifth steps show why the rebalancing is needed. After 3 is added, left holds 3 items and right holds 1. The median is no longer the top of left. Moving 5 to right evens the halves out again. At the fifth step right becomes the larger one this time, and 5 moves back. The same item has been moved twice; this is normal. When the code was run, the medians came out as 5.0, 10.0, 5.0, 4.0, 5.0, and 6.0 in order.
Question. What are the online medians for the stream 2, 9, 4, 7?
Solution. 2 goes into left: median 2. Because 9 > 2, it goes into right: median (2 + 9)/2 = 5.5. Because 4 > 2, it goes into right. Now right is larger, and its top, 4, is moved to left. left holds 4, 2; right holds 9; median 4. Because 7 > 4, it goes into right. The sizes are 2 and 2; median (4 + 7)/2 = 5.5. The medians are 2, 5.5, 4, 5.5. This can be checked with sorted lists: [2, 9], [2, 4, 9], and [2, 4, 7, 9].
Forgetting the rebalancing. Putting the item in the correct half is not enough by itself. If the stream is 5, 1, 3, all three items go into left. Without the rebalancing, median() returns the top of left, which is 5; the correct answer is 3. When the size difference exceeds 1, the top must be moved to the other heap. A second mistake is to build the max-heap with (a, b) -> b - a. With very large and very small numbers this subtraction overflows. The safe choice is Comparator.reverseOrder().
8.6.4Reservoir sampling
We want to keep a random sample of k items from a stream of unknown length. Every item must be in the sample with equal probability. If the stream length n were known, the job would be easy: pick k indices from 1, …, n. But n is unknown, and the items cannot be stored. Reservoir sampling solves this problem with O(k) memory.
Algorithm R (Vitter, 1985): the first k items are put into the reservoir. Then, for each 0-based item i ≥ k, a uniformly random j in the range 0 … i is chosen. If j < k, xi overwrites the j-th item of the reservoir; otherwise xi is skipped.
According to the algorithm, item i enters the reservoir with probability k / (i + 1). If it enters, it evicts the item at a random position. Late-arriving items have a small probability of entering. But early items also face a risk of being evicted that lasts a long time. The two effects balance exactly.
When a stream of n ≥ k items ends, each item is in the reservoir with probability k / n.
Consider an item xi with i ≥ k. It enters with probability k/(i + 1). At each later step t > i, item xt enters with probability k/(t + 1) and, if it enters, picks one of the k positions with equal probability. The probability that xi is evicted at this step is (k/(t + 1)) · (1/k) = 1/(t + 1). The probability that it stays is t/(t + 1). Because the steps are independent, the probabilities multiply:
k/(i + 1) · (i + 1)/(i + 2) · (i + 2)/(i + 3) · … · (n − 1)/n = k / n
In the product each numerator cancels the previous denominator, leaving k/n. For the first k items, with i < k, the probability of entering is 1. The product of staying is k/(k + 1) · … · (n − 1)/n = k/n. The result is the same for every item. □
List<Integer> reservoir(int[] stream, int k) {
List<Integer> r = new ArrayList<>();
for (int i = 0; i < Math.min(k, stream.length); i++)
r.add(stream[i]);
for (int i = k; i < stream.length; i++) {
int j = rnd.nextInt(i + 1); // 0..i
if (j < k)
r.set(j, stream[i]);
}
return r;
}The code works with a list. The first loop puts the first k items into the reservoir; if the stream is shorter than k, it puts in all items and the list is returned as is, because the second loop never runs. The second loop calls rnd.nextInt(i + 1) for each remaining item. This call returns a uniform integer in the range 0 … i, endpoints included. If j < k, r.set overwrites the item at that position. It uses O(1) work per item and O(k) memory in total. On a real stream one works with an iterator instead of an array; the algorithm does not change.
Table 8.22 traces the code with the stream 10, 20, 30, 40, 50, 60 and k = 3. The random numbers are fixed for this trace: 1, 4, and 0.
i | Value | j | Action | r | Entry probability |
|---|---|---|---|---|---|
| 0–2 | 10, 20, 30 | — | added directly | [10, 20, 30] | 1 |
| 3 | 40 | 1 | r[1] = 40 (20 is evicted) | [10, 40, 30] | 3/4 |
| 4 | 50 | 4 | 4 ≥ 3: does not enter | [10, 40, 30] | 3/5 |
| 5 | 60 | 0 | r[0] = 60 (10 is evicted) | [60, 40, 30] | 3/6 |
Other values of j give another sample. But according to the theorem every item is in the sample with probability 3/6 = 1/2. This claim was also checked by simulation. With the stream 1, …, 10 and k = 3, the code was run 300,000 times. The frequency of each item appearing in the sample came out between 0.299 and 0.301; the expected value is 3/10 = 0.3.
Question. Let k = 2. With what probability does the 0-based item 9 of the stream enter the reservoir? If the stream ends with 10 items, with what probability is this item in the reservoir at the end?
Solution. The probability of entering is k/(i + 1) = 2/10 = 1/5. Because the stream ends with 10 items, item 9 is the last one and there is no risk of eviction after it. The probability of being in the reservoir at the end is also 1/5. This equals k/n = 2/10 in the theorem.
Choosing the wrong range. If you write nextInt(i), j comes from the range 0 … i − 1 and the item enters with probability k/i. The sample is not uniform. In particular at i = k the probability rises to 1: the k-th item always enters. The faulty code was run 300,000 times with the stream 1, …, 10 and k = 3. The frequency of the first three items dropped to 0.22, while that of the other seven rose to 0.33.
8.6.5Pattern search in a stream: the rolling hash
Suppose a network monitoring program is looking for a certain signature in the packets passing by. The characters arrive as a stream. If the pattern has length m, looking at only the last m characters is enough. Comparing this window with the pattern at every new character takes O(m). The rolling hash reduces the comparison to O(1) most of the time.
The window's hash value treats its characters like the digits of a number in base B. When a new character enters, the value is not computed from scratch. The outgoing character's contribution is subtracted, the remaining value is shifted by one digit, and the incoming character is added:
hnew = (hold − cout · Bm−1) · B + cin
void search(String stream, String pattern) {
int m = pattern.length(), B = 101, h = 0, hp = 0;
int pow = 1; // B^(m-1)
for (int i = 0; i < m - 1; i++) pow *= B;
for (int i = 0; i < m; i++)
hp = hp * B + pattern.charAt(i);
for (int t = 0; t < stream.length(); t++) {
char c = stream.charAt(t);
if (t >= m) h -= stream.charAt(t - m) * pow;
h = h * B + c; // add incoming
if (t >= m - 1 && h == hp
&& stream.startsWith(pattern, t - m + 1))
System.out.println("match: " + (t - m + 1));
}
}The code first computes Bm−1 into the variable pow and the pattern's hash value into hp. The main loop runs for each character. If t >= m, a character leaves the window and its contribution is subtracted as stream.charAt(t - m) * pow. Then h is shifted by one digit and the incoming character is added. Once the window is full, if h == hp, the characters are also compared with startsWith. Two different strings can give the same hash value; this is called a collision. For this reason hash equality alone is not enough. If the hashes differ, the characters are never looked at. If collisions are rare, the work per item is O(1); memory is O(m) for the window.
Table 8.23 searches for the pattern "AB" in the stream "CABDAB". B = 101, m = 2, and pow = 101. The character codes are A = 65, B = 66, C = 67, D = 68. The pattern's hash value is 65 · 101 + 66 = 6631.
t | Outgoing | Incoming | Window | h | Result |
|---|---|---|---|---|---|
| 0 | — | C | “C” | 67 | window not full |
| 1 | — | A | “CA” | 67 · 101 + 65 = 6832 | ≠ 6631 |
| 2 | C | B | “AB” | (6832 − 6767) · 101 + 66 = 6631 | match: 1 |
| 3 | A | D | “BD” | 6734 | ≠ 6631 |
| 4 | B | A | “DA” | 6933 | ≠ 6631 |
| 5 | D | B | “AB” | (6933 − 6868) · 101 + 66 = 6631 | match: 4 |
When the code was run, it printed "match: 1" and "match: 4". As the pattern gets longer, int overflows. This does not harm correctness. In Java, int operations are done modulo 232, and subtraction, multiplication, and addition are consistent in this modulus. Because h and hp are computed in the same modulus, equal windows give equal hashes. Overflow can only increase collisions; the character comparison filters them out. In practice one usually works modulo a large prime.
8.7Incremental learning
In machine learning the model is usually trained once on all the data. If data arrives continuously, this approach is expensive. Retraining the model from scratch at every new piece of data means reprocessing all the data that has arrived so far. The online view helps here too: the model is updated with the new data only.
8.7.1Updating a model with new data
Incremental learning is the updating of a model with each new piece of data without reprocessing the past data. The updated model represents the knowledge in both the old and the new data.
Figure 8.24 shows the process. Initially the model is trained on the original data set, giving MODEL 1. When new data 1 arrives, the model is updated with this data alone and becomes MODEL 2. MODEL 2 carries the knowledge of two data sets, but the original data has not been reprocessed. The same step is repeated with new data 2. The model is up to date at every moment, and the cost of an update is only the size of the new data.
The similarity to stream algorithms is clear. The model is a summary of the past data, just like the sum in the moving average or the two heaps in the online median. The difference is that the summary is more complex: the weights of a classifier, the branches of a decision tree, or the parameters of a neural network.
8.7.2Running mean and online gradient descent
The simplest example of an incremental update is the running mean. The mean of all items in the stream can be updated without storing the past:
μn = μn−1 + (xn − μn−1) / n
The formula corrects by 1/n of the difference between the new item and the old mean. For the stream 4, 8, 6 we get μ1 = 4, μ2 = 4 + (8 − 4)/2 = 6, μ3 = 6 + (6 − 6)/3 = 6. This equals (4 + 8 + 6)/3 = 6. Only n and μ are stored; memory is O(1). Because the formula does not keep a separate sum, it also causes no trouble with large numbers on long streams.
The same idea carries over to model training as online gradient descent. The model is defined by a weight vector w. When each example (xt, yt) arrives, the weight takes a small step in the direction opposite to the gradient of the loss:
w ← w − η · ∇ℓ(w; xt, yt)
Here ℓ is the loss function and η is the learning rate. Each example is used once and discarded.
Question. Let the model be ŷ = w · x and the loss ℓ = (w · x − y)² / 2. The derivative of this loss with respect to w is (w · x − y) · x. Initially w = 0 and the learning rate is η = 0.1. The examples (1, 2), (2, 4), (3, 6) arrive in order. What is w after each example?
Solution. On the first example the prediction is 0, the error is 0 − 2 = −2, and the gradient is −2 · 1 = −2. w = 0 − 0.1 · (−2) = 0.2. On the second example the prediction is 0.2 · 2 = 0.4, the error is −3.6, and the gradient is −3.6 · 2 = −7.2. w = 0.2 + 0.72 = 0.92. On the third example the prediction is 2.76, the error is −3.24, and the gradient is −9.72. w = 0.92 + 0.972 = 1.892. The true relationship in the data is y = 2x, and w has approached 2 in three examples. If a fourth example, (1, 2), arrived again, w would be 1.9028.
8.7.3Difficulties
Incremental learning gives a cheap and up-to-date model, but it has problems of its own.
- Catastrophic forgetting: while adapting to new data, the model loses old knowledge. A neural network learning a new task may suddenly lose its performance on the old task.
- Concept drift: the distribution of the data changes over time. Last year's shopping habits may not represent this year well. In this case old data becomes misleading.
- Order effects: if the same data arrives in a different order, the model takes a different shape. In offline training the data can be shuffled; in a stream the order comes with the data.
- Noise: a single outlier can corrupt the model. A small learning rate and a sliding window reduce this effect.
Forgetting and concept drift pull in opposite directions. When there is concept drift, some forgetting of old data is desirable. When there is none, forgetting is a loss. The window size in a moving average or the learning rate are the knobs that tune this balance.
8.8Problems and results
Table 8.24 gives the problems of the chapter and their results together. The numbers in the first five rows are competitive ratios. The rows below give the time per item.
| Problem | Online algorithm | Result | Note |
|---|---|---|---|
| Ski rental | Rent for B − 1 days, then buy | 2 − 1/B | best among deterministic; randomized e/(e − 1) |
| Paging | LRU, FIFO, FWF | k | best among deterministic |
| Paging | LFU, LIFO | unbounded | not competitive |
| Paging (randomized) | Marking | 2Hk | lower bound Hk |
| List update | Move-to-front | 2 | transpose and frequency count are not competitive |
| Moving average | Queue and sum | O(1) | memory O(k) |
| Online median | Two heaps | O(log n) | median read O(1) |
| Reservoir sampling | Algorithm R | O(1) | each item with probability k/n |
The proofs for the three competitive problems in the table follow the same skeleton. For the upper bound, the algorithm's cost is bounded by a multiple of OPT. In ski rental this is done with a case analysis, in paging with phases, and in list update with a potential function. For the lower bound, the adversary knows the deterministic algorithm's next decision and generates the request that hurts it most. In all three problems randomization lowers the ratio, because it takes this knowledge away from the adversary.
8.9Common mistakes
- Thinking "online = internet". An online algorithm is a model in which the input is revealed over time. It has nothing to do with a network connection.
- Confusing the ratio with average-case behavior. The competitive ratio refers to the worst input. "It usually works well" is not a competitive ratio.
- Confusing FIFO with LRU. In FIFO a hit does not change the order; in LRU a hit makes the page the newest. This is the only difference between the two policies.
- Forgetting compulsory faults. The first k distinct pages fault in every policy. Even OPT cannot make zero faults.
- Thinking OPT evicts the "least used page". OPT evicts the page whose next use is farthest away; it does not look at the number of uses.
- Thinking a larger cache is always better. In FIFO, faults can increase as the number of slots grows: Belady's anomaly. This does not happen in LRU and OPT.
- Wrong range in the reservoir. j must be chosen from the range 0 … i, including i. Writing
nextInt(i)breaks the probabilities. - Forgetting the balance in the median. Putting the item in the right heap is not enough. When the size difference exceeds 1, the top must be moved to the other heap.
- Counting hash equality as a match. In a rolling hash, equal values can arise from collisions. The characters must be compared separately.
8.10Summary
- Model: the input arrives piece by piece as a request sequence. The decision is made the moment the request arrives and cannot be undone. An offline algorithm, by contrast, sees the whole input from the start.
- Competitive ratio: if ALG(σ) ≤ c · OPT(σ) + α holds for every σ, the algorithm is c-competitive. The analysis measures the worst case. Lower bounds are built with the adversary model.
- Ski rental: OPT = min(d, B). The break-even strategy rents for B − 1 days and buys on day B; its ratio is 2 − 1/B. No deterministic strategy is better; a randomized strategy comes down to e/(e − 1) ≈ 1.58.
- Paging: FIFO evicts the page loaded earliest, LRU the least recently used, and OPT the one whose next use is farthest away. On the example sequence: 10, 9, and 7 faults. LRU and FIFO are k-competitive, and nothing better exists among deterministic algorithms. Randomized marking comes down to 2Hk.
- Belady's anomaly: in FIFO, faults can increase as the number of slots grows (9 → 10). LRU and OPT are stack algorithms; they show no anomaly.
- Implementation: LRU with a linked list costs O(k) per request, and with
LinkedHashMapO(1). FIFO is O(1) with a queue and a set. - List update: the cost is the position. Move-to-front satisfies MTF ≤ 2 · OPT − m; the proof takes the number of inversions as the potential. Transpose and frequency count are not competitive.
- Data streams: single pass and little memory. The moving average runs in O(1) with a sliding window, the online median in O(log n) with two heaps, and reservoir sampling in O(1) per item with O(k) memory. In the reservoir every item is present with probability k/n. The rolling hash updates the window in O(1).
- Incremental learning: the model is updated with new data. The running mean and online gradient descent are the basic examples. Forgetting and concept drift are the main difficulties.
8.11Key terms
- online algorithm
- offline algorithm
- competitive analysis
- competitive ratio
- adversary
- ski rental problem
- randomized algorithm
- paging
- cache
- page fault
- eviction policy
- Belady's anomaly
- stack algorithm
- marking algorithm
- list update problem
- move-to-front (MTF)
- transpose
- amortized analysis
- inversion
- data stream
- running median
- reservoir sampling
- rolling hash
- incremental learning
8.12Test Yourself
In ski rental, B = 8. What is the worst-case ratio of the strategy that buys on day 6? How different is it from that of the break-even strategy?
Answer
The adversary ends the season on day 6. ALG = 5 + 8 = 13, OPT = min(6, 8) = 6; ratio 13/6 ≈ 2.17. The break-even strategy's ratio is 2 − 1/8 = 15/8 = 1.875. The early-buying strategy is worse.
The sequence 1 2 1 3 1 4 1 2 is processed with k = 2 slots. How many page faults do FIFO and LRU make?
Answer
FIFO makes 6 faults: when 3 arrives, 1, the earliest loaded, is evicted and is requested again right away. When 1 arrives, 2 is evicted; when 4 arrives, 3; when the final 2 arrives, 1. LRU makes 5 faults. Because 1 is the newest on every hit, it is never evicted; when 3, 4, and the final 2 arrive, 2, 3, and 4 are evicted respectively. On this sequence OPT also makes 5 faults.
The sequence 1 2 3 1 4 2 is processed with k = 3 under the OPT policy. How many faults occur? Which pages can be evicted when 4 arrives?
Answer
There are 4 faults: three compulsory faults and the fault on 4. When 4 arrives the cache is {1, 2, 3}. 1 and 3 are never requested again, and 2 is requested in the last request. Either 1 or 3 can be evicted; both give the same result. The 2 in the last request is a hit. On the same sequence LRU had made 5 faults.
On the list A B C, what is the total cost of the requests C C B A under move-to-front? What does the list that never moves pay?
Answer
C at position 3: 3, list C A B. C at position 1: 1. B at position 3: 3, list B C A. A at position 3: 3, list A B C. Total 3 + 1 + 3 + 3 = 10. The non-moving list pays 3 + 3 + 2 + 1 = 9. On this short sequence move-to-front is slightly more expensive; being 2-competitive does not mean being best on every sequence.
3, 5, 9, 1 are given in order to
new MovingAverage(2). What values doesnextreturn?Answer
3.0; (3 + 5)/2 = 4.0; 3 leaves and (5 + 9)/2 = 7.0; 5 leaves and (9 + 1)/2 = 5.0.
10, 2, 7, 4 are added in order to the online median structure. What is the median after each insertion? When 7 is added, is there a transfer between the heaps?
Answer
The medians are 10, 6, 7, 5.5. When 2 is added it goes into
left,leftholds two items, and the top, 10, moves toright: median (2 + 10)/2 = 6. When 7 is added, because 7 > 2, it goes intoright.rightholds two items andleftone. The top ofright, 7, moves toleft; the median is 7. 4 goes intoleft;leftholds three items and its top, 7, moves toright. The sizes become 2 and 2: (4 + 7)/2 = 5.5.In reservoir sampling with k = 1, with what probability does the 0-based item 4 enter the reservoir? If the stream ends with 8 items, with what probability is this item selected at the end?
Answer
The probability of entering is 1/5. The probabilities of staying in the next three steps are 5/6, 6/7, and 7/8. The product is 1/5 · 5/6 · 6/7 · 7/8 = 1/8 = k/n.
In a cache of k = 6 pages, what are the competitive ratios of deterministic LRU and the randomized marking algorithm? Which gives the better guarantee?
Answer
LRU's ratio is 6. H6 = 1 + 1/2 + … + 1/6 = 49/20 = 2.45; the marking algorithm's ratio is 2H6 = 4.9. In this case marking is below the deterministic bound. No randomized algorithm can do better than 2.45.
In the call
search("ABA", "BA")with B = 101, what ishp? What value doeshtake att = 2, and what is printed?Answer
hp= 66 · 101 + 65 = 6731. Att = 1the window is "AB" andh= 6631. Att = 2, A leaves: (6631 − 65 · 101) · 101 + 65 = 66 · 101 + 65 = 6731. The hashes are equal and the characters match too; "match: 1" is printed.
8.13Further reading
- A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis: the standard book in the field. It treats paging, list update, adversary models, and randomized algorithms with detailed proofs.
- T. H. Cormen et al., Introduction to Algorithms, 4th edition, chapter 27: an introduction to online algorithms; it covers the elevator waiting problem (a variant of ski rental), list update, and cache problems.
- S. Albers, "Online algorithms: a survey" (2003): gives the main results of competitive analysis in a short, readable summary.
- J. S. Vitter, "Random Sampling with a Reservoir" (1985): introduces Algorithm R and the skip-ahead versions that speed it up.
8.14References
- A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998.
- D. D. Sleator and R. E. Tarjan, “Amortized Efficiency of List Update and Paging Rules”, Communications of the ACM 28(2), 1985.
- L. A. Belady, “A Study of Replacement Algorithms for a Virtual-Storage Computer”, IBM Systems Journal 5(2), 1966.
- L. A. Belady, R. A. Nelson, and G. S. Shedler, “An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine”, Communications of the ACM 12(6), 1969.
- A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, and N. E. Young, “Competitive Paging Algorithms”, Journal of Algorithms 12(4), 1991.
- A. R. Karlin, M. S. Manasse, L. A. McGeoch, and S. Owicki, “Competitive Randomized Algorithms for Nonuniform Problems”, Algorithmica 11(6), 1994.
- J. S. Vitter, “Random Sampling with a Reservoir”, ACM Transactions on Mathematical Software 11(1), 1985.
- S. Albers, “Online Algorithms: A Survey”, Mathematical Programming 97(1–2), 2003.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 4th edition, MIT Press, 2022 (chapter 27: Online Algorithms).