An average-case analysis of MAT and inverted file

DOI10.1016/0304-3975(88)90069-2MaRDI QIDQ1114453zbMATH OpenOpenAlexFDO

Authors S. H. Smith

Publication date 1988

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(88)90069-2

zbMATH Keywords

complete match queryinverted filesmultiple attribute treerange query

Mathematics Subject Classification ID

Data structures (68P05) Information storage and retrieval of data (68P20)

Review text

It is shown in the literature that the multiple attribute tree outperforms inverted files in terms of worst-case complexities for partial-match queries. In this paper, we estimate the expected values for the complexities of both complete match query and range query on multiple attribute tree and inverted files. We use a uniform probabilistic model for the input data space. We show that the multiple attribute tree is more efficient than the inverted file in terms of these expected value measures.

Recommendations

• scientific article; zbMATH DE number 4014072
• Optimal attribute ranking in multiple attribute tree
• Performance evaluation of shared and separate inverted files
• Multi-attribute hashing with multiple file copies for high performance partial-match retrieval
• Secondary attribute retrieval using tree data structures

Cites work

• Analysis and performance of inverted data base structures
• Analysis of the Multiple-Attribute-Tree Data-Base Organization
• Dynamic k-dimensional multiway search under time-varying access frequencies
• scientific article; zbMATH DE number 3845093 (Why is no real title available?)
• scientific article; zbMATH DE number 3829300 (Why is no real title available?)
• Modeling and analysis of data base organization. The doubly chained tree structure
• Multidimensional B-trees: Analysis of dynamic behavior
• Performance evaluation of attribute-based tree organization
• Secondary attribute retrieval using tree data structures

Cited in

(5)

• Data base design with the constrained multiple attribute tree
• scientific article; zbMATH DE number 3881908 (Why is no real title available?)
• Optimal attribute ranking in multiple attribute tree
• An set refinement algorithm with applications
• Secondary attribute retrieval using tree data structures

This page was built for publication: An average-case analysis of MAT and inverted file

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114453)