| Presentation | 1997/9/26 Towards Dynamic Clustering Jun Kiniwa, Tiko Kameda, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In two-level memories including some fast accessible pages, we investigate an effective clustering of data in each page. Given an offine sequence of requests, we derive the ratio bound of the worst clustering to the optimal clustering if the optimal page replacement policy MIN is used. Next we present two heuristic methods, called Longest Unused and Nearest Neighbor, which can generate desirable clusterings. If we can do clustering beforehand by using our methods, the bound above can be highly improved in the Nearest Neighbor, in particular. Assuming the locality of reference, we also examine the performance of our methods by simulation for online sequences of requests and the page replacement policy LRU. In this situation, the Longest Unused turns out to be superior to the Nearest Neighbor. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | offline clustering / two-level memory / MIN page replacement / LRU page replacement / heuristic algorithm / dynamic clustering |
| Paper # | COMP97-44 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1997/9/26(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Towards Dynamic Clustering |
| Sub Title (in English) | |
| Keyword(1) | offline clustering |
| Keyword(2) | two-level memory |
| Keyword(3) | MIN page replacement |
| Keyword(4) | LRU page replacement |
| Keyword(5) | heuristic algorithm |
| Keyword(6) | dynamic clustering |
| 1st Author's Name | Jun Kiniwa |
| 1st Author's Affiliation | Department of Management Science, Kobe University of Commerce() |
| 2nd Author's Name | Tiko Kameda |
| 2nd Author's Affiliation | School of computing Science, Simon Fraser University |
| Date | 1997/9/26 |
| Paper # | COMP97-44 |
| Volume (vol) | vol.97 |
| Number (no) | 290 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |