View publication
| Title | D-cache: Universal Distance Cache for Metric Access Methods |
| Authors | Tomas Skopal, Jakub Lokoc, Benjamin Bustos |
| Publication date | May 2012 |
| Abstract |
The caching of accessed disk pages has been successfully used for decades in database technology, resulting in effective amortization of I/O operations needed within a stream of query or update requests. However, in modern complex databases, like multimedia databases, the I/O cost becomes a minor performance factor. In particular, metric access methods (MAMs), used for similarity search in complex unstructured data, have been designed to minimize rather the number of distance computations than I/O cost (when indexing or querying). Inspired by I/O caching in traditional databases, in this paper we introduce the idea of distance caching for usage with MAMsa novel approach to streamline similarity search. As a result, we present the D-cache, a main-memory data structure which can be easily implemented into any MAM, in order to spare the distance computations spent by queries/updates. In particular, we have modified two state-of-the-art MAMs to make use of D-cachethe M-tree and Pivot tables. Moreover, we present the D-file, an index-free MAM based on simple sequential search augmented by D-cache. The experimental evaluation shows that performance gain achieved due to D-cache is significant for all the MAMs, especially for the D-file. |
| Pages | 868-881 |
| Volume | 24 |
| Journal name | IEEE Transactions on Knowledge and Data Engineering |
| Publisher | IEEE Press (Piscataway, NJ, USA) |
| Reference URL |
|