PERFORMANCE COMPARISON OF SIGNATURE-BASED MULTIKEY ACCESS METHODS

Abstract

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.