Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10358797 | Journal of Visual Languages & Computing | 2014 | 8 Pages |
Abstract
Hybrid index structures support access to heterogeneous data types in multiple columns. Several experiments confirm the improved efficiency of these hybrid access structures. Yet, very little is known about the worst case time and space complexity of them. This paper aims to close this gap by introducing a theoretical framework supporting the analysis of hybrid index structures. This framework then is used to derive the constraints for an access structure which is both time and space efficient. An access structure based on a B+-Tree augmented with bit lists representing sets of terms from texts is the outcome of the analysis which is then validated experimentally together with a hybrid R-Tree variant to show a logarithmic search time complexity.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science Applications
Authors
Richard Göbel, Carsten Kropf, Sven Müller,