"Evolved" Caches Could Speed the Net

SpaceDilbert writes "According to New Scientist, evolutionary algorithms could make many network caches twice as efficient. This article describes a study carried out by a US researcher and two German academics, who "evolved" algorithms to determine what data should be held at a cache and for how long."

Comments

LRU Rules

[Mirk]

There's a good reason why LRU caching (least recently used) is so widespread, and that is that it's very very hard to come up with a sophisticated algorithm that outperforms this very naive one.

For the uninitiated, elements are added to an LRU cache until it fills up; thereafter, whenever a new element is added, space is made for it by throwing away the least-recently used one. Note, least recently used, not the least recently added, i.e. the oldest, since an element that was cached long ago may be used all the time, and so be well worth its place in the cache. For example, consider the company-logo image that your browser caches when you visit a new site and that is embedded in every page on that site. However old it gets, it's likely to continue to be used while you're on the site. As soon as you move to another site, it gradually shuffles its way down the deck until it falls off the bottom - which is precisely what you want.

Re:LRU Rules

[rossjudson]

ARC caches fairly handily outperform LRU. When LRU is appropriate they adapt towards it. When frequency is important they adapt towards that.

Re:LRU Rules

[Fzz]

ARC caches fairly handily outperform LRU.

Thanks for the pointer. Here's a link to some background on ARC, and a paper describing the algorithm. Looks like an interesting algorithm.

Re:Not DNS

[Short Circuit]

If I'm not mistaken, the DNS RFC takes into account the fact that domain records will be cached. That's why the records have expiration and refresh times on them.

A note on hill-climbing

[Animats]

Genetic algorithms are methods for optimization in bumpy spaces. The basic goal is "find x such that f(x) is maximized". As optimization algorithms, they should always be tested against the two simple optimization algorithms - basic hill climbing, and random search.

If the search space is not dominated by local maxima, basic hill climbing (go for the best neighboring value) will work. And it will be fast. If the function is differentiable, it can be orders of magnitude faster than other methods, because you can use a variant of Newton's Method.

If the search space is small, random search (just guessing) will work by exhaustively searching the space. This is obvious, but tends to be ignored in academic papers all too often.

This discussion also applies to neural nets and simulated annealing.

Now this article at least describes a problem for which a GA might actually be useful. Many such articles don't. But they haven't demonstrated that you need a bumpy hill-climbing algorithm.

This is why, despite all the hype, GAs, neural nets, and such aren't used all that much. The search space has to have the right properties. Not too small, not too big, bumpy, but not too bumpy.

Legos and Tron mentioned in his thesis

[the frizz]

The article link is light on details of the evolution algorithm, but Pablo Funes's home page has the text of his thesis on Evolution of Complexity in Real-World Domains. It talks about his use of evolving algorithms on topics like designing the strongest lego brick structure and playing Tron. Very cool, but not its application to caching.

The is even a link to an online Tron game where us humans can play versus his evolving algorithms. The win/loss stats for his algorithm is approaching even. Given that humans can also evolve in the Tron game play, I imagine that the algorithm will have a head start over the new influx of slashdot visitors and start to win more often than not over the next week. I never got to play though. The SQL db to mange the stats was already down then I tried.

Re:*sigh*

[NialScorva]

Evolution is the change in allele frequencies over time. Pure and simple, that's all it is. Check any evolutionary biology book. The notion of giraffes sprouting gills is absurd and not even remotely what evolution is except in the creationist strawmen. What prevents a whole lot of small changes from adding up? No one has discovered a barrier or any reason that this wouldn't occur. It's like saying that water can move grains of sand, but there's no proof that a lot of water will eventually erode a beach.

The evolutionary algorithm will have a range of all possible algorithms that can be developed, so in a sense it is limited to "test various algorithms", though it would be testing all possible algorithms. Similarly biological evolution is limitted to testing various imperfect self-replicators, meaning all possible imperfect self-replicators. It is further constrained by the current state, but then that's the problem with non-biological GAs as well, the King of the Hill effect.

Re:*sigh*

[Conspiracy_Of_Doves]

ANY environmental adaptation of genetic code over multiple generations is evolution. It does not have to be a major change. BTW, creationists are the only ones that make a distinction between macro-evolution and micro-evolution. If fact, creationists are the only ones that I have ever heard use the terms.

Re:What makes a good cache?

[a_ghostwheel]

There are other types of neural networks than just standard back-propagating ones. Linear vector quantization is much better at solving classification problems (ART-based algorithm should be good too). Problem is that in many "on-the-surface" problems have better specialized solution than just a generic NN or GA brute-force approach. This situation led to drastic decrease in funding for NN research.