Space-Efficient Hot Spot Estimation

Loading...
Thumbnail Image

Files

CS-TR-3115.ps (294.63 KB)
No. of downloads: 214
CS-TR-3115.pdf (199.67 KB)
No. of downloads: 683

Publication or External Link

Date

1998-10-15

Advisor

Citation

DRUM DOI

Abstract

This paper is concerned with the problem of identifying names which occur frequently in an ordered list of names. Such names are called hot spots. Hot spots can be identified easily by counting the occurrences of each name and then selecting those with large counts. However, this simple solution requires space proportional to the number of names that occur in the list. In this paper, we present and evaluate two hot spot estimation techniques. These techniques guess the frequently occurring names, while using less space than the simple solution. We have implemented and tested both techniques using several types of input traces. Our experiments show that very accurate guesses can be made using much less space than the simple solution would require. (Also cross-referenced as UMIACS-TR-93-74)

Notes

Rights