An Index Structure for Fast Query Retrieval in Object Oriented Data Bases Using Signature Weight Declustering

摘要

An important question in information retrieval is how to create a database index which can be searched efficiently for the data one seeks. One such technique called signature file based access method is preferred for its easy handling of insertion and update operations. Most of the proposed methods use either efficient search method or tree based intermediate data structure to filter data objects matching the query. Use of search techniques retrieves the objects by sequentially comparing the positions of 1s in it. Such methods take longer retrieval time. On the other hand tree based structures traverse multiple paths making comparison process tedious. This study describes a new indexing technique for object-oriented data bases using the dynamic balancing of B+ tree called SD (Signature Declustering) tree. The SD-tree represents all 1s in signatures in a compact manner that results in saving of insertion and searching time. Analytical experiments have been conducted by varying the signature length and the distribution of signature weight. The study clearly indicates the advantage of fast retrieval time in a way quite different from the other methods suggested in the past.