# Presentation: 177018

## High-dimensional indexing techniques

**Kesheng John Wu**
**Ekow Otoo**
**Arie Shoshani**

## The big picture

**grid**

**storage**

**MPI-IO**

**file**

**Request**
**Interpreter**

**dataset**

**Data mining**

**Distributed**

**Large**

## The big picture

*Request interpreter*

*Logical request*

*Qualified objects*

*Request planning/execution*

*Execution services*

*grid*

*LBNL*

*PPDG*

*MPI-IO, ...*

*Sub-task schedule*

## Problem statement

**Main objective: maps logical request to qualified objects**
**a logical request:**
**20001015<=eventTime & 200<energy<300 ...**
**objects:**
**set of object IDs; **
**set of files containing the objects; **
**offsets within the files, ...**

## Requirements & Status

**General requirements**
**User request data in terms of their scientific domain, not file names or offsets in files**
**Each object may be described in hundreds of attributes**
**Each request is in terms of range predicates on a handful of attributes (partial range query)**
**Status**
**Initially motivated by a HENP experiment: STAR **
**Software originally developed under GC and is currently in use at BNL**

## Large high-dimensional datasets

**Number of attributes / columns: 200 – 500**
**Number of objects / events: 10****8**** – 10****9 **
**File containing one attribute: 400MB – 4GB**
**Total size over all attributes: 80GB – 2TB**

*A1*

*A2*

*A3*

*A4*

*...*

*Object ID*

*0*

*1*

*2*

*.*
*.*
*.*

*10**9** *

*10**8 *

*.*
*.*
*.*

**Goal:**** develop an index, so that:**
**Read as little as possible from disk**
**Minimize computation in memory**

- Curse of dimensionality

## Well known indexing methods

**B-tree based indices**
**One or a small number of attributes**
**Index size may be up to 3 times the data size**
**R-tree based indices**
**Small number of attributes, say, < 10**
**UB-tree**
**Use space filling curves to map high-dimensional data to one-dimension**
**One range query is mapped into many many queries on the B-tree based index**
**Even sequential scan**
**Better than B-tree and R-tree if dimension > 10**
**Simply read all data and compare ******** ****take too long**

## Another class of indexes: Bitmap index

**Example queries on the attribute, say, A**
**One-sided range query: A < 2**
**b****0**** OR b****1**
**Two-sided range query: 2<A<5**
**b****3**** OR b****4**
**Basic steps of building a bitmap index**
**Binning**
**Encoding**
**Compressing**

*Data*
*values*

*0*
*1*
*5*
*3*
*1*
*2*
*0*
*4*
*1*

*1*
*0*
*0*
*0*
*0*
*0*
*1*
*0*
*0*

*0*
*1*
*0*
*0*
*1*
*0*
*0*
*0*
*1*

*0*
*0*
*0*
*0*
*0*
*1*
*0*
*0*
*0*

*0*
*0*
*0*
*1*
*0*
*0*
*0*
*0*
*0*

*0*
*0*
*0*
*0*
*0*
*0*
*0*
*1*
*0*

*0*
*0*
*1*
*0*
*0*
*0*
*0*
*0*
*0*

*=0*

*=1*

*=2*

*=3*

*=4*

*=5*

*b**0*

*b**1*

*b**2*

*b**3*

*b**4*

*b**5*

## How many bins?

- More bins
- Less objects in edge bins

## How to encode

**Notes:**
Using the same example with 6 distinct values

## Advantages of bitmap indices

**Fast operations**
**The most common operations are the bitwise logical operations**
**They are well supported by hardware**
**Easy to compress, potentially small index size**
**Each individual bitmap is small and frequently used ones can be cached in memory**
**Efficient for read-mostly data: data produced from scientific experiments can be appended in large groups**
**Available in most major commercial DBMS**

## Why our own bitmap index

**Early tests shown that we can do an order of magnitude better than ORACLE (using equality encoding)**
**Vertical partition: allows one to only read data of the attributes involved in a query**
**New compression method**
**Best known: Byte-aligned Bitmap Code (BBC)**
**Developed 2 Word-Aligned Schemes: WAH, WBC**
**Different encoding schemes under compression**
**Equality encoding – used in ORACLE and others**
**Range encoding – one-sided range queries**
**Interval encoding – two-sided range queries**

## Information about the test machines

**Hardware and system**
**Sun enterprise 450 (Ultrasparc II 400MHz)**
**4GB RAM**
**VARITAS volume manager (stripped disk)**
**Real application data from STAR**
**Above 2 million objects**
**Picked 12 attributes with varying distributions **
**Measures:**
**Logical operation time without IO**
**Logical operation time with IO**
**Query processing time**

## Logical operation time (no IO)

**Logical operation time (no IO)**

**Notes:**
Logical operation (on in-core bit vectors) times only

## Logical operation time (including IO)

**Logical operation time (including IO)**

**Notes:**
Total time = logical operation time + time to read two operands from disk

This is the maximum time because the actual DBMS is likely to retain the operands in memory as long as it can – the IO time should be amortized among the logical operations.

WAH, WBC and BBC use the same amount of when the files are very small, i.e., when the compression ratios are extreme low.  The actual time is about 0.0002 sec which is the overhead of the IO operations.

## New compression schemes

**Overall, use about 50% more space than BBC**
**On average, 12 times faster than BBC**
**Faster than the uncompressed in more cases:**
**New schemes are faster than the uncompressed scheme when the compression ratios are less than 0.3**
**BBC is faster than the uncompressed when the compression ratios are less than 0.03**

## Sizes of bitmap indices 

**Sizes of bitmap indices **

**Conclusion:**
** ****equality encoding is most space efficient**
** ****Compression gain is at least a factor of 2.5**

**Notes:**
WAH compresses reasonably well

## Average query processing time

**Average query processing time**

**Conclusion:**
** ****interval and range encoding are the best**
** ****For these cases, there is practically no penalty to compression**

**Notes:**
In most cases, the compressed versions of the different indexing schemes are just as fast as their uncompressed versions.
All bitmap indexing schemes run much faster than the sequential scan – a sanity check.
The uncompressed equality encoded index is faster than the compressed version because the compressed version generates and delete a large number of temporary bit vectors during operations – this extra cost can be avoided in this particular case.

## Interval encoding is better overall

- Sequential scan time: 0.557 sec

**Notes:**
Compressed Interval scheme uses 40% space compared to the uncompressed (U I)
It runs at about the same space given the same number of bins
If using the same amount of space, the compressed one is faster because there are less events to be scanned in the final filtering step

## Summary

**Better compression scheme**
**50% more space, but 10-12 time faster !!!**
**Among the different encoding schemes**
**the interval encoding is the better than the equality encoding and the range encoding**
**Selecting the number of bins => Bitmap index size and operation efficiency.  For example:**
**10% of data size => 3 x speed of sequential scan**
**20% of data size => 6 x speed of sequential scan**
**Equality encoding currently used in the STAR experiment.  Next version will include the interval encoding.**

## Future work

**Support NULL value and categorical values**
**On-line update: add new data and update index without interrupting request processing**
**Recovery mechanism for robustness**
**Potential new applications: climate, astrophysics, biology**
**Study different non-uniform binning strategies**
**Integrate with conventional database system: to better handle metadata, to provide more versatile front-end**