Dynamic partitioning of signature files

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Dynamic partitioning of signature files

Full text

Pdf (2.22 MB)

Source

ACM Transactions on Information Systems (TOIS) archive
Volume 9 , Issue 4 (October 1991) table of contents

Pages: 336 - 367

Year of Publication: 1991

ISSN:1046-8188

Authors

P. Zezula	IEI-CNR, Pisa, Italy
F. Rabitti	IEI-CNR, Pisa, Italy
P. Tiberio	Univ. of Bologna, Bologna, Italy

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 29, Citation Count: 16

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/119311.119313 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Sudhir R. Ahuja , Charles S. Roberts, An associative/parallel processor for partial match retrieval using superimposed codes, Proceedings of the 7th annual symposium on Computer Architecture, p.218-227, May 06-08, 1980, La Baule, United States [doi>10.1145/800053.801929]
	2	Elisa Bertino , Fausto Rabbiti , Simon Gibbs, Query processing in a multimedia document system, ACM Transactions on Information Systems (TOIS), v.6 n.1, p.1-41, Jan. 1988 [doi>10.1145/42279.42281]
	3	Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
	4	W. W. Chang , H. J. Schek, A signature access method for the Starburst database system, Proceedings of the 15th international conference on Very large data bases, p.145-153, July 1989, Amsterdam, The Netherlands
	5	J. W. Chang , J. H. Lee , Y. J. Lee, Multikey access methods based on term discrimination and signature clustering, Proceedings of the 12th annual international ACM SIGIR conference on Research and development in information retrieval, p.176-185, June 25-28, 1989, Cambridge, Massachusetts, United States [doi>10.1145/75334.75353]
	6	H.-T. Chou , David J. Dewitt , Randy H. Katz , Anthony C. Klug, Design and implementation of the Wisconsin storage system, Software—Practice & Experience, v.15 n.10, p.943-962, Oct. 1985 [doi>10.1002/spe.4380151003]
	7	Chris Faloutsos , Stavros Christodoulakis, Signature files: an access method for documents and its analytical performance evaluation, ACM Transactions on Information Systems (TOIS), v.2 n.4, p.267-288, Oct. 1984 [doi>10.1145/2275.357411]
	8	S. Christodoulakis , M. Theodoridou , F. Ho , M. Papa , A. Pathria, Multimedia document presentation, information extraction, and document formation in MINOS: a model and a system, ACM Transactions on Information Systems (TOIS), v.4 n.4, p.345-383, Oct. 1986 [doi>10.1145/9760.9764]
	9	R. M. Colomb , Jayasooriah, A clause indexing system for PROLOG based on superimposed coding, Australian Computer Journal, v.18 n.1, p.18-25, Feb. 1986
	10	Uwe Deppisch, S-tree: a dynamic balanced signature index for office retrieval, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.77-87, September 1986, Palazzo dei Congressi, Pisa, Italy [doi>10.1145/253168.253189]
	11	Didier DuBois , Henri Prade, Fuzzy Sets and Systems: Theory and Applications, Academic Press, Inc., Orlando, FL, 1997
	12	Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
	13	FALOUTSOS, C. Integrated access methods for message using signature files. In IFIP Working Conference on Methods and Tools for Office Systems (Pisa, Oct. 1986), pp. 135-157.
	14	Christos Faloutsos, Multiattribute hashing using Gray codes, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.227-238, May 28-30, 1986, Washington, D.C., United States [doi>10.1145/16894.16877]
	15	C. Faloutsos, Signature-based text retrieval methods: a survey, Data Engineering, v.13 n.1, p.25-32, Mar. 1990
	16	Christos Faloutsos , Stavros Christodoulakis, Description and performance analysis of signature file methods for office filing, ACM Transactions on Information Systems (TOIS), v.5 n.3, p.237-257, July 1987 [doi>10.1145/27641.28057]
	17	Michael Freeston, The BANG file: A new kind of grid file, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.260-269, May 27-29, 1987, San Francisco, California, United States [doi>10.1145/38713.38743]
	18	Gaston H. Gonnet , Per Åke Larson, External hasing with limited internal storage, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588153]
	19	Gaston H. Gonnet , Per-Åke Larson, External hashing with limited internal storage, Journal of the ACM (JACM), v.35 n.1, p.161-184, Jan. 1988 [doi>10.1145/42267.42274]
	20	GRAY, F. Pulse code communications. U.S. Patent 2632058, March 17, 1953.
	21	HUTFLESZ, A., Six, H. W., AND WIDMAYER, P. Twin grid files: Space optimizing access
	22	LARSON, P. Linear hashing with partial expansions In Froceeatngs o1' Oth lnternattonat Conference on VLDB (Montreal, Oct. 1980), VLDB Endowment, 1980, pp. 212-223
	23	Per-Åke Larson , Ajay Kajla, File organization: implementation of a method guaranteeing retrieval in one access, Communications of the ACM, v.27 n.7, p.670-677, July 1984 [doi>10.1145/358105.358193]
	24	Dik Lun Lee, A Word-Parallel, Bit-Serial Signature Processor for Superimposed Coding, Proceedings of the Second International Conference on Data Engineering, p.352-359, February 05-07, 1986
	25	Dik Lun Lee , Chun-Wu Leng, Partitioned signature files: design issues and performance evaluation, ACM Transactions on Information Systems (TOIS), v.7 n.2, p.158-180, April 1989 [doi>10.1145/65935.65937]
	26	Dik Lun Lee , Chun-Wu Leng, A Partitioned Signature File Structure for Multiattribute and Text Retrieval, Proceedings of the Sixth International Conference on Data Engineering, p.389-397, February 05-09, 1990
	27	LITWlN, W. Linear hashing: a new tool for files and table addressing. In Proceedings of 6th Internatzonal Conference on VLDB (Montreal, Oct. 1980), pp. 212-223
	28	MClLROY, M, D. Development of a spelling list. IEEE Trans Commun. COM-30, 1 (Jan. 1982), 91-99.
	29	J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
	30	Ekow J. Otoo, Balanced multidimensional extendible hash tree, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.100-113, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.6015]
	31	John L. Pfaltz , William J. Berman , Edgar M. Cagley, Partial-match retrieval using indexed descriptor files, Communications of the ACM, v.23 n.9, p.522-528, Sept. 1980 [doi>10.1145/359007.359013]
	32	F. Rabitti , P. Zezula, A dynamic signature technique for multimedia databases, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.193-210, September 05-07, 1990, Brussels, Belgium [doi>10.1145/96749.98223]
	33	F. Rabitti , J. Zizka, Evaluation of access methods to text documents in office systems, Proc. of the third joint BCS and ACM symposium on Research and development in information retrieval, p.21-40, November 1984, King's College, Cambridge
	34	RAMAMOHANARAO, t~., AND LLOYD, L W Dynamic hashing schemes Comput J. 25, 4 (Nov. 1982), 478-485.
	35	K Ramamohanarao , R Sacks-Davis, Recursive linear hashing, ACM Transactions on Database Systems (TODS), v.9 n.3, p.369-391, Sept. 1984 [doi>10.1145/1270.1285]
	36	Kotagiri Ramamohanarao , John Shepherd, A superimposed codeword indexing scheme for very large Prolog databases, Proceedings on Third international conference on logic programming, p.569-576, September 1986, London, United Kingdom
	37	M. V. Ramakrishna , W. R. Tout, Dynamic external hashing with guaranteed single access retrieval, 3rd International Conference, FODO 1989 on Foundations of Data Organization and Algorithms, p.187-201, July 1989, Paris, France
	38	ROBERTS, C. S. Partial match retrieval via the method of the superimposed codes. Prec. IEEE 67, 12 (Dec. 1979), 1624-1642.
	39	John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
	40	R. Sacks-Davis , A. Kent , K. Ramamohanarao, Multikey access methods based on superimposed coding techniques, ACM Transactions on Database Systems (TODS), v.12 n.4, p.655-696, Dec. 1987 [doi>10.1145/32204.32222]
	41	SACK-DAviS, R., AND RAMAMOHANARAO, K. A two level superimposed coding scheme for partial match retrieval. Inf. Syst. 8, 4 (Oct. 1983), 273-280.
	42	Craig Stanfill , Brewster Kahle, Parallel free-text search on the connection machine system, Communications of the ACM, v.29 n.12, p.1229-1239, Dec. 1986 [doi>10.1145/7902.7907]
	43	Craig Stanfill , Brewster Kahle, Parallel free-text search on the connection machine system, Communications of the ACM, v.29 n.12, p.1229-1239, Dec. 1986 [doi>10.1145/7902.7907]
	44	C. (Costantino) Thanos, Multi-Media Office Filing: The Multos Approach, Elsevier Science Inc., New York, NY, 1990
	45	Dennis Tsichritzis , Stavros Christodoulakis , P. Economopoulos , Christos Faloutsos , A. Lee , D. Lee , J. Vandenbroeck , Carson C. Woo, A Multimedia Office Filing System, Proceedings of the 9th International Conference on Very Large Data Bases, p.2-7, October 31-November 02, 1983
	46	WONG, H. K. T., LIu, H., OLKEN, F., ROTEM, D., AND WONG, L. Bit transposed files. In Proceedings of llth International Conference on VLDB (Stockholm, Aug. 1985), pp. 448-457.
	47	Z~ZUL^, P., AND ZIZKA, J. FOPES: File organization performance prediction system In Foundations of Data Organization. S. Ghosh, Y. Kambayashi, and K. Tanaka, Eds. Plenum Press, New York, 1987, pp. 399-406.
	48	ZEZULA, P. How to organize statistical files. J. Official Stat 3, i (Jan. 1987), 3-17.
	49	ZEZULA, P. Linear hashing for signature files. In Proceedings of the IFIP TC6 and TC8 International Symposium on Network Information Processing Systems. (Sofia, Bulgaria, May 1988), pp. 192-196. Also available from Network Information Processing Systems, K. Boyanov, and R. Angelinov Eds. Elsevier Science, IFIP, 1989, 243-250.
	50	ZEZULA, P., AND TmEmo, P. Selecting signature files for specific applications. CIOC-CNR, Bologna, Tech. Rep. 74, Nov. 1990.

