SD-tree Based Indexing for Nested Object Query Processing

Abstract

Aiming at the fast retrieval of nested objects, we introduce a variation of the signature file based top-down hierarchy retrieval using an index structure called SD (Signature Declustering) tree. Signature files which were initially used on text data for their filtering capability have now been applied in Object Oriented Data Base Systems (OODBSs). Most of the proposed methods for Object Oriented query handling suffer from either longer retrieval time or comparison procedure complexity. This is mainly due to the poor filtering capability of the index structure in order to support complex query styles in OODBSs. In this paper we focus on the Object Oriented query handling of nested queries in the class hierarchy using an intermediate indexing structure called SD-tree that represents object signatures in a compact manner. Further it helps to retrieve all matching objects in a single access. We compare the performance of SD-tree based query processing with the signature tree based query processing reported recently. Our experimental analysis on large data sets shows that combined with query signature hierarchies SD-tree retrieves the matching objects quickly and therefore improves the time complexity of query evaluation substantially.