An average-case analysis of MAT and inverted file (Q1114453)

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.