CITED BY 16

	Paolo Ciaccia , Paolo Tiberio , Pavel Zezula, Declustering of key-based partitioned signature files, ACM Transactions on Database Systems (TODS), v.21 n.3, p.295-338, Sept. 1996
	Paulo Ciaccia , Pavel Zezula, Estimating accesses in partitioned signature file organizations, ACM Transactions on Information Systems (TOIS), v.11 n.2, p.133-142, April 1993
	Guang-Ho Cha , Chin-Wan Chung, Object-oriented retrieval mechanism for semistructured image collections, Proceedings of the sixth ACM international conference on Multimedia, p.323-332, September 13-16, 1998, Bristol, United Kingdom
	Justin Zobel , Alistair Moffat , Kotagiri Ramamohanarao, Inverted files versus signature files for text indexing, ACM Transactions on Database Systems (TODS), v.23 n.4, p.453-490, Dec. 1998
	Fabio Grandi , Paolo Tiberio , Pavel Zezula, Frame-sliced partitioned parallel signature files, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.286-287, June 21-24, 1992, Copenhagen, Denmark
	Deniz Aktug , Fazli Can, Analysis of multiterm queries in a dynamic signature file organization, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.96-105, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States
	Dik Kun Lee , Liming Ren, Document ranking on weight-partitioned signature files, ACM Transactions on Information Systems (TOIS), v.14 n.2, p.109-137, April 1996
	Jeong-Ki Kim , Jae-Woo Chang, A new parallel signature file method for efficient information retrieval, Proceedings of the fourth international conference on Information and knowledge management, p.66-73, November 29-December 02, 1995, Baltimore, Maryland, United States
	Eleni Tousidou , Panayiotis Bozanis , Yannis Manolopoulos, Signature-based structures for objects with set-valued attributes, Information Systems, v.27 n.2, p.93-121, April 2002
	Ben Carterette , Fazli Can, Comparing inverted files and signature files for searching a large lexicon, Information Processing and Management: an International Journal, v.41 n.3, p.613-633, May 2005
	H. Andr\'e-J\osson , D. Z. Badal, Indexing time series using signatures, Intelligent Data Analysis, v.4 n.1, p.67-92, January 2000
	Justin Zobel , Alistair Moffat, Inverted files for text search engines, ACM Computing Surveys (CSUR), v.38 n.2, p.6-es, 2006
	Pavel Zezula , Paolo Ciaccia , Paolo Tiberio, Hamming Filters: A Dynamic Signature File Organization for Parallel Stores, Proceedings of the 19th International Conference on Very Large Data Bases, p.314-327, August 24-27, 1993
	Sven Helmer , Guido Moerkotte, A performance study of four index structures for set-valued attributes of low cardinality, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.3, p.244-261, October 2003
	Pavel Zezula , Paolo Ciaccia , Paolo Tiberio, Key-based partitioned bit-sliced signature file, ACM SIGIR Forum, v.29 n.2, p.20-34, Fall 1995
	Fabio Grandi, On the signature weight in “multiple” m signature files, ACM SIGIR Forum, v.29 n.1, p.20-25, Spring 1995

INDEX TERMS

Primary Classification:
E. Data
E.5 FILES
Subjects: Organization/structure

Additional Classification:
H. Information Systems
H.2 DATABASE MANAGEMENT
H.2.2 Physical Design
Subjects: Access methods
H.3 INFORMATION STORAGE AND RETRIEVAL
H.3.2 Information Storage
Subjects: File organization
H.4 INFORMATION SYSTEMS APPLICATIONS
H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)

General Terms:
Design, Performance

REVIEW

"Fazli Can : Reviewer"

Signature files are especially useful for the retrieval of unformatted data such as text. In a signature file, each record is represented by a bit string called its signature. The weak point of this approach is the difficulty of term weight pr more...

Collaborative Colleagues:

P. Zezula: colleagues

F. Rabitti: colleagues

P. Tiberio: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player