Comparison matrix Rule Longest Match Most Confident Pessimistic Rep/Methods Selection Selection Selection Subset rules Subsequence rules ?? subsequence rules Substring rules atest-substring Best Com pared with c4. 5 as well Comparison Criteria: Precision Model size 2021/1/26 7
2021/1/26 7 • Compared with C4.5 as well. • Comparison Criteria: Precision & Model Size Rule Rep/Methods Longest Match Selection Most Confident Selection Pessimistic Selection Subset rules ? ? ? Subsequence rules ? ? ? Latestsubsequence rules ? ? ? Substring rules ? ? ? Latest-substring rules ? ? Best! Comparison Matrix
Integrating with Caching Cache replacement algorithm a key value k(p) is assigned to each object p ■[ Arlltt et a.USENⅨ1998,Cao& irani,97] K(P)=L+ F(P*C(p)/S(p) C(p: Cost of loading a page(e.g. amount of time S(p): Size of a page F(p): Frequency Count of a page L: An Inflation factor to reflect cache aging 2021/1/26
2021/1/26 8 Integrating with Caching ◼ Cache replacement algorithm ◼ A key value K(p) is assigned to each object p ◼ [Arlltt et al. USENIX 1998, Cao & Irani, 97] ◼ K(p) = L + F(p) * C(p) / S(p) ◼ C(p): Cost of loading a page (e.g., amount of time) ◼ S(p): Size of a page ◼ F(p): Frequency Count of a page ◼ L: An Inflation factor to reflect cache aging
Predicting future frequency O1:0.70 Session 1 o2:0.90 O2:0.30 Predicted Frequency W1=0.70+0.60+0.70=2.00 O1:0.60 W2=0.90+0.70+0.90=2.50 ession O2:0.70 W2=0.30+0.20 0.50 o3:0.20 W4=0.11+0.30 0.41 Os:0.42 W=0.42+0.33 =0.7 O1:0.70 O2:0.90 Session 3 O4:0.30 O:0.33 K=L+(W+Fi*C/s Wi: Future frequency Fi Past frequen 2021/1/26
2021/1/26 9 Predicting future frequency Session 1 O1: 0.70 O2: 0.90 O3: 0.30 O4: 0.11 Session 2 O1: 0.60 O2: 0.70 O3: 0.20 O5: 0.42 Session 3 O1: 0.70 O2: 0.90 O4: 0.30 O5: 0.33 W1 = 0.70+0.60+0.70 = 2.00 W2 = 0.90+0.70+0.90 = 2.50 W3 = 0.30+0.20 = 0.50 W4 = 0.11+0.30 = 0.41 W5 = 0.42+0.33 = 0.75 Predicted Frequency Ki = L + ( Wi+Fi ) * Ci / Si Wi : Future frequency Fi : Past frequency
Byte-hit Rate measures bandwidth reduction Byte Hit Rate=/ Bytes answered by cache I I Total bytes Byte Hit Rate vs Cache Size on NASA web log NGRAM GDSF GDSize LRU 0 0.002 0.004 0006 0008 0.01 Cache Size(%) 2021/1/26
2021/1/26 10 Byte-hit Rate measures bandwidth reduction Byte Hit Rate vs Cache Size on NASA web log 0 1 0 2 0 3 0 4 0 5 0 0 0.002 0.004 0.006 0.008 0.01 Cache Size (%) Byte Hit Rate % NGRAM GDSF GDSize LFUDA LRU Byte Hit Rate = | Bytes answered by cache | | Total bytes |
Prefetch VS No-prefetch Relative Network traffic NASA Fractional Latency (NASA) 85 NASA Relative Network Traffic 75 Fractionallatency (NASA) 65 55 E+UmL 45 000m004000 35 002004000001 00002000400060008001 -o-Ngram +-Ngramt+Prefetch Cache size(%g) +导的门 2021/1/26
2021/1/26 11 Relative Network Traffic (NASA) NASA Relative Network Traffic 0 10 20 30 40 50 60 70 80 90 100 0 0.002 0.004 0.006 0.008 0.01 Cache size(%) Relative Network Traffic (%) Ngram Ngram+Prefetch NASA Fractional Latency 25 35 45 55 65 75 85 0 0.002 0.004 0.006 0.008 0.01 Cache size(%) Fractional latency (%) Ngram Ngram+Prefetch Fractional latency (NASA) Prefetch vs. No-prefetch