Accelerating Queries on Very Large Datasets - Scientific Data Management - page 183

Chapter 6

Accelerating Queries on Very
Large Datasets

Ekow Otoo and Kesheng Wu
Lawrence Berkeley National Laboratory

Contents

6.1 Introduction .......................................................... 184

6.2 Characteristics of Scientific Data .................................... 185

6.3 A Taxonomy of Index Methods ...................................... 189

6.4 Single-Attribute Index Schemes ..................................... 193

6.4.1 Sequential Scan Access ....................................... 193

6.4.2 Tree-Structured Indexing ..................................... 194

6.4.3 Hashing Schemes .............................................. 196

6.5 Multidimensional Index Schemes .................................... 196

6.5.1 Multidimensional Tree-Structured Indexing Methods ........ 200

6.5.1.1 K-D-Tree and LSD-Tree ............................. 200

6.5.1.2 R-Tree and Its Variants .............................. 200

6.5.2 Multidimensional Direct Access Methods .................... 203

....................................

6.5.3 Hybrid Indexing Methods 203

..........

6.5.3.1 Quaternary/Hierarchical Triangular Mesh 205

6.5.4 Simple Scanned Access of Multidimensional Datasets ....... 207

6.6 Bitmap Index ........................................................ 208

6.6.1 The Basic Bitmap Index ...................................... 209

6.6.2 Compression .................................................. 210

6.6.3 Bitmap Encoding ............................................. 213

6.6.4 Binning ........................................................ 215

6.6.5 Implementations .............................................. 217

6.7 Data Organization and Parallelization .............................. 218

6.7.1 Data Processing Systems ..................................... 219

6.7.1.1 Column-Based Systems .............................. 219

6.7.1.2 Special-Purpose Data Analysis Systems ............. 219

6.7.1.3 MapReduce Parallel Analysis System ............... 220

6.7.1.4 Custom Data Processing Hardware ................. 221

183