Paulo Ciaccia
Pavel Zezula
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.
- 1 FALOUTSOS, C., AND CHRISTODOULAKiS, S. Description and performance analysis of signature file methods for office filing. ACM Trans. Inf. Syst. 5, 3 (July 1987), 237 257. Google Scholar
- 2 FELLER, W An Introductwn to Probabd~ty Theory and Its Apphcations Vol. 1, 3rd edition, Wiley~ New York, 1968.Google Scholar
- 3 Gm~NDL F., TIBERIO, P., AND ZEZULA, P. Frame-shce partitioned parallel signature files. In Proceedings of the ACM SIGIR'92, 15th International Conference on Research and Development tn Informatwn Retrzeval, Copenhagen, (June 1992), 286-297. Google Scholar
- 4 LEE, D. L., AND LENG, C. A partitioned signature file structure for multiattribute and text retrieval. In Proceedings of the 6th IEEE Internatwnal Conference on Data Engzneerzng (Los Angeles, Feb. 1990), 389 397. Google Scholar
- 5 LEE, D. L., AND LENG, C. Partitioned signature files: Design issues and performance evaluation. ACM Trans. Inf. SYst. 7, 2 (Apr. 1989), 158 180. Google Scholar
- 6 LITWIN, W. Linear hashing: A new tool for files and table addressing In Proceedtngs of the 6th VLDB International Conference (Montreal, 1980), 212-223.Google Scholar
- 7 RABITTI, F., AND ZEZULA, P. A dynamic signature technique for multimedia databases. In Proceedings of the ACM-SIGIR'90, 13th International Conference on Research and Development in Informatwn Retrieval (Brussels, Sept 1990), 193-210. Google Scholar
- 8 ZEZULA, P. Linear hashing for signature files. In Network Informatlon Processing Systems. Elsevier Science (North-Holland) 1989, 243 250.Google Scholar
- 9 ZEZULA, P., RABITTL F., AND TIBERIO, P. Dynamic partitioning of s~gnature files. ACM Trans. Inf. Syst. 9, 4 (Oct. 1991), 336 369. Google Scholar
Index Terms
- Estimating accesses in partitioned signature file organizations
Recommendations
Declustering of key-based partitioned signature files
Access methods based on signature files can largely benefit from possibilities offered by parallel environments. To this end, an effective declustering strategy that would distribute signatures over a set of parallel independent disks has to be combined ...
Document ranking on weight-partitioned signature files
A signature file organization, called the weight-partitioned signature file, for supporting document ranking is proposed. It employs multiple signature files, each of which corresponds to one term frequency, to represent terms with different term ...
Performance of the Vesta parallel file system
IPPS '95: Proceedings of the 9th International Symposium on Parallel ProcessingVesta is an experimental parallel file system implemented on the IBM SPI. Its main features are support for parallel access from multiple application processes to file, and the ability to partition and re-partition the file data among these processes. ...
Reviews
Fazli Can
Quick filter (QF), or linear hashing with superimposed signatures [1], and fixed prefix (FP) [2] are two methods for signature file partitioning. QF and FP are designed for dynamic and static environments, respectively. The performance of a partitioning scheme can be analyzed using the partition activation ratio (PAR), which is defined as the ratio of the number of partitions that must be searched to the total number of existing partitions. The combinatorial PAR formulas for QF and FP look different due to unlike derivations and are difficult to understand and compute. In this paper, Ciaccia and Zezula prove that the exact PAR formulas for QF and FP methods coincide (although this does not mean that the two methods behave in the same manner). They develop an approximate closed PAR formula that is applicable to both QF and FP and is easy to compute and understand. The quality of their approximation is validated by simulation and relies on probability theory. This paper is important for researchers working on signature files and may be a source of inspiration for this type of research. It is nicely done.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments