Performance comparison of signature-based multikey access methods

In this paper we evaluate the performance of signature-based multikey access methods. We first establish a taxonomy of signature-based access methods; i.e. One-Path Single-Level (OPSL), Two-Path Single-Level (TPSL), One-Path Two-Level (OPTL), and Two-Path Two-Level (TPTL). Then we show from experimental results that two-path methods such as TPSL and TPTL achieve about 20-80% gains on retrieval with the expense of 4-9 % more storage overhead, compared to OPSL and OPTL. Among two-path methods. TPTL outperforms TPSL on retrieval when the number of matching records is relatively small (less than 80); otherwise TPSL is better.