On Apr 17, 2008, at 2:50 AM, YKY (Yan King Yin) wrote:
ARC (Adaptive Cache Replacement) seems to be one of the most popular methods, and it's based on keeping track of "frequently used" and "recently used". Unfortunately, for AGI / inference purposes, those may not be the right optimization objectives.
It is a cache replacement algorithm, what would be a "right optimization objective" for such an algorithm? There is a lot of cleverness in the use of the cache to maximize cache efficiency beyond the cache replacement algorithm -- it is one of the most heavily engineered parts of a database engine.
As an FYI, ARC is patented by IBM. PostgreSQL uses a different but similar algorithm that is indistinguishable from ARC in benchmarks (having implemented ARC briefly, not realizing that it was patented).
The requirement of inference is that we need to access a lot of *different* nodes, but the same nodes may not be required many times. Perhaps what we need is to *bundle* up nodes that are associated with each other, so we can read a whole block of nodes with 1 disk access. This requires a very special type of storage organization -- it seems that existing DBMSs don't have it =(
Again, most good database engines can do this, as it is a standard access pattern for databases, and most databases can solve this problem multiple ways. As an example, clustering and index- organization features in databases address your issue here.
It is pretty difficult to generate an access pattern use case that they cannot be optimized for with a good database engine. They are very densely engineered pieces of software, designed to be very fast while scaling well in multiple dimensions and adapting to varying workloads. On the other hand, if your use case is simple enough you can gain some significant speed for modest effort by writing your own engine that is purpose-built to be optimized for your needs.
J. Andrew Rogers ------------------------------------------- agi Archives: http://www.listbox.com/member/archive/303/=now RSS Feed: http://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: http://www.listbox.com/member/?member_id=8660244&id_secret=101455710-f059c4 Powered by Listbox: http://www.listbox.com
