An average-case analysis of MAT and inverted file (Q1114453)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An average-case analysis of MAT and inverted file |
scientific article |
Statements
An average-case analysis of MAT and inverted file (English)
0 references
1988
0 references
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.
0 references
multiple attribute tree
0 references
inverted files
0 references
complete match query
0 references
range query
0 references