We show that performance of some basic methods for the partitioning of signature files, namely Quick Filter and Fixed Prefix, can be easily evaluated by means of a closed formula. The approximation is based on well-known results from probability theory, and, as shown by simulations, introduces no appreciable errors when compared with the exact, cumbersome formulas used so far. Furthermore, we prove that the exact formulas for the two methods coincide. Although this does not imply that the two methods behave in the same way, it sheds light on the way they could be compared. © 1993, ACM. All rights reserved.
Estimating Accesses in Partitioned Signature File Organizations / Ciaccia P.; Zezula P.. - In: ACM TRANSACTIONS ON INFORMATION SYSTEMS. - ISSN 1046-8188. - STAMPA. - 11:2(1993), pp. 133-142. [10.1145/130226.145014]
Estimating Accesses in Partitioned Signature File Organizations
Ciaccia P.;
1993
Abstract
We show that performance of some basic methods for the partitioning of signature files, namely Quick Filter and Fixed Prefix, can be easily evaluated by means of a closed formula. The approximation is based on well-known results from probability theory, and, as shown by simulations, introduces no appreciable errors when compared with the exact, cumbersome formulas used so far. Furthermore, we prove that the exact formulas for the two methods coincide. Although this does not imply that the two methods behave in the same way, it sheds light on the way they could be compared. © 1993, ACM. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
