Indexing Cached Multidimensional Objects in Large Main Memory Systems
Indexing Cached Multidimensional Objects in Large Main Memory Systems
Files
Publication or External Link
Date
2006-06-05
Authors
Nam, Beomseok
Sussman, Alan
Advisor
Citation
DRUM DOI
Abstract
Semantic caches allow queries into large datasets to leverage cached
results either directly or through transformations, using semantic
information about the data objects in the cache. As the price of main
memory continues to drop and its size increases, the
size of semantic caches grows proportionately, and it is becoming
expensive to compare the semantic information for each data object in the
cache against a query predicate. Instead, we propose to create an index
for cached objects. Unlike straightforward linear scanning, indexing
cached objects creates additional overhead for cache replacement. Since
the contents of a semantic cache may change dynamically at a high rate,
the cache index must support fast inserts and deletes as well as fast
search. In this paper, we show that multidimensional indexing helps
navigate efficiently through a large
semantic cache in spite of the additional overhead and overall is
considerably less expensive than linear scanning. Little emphasis has been
laid upon the performance of multidimensional index inserts and deletes,
as opposed to search performance. We compare the performance of a few
widely used multidimensional indexing structures with our SH-tree, looking
at insert, delete, and search operations, and show that SH-trees overall
perform better for large semantic caches than the widely used indexing
techniques.