BLOCK CONCATENATED SIGNATURES FOR PARTIAL MATCH RETRIEVAL

In this paper, a block concatenated signature (BCS) file scheme is pro posed to speed up partial match retrieval in very large databases. A B CS is generated for each block of the data file by hashing the attribu te values in the data block. Then the BCSs form a signature file which is used as an index to the data file. For a partial match retrieval q uery, a block query signature (BQS) is generated and compared with the BCSs. Only those data blocks whose corresponding BCSs match the BQS a re retrieved from secondary storage and compared with the actual query . The size of the BCS file is usually less than 15% of the size of the data file, and usually only a subset of each BCS is accessed. Compare d to the record signature schemes, the proposed BCS scheme has better performance because the number of signature blocks to be accessed is m uch smaller per query. Thus, we can obtain considerable speedup in par tial match retrieval by using the BCS file. The storage requirement an d the performance of the BCS file are evaluated and compared with thos e of other signature file schemes.