Caching Scheme for N-Type dictionary

Last Update : 95.7.29 (Sat), see the tail for change log.

brief explanation

In memory-cache structure, two main problem must be solved. One is how fast wanted item can be found in cache, and the other is how to select the victim to be forced out to secondary storage(hard disk).

sequential search is very good for 10. (there must be some reference for this convicement.) And why 10 is selected? only one lookup is good. then O(10).

And is there any enough reason to select victim in one bucket row which is the same hash value.

it can suffer from the main problem of Hashing scheme - clustering. But I think there exists not so many word to be kept in cache. And if it is used for entire sentence or one file, then this scheme will work very well!

And hit ratio will be increased as this caching method is used over time.

There must be some testament for this scheme.


change log


Home of MoA, Features of MoA
Byoung-Gyu, Chang / bgjang@csone.kaist.ac.kr