Portal de Periódicos da CAPES

Random sampling from hash files

1990; Association for Computing Machinery; Volume: 19; Issue: 2 Linguagem: Inglês

10.1145/93605.98746

1943-5835

Frank Olken, Doron Rotem, Ping Xu,

Advanced Image and Video Retrieval Techniques

In this paper we discuss simple random sampling from hash files on secondary storage. We consider both iterative and batch sampling algorithms from both static and dynamic hashing methods. The static methods considered are open addressing hash files and hash files with separate overflow chains. The dynamic hashing methods considered are Linear Hash files [Lit80] and Extendible Hash files [FNPS79]. We give the cost of sampling in terms of the cost of successfully searching a hash file and show how to exploit features of the dynamic hashing methods to improve sampling efficiency.