False Drop Analysis of Set Retrieval with Signature Files

スポンサーリンク

概要

• 論文の詳細を見る

• Modern database systems have to support complex data objects, which appear in advanced data models such as object-oriented data models and nested relational data models. Set-valued objects are basic constructs to build complex structures in those models. Therefore, efficient processing of set-valued object retrieval (simply, set retrieval) is an important feature required of advanced database systems. Our previous work proposed a basic scheme to apply superimposed coded signature files to set retrieval and showed its potential advantages over the B-tree index based approach using a performance analysis model. Retrieval with signature files is always accompanied by mismatches called false drops, and proper control of the false drops is indispensable in the signature file design. This study intensively analyzes the false drops in set retrieval with signature files. First, schemes to use signature files are presented to process set retrieval involving "has-subset," "is-subset," "has-intersection," and "is-equal" predicates, and generic formulas estimating the false drops are derived. Then, three sets of concrete formulas are derived in three ways to estimate the false drops in the four types of set retrieval. Finally, their estimates are validated with computer simulations, and advantages and disadvantages of each set of the false drop estimation formulas are discussed. The analysis shows that proper choice of estimation formulas gives quite accurate estimates of the false drops in set retrieval with signature files.

• 社団法人電子情報通信学会の論文
• 1997-06-25

著者

• Ishikawa Yoshiharu

  Graduate Institute Of Information Science Nara Institute Of Science And Technology (naist)

• Ishikawa Yoshiharu

  Graduate Institute Of Information Science Nara Institute Of Science And Technology

• KITAGAWA Hiroyuki

  Institute of Information Sciences and Electronics, University of Tsukuba

• Kitagawa Hiroyuki

  Institute Of Information Sciences And Electronics University Of Tsukuba

• Kitagawa Hiroyuki

  Institute Of Information Science And Electronics University Of Tsukuba

関連論文

• False Drop Analysis of Set Retrieval with Signature Files
• Requirement Specification and Derivation of ECA Rules for Integrating Multiple Dissemination-Based Information Sources (the 2002 IEICE Excellent Paper Award)
• Requirement Specification and Derivation of ECA Rules for Integrating Multiple Dissemination-Based Information Sources
• Design and Performance Analysis of Indexing Schemes for Set Retrieval of Nested Objects
• Optimization of Join-Type Queries in Nested Relational Databases
• Join Query Optimization in Object-Oriented Database
• A Web Search Method Integrating Taxonomy-based and Crawler-based Search Engines

スポンサーリンク