In periodic wireless broadcasting, air behaves like a storage medium requiring new data organization and access methods.Due to power limit for the portable units (ex. the palmtop), how to design an energy-saving organization is a key issue.Imielinski et al. have proposed the hashing based schemes, including the Hashing A and Hashing B schemes, to save energy in the progress of getting data of interest. The Hashing B scheme improves the directory miss phenomenon in the Hashing A scheme, where the directory miss is that the client's initial probe comes before
the bucket containing his key but after the bucket which contains a proper offset. However, based on these two schemes, if the differences between the minimum overflow and the other overflows are large extremely or the small overflows appear near the rear part of the broadcast file, both schemes have a poor performance. Therefore, in this thesis, we propose four multiple-hashing-functions-based
schemes, including the FirstR, FirstL, AvgK and TopK schemes, to overcome such the situations.
The basic idea is to use cutlines to divide the
broadcast file with N logical buckets into several regions, and then each region may have
the different minimum overflow. Since the minimum overflow in each region can be different, we can have different hashing functions for those regions to determine the positions of the designated buckets.
Among the proposed schemes, the difference is how to determine the positions of the cutlines. The FirstR scheme finds those cutlines from the right end to the left whenever the difference of overflows of two adjacent logical buckets is greater than or equal to 1. The FirstL scheme finds those cutlines from the left end to the right whenever the difference of overflows of two adjacent logical buckets is greater than or equal to 1. In the AvgK scheme, we first calculate AvgD, the average of the differences of two consecutive overflows whose values are large than or equal to 1. Then we find cutlines from the left end to the right whenever the difference of
two adjacent logical buckets is greater than or equal to AvgD. The TopK determines the cutlines by considering the descending order of the differences of overflows. From our performance analysis and simulation study, the
performance of the TopK scheme is the best among the proposed schemes. Therefore, we then make a comparison between the TopK scheme and the Hashing B scheme. Since the number of the hashing functions in the TopK scheme is larger than those in the Hashing B, the physical bucket in the TopK scheme is somewhat bigger than that in the m Hashing B scheme. In our simulation, we have considered this factor as well. From our performance analysis and simulation study, we show that the performance of the TopK scheme performs better than that of the Hashing B
scheme, even though the above factor about the storage size is considered. The TopK scheme improves the directory miss in the Hashing B scheme; therefore, the average access time is
improved excellently.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0718101-124424 |
| Date | 18 July 2001 |
| Creators | Shen, Jun-Hong |
| Contributors | Chien-I Lee, Gen-Huey Chen, Ye-In Chang, San-Yih Hwang |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0718101-124424 |
| Rights | restricted, Copyright information available at source archive |
Page generated in 0.0022 seconds