# Presentation: 250324

## Searching TechnologyFor a Large Number Of Objects

**Kurt Stockinger and John Wu**
- Lawrence Berkeley National Laboratory

## Outline

**Current work**
**FastBit: a compressed bitmap indexing package**
**Applications:**
**Grid Collector**
**DEX**
**TBitmapIndex**
**Network Flow Data Analysis**
**Future Plans**
**Extending the searching technology**
**Integrating with other SDM center technologies**

- SDM All-hands, October 2005

## FastBit

**A compressed bitmap indexing technology for efficient searching of read-only data**
**John Wu, Ekow Otoo, Arie Shoshani**
**Kurt Stockinger, Doron Rotem**
_**[http://sdm.lbl.gov/fastbit](http://sdm.lbl.gov/fastbit)**_

**Notes:**
Don’t say anything about URL

## FastBit Overview

**FastBit is designed to search multi-dimensional data**
**Conceptually in table format**
**rows ******** objects**
**columns ******** attributes**
**FastBit uses vertical (column-oriented) organization for the data**
**Efficient for analysis of read-only data**
**FastBit uses **_**compressed bitmap indices**_** to speed up searches**
**Proven**** in analysis to be ****optimal**** for single-attribute queries**
**Superior**** to other optimal indices because they are also efficient for multi-attribute queries**

|  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- |
|  |  |  |  |  |  |
|  |  |  |  |  |  |
|  |  |  |  |  |  |
|  |  |  |  |  |  |
|  |  |  |  |  |  |
|  |  |  |  |  |  |
|  |  |  |  |  |  |
|  |  |  |  |  |  |
|  |  |  |  |  |  |
|  |  |  |  |  |  |
|  |  |  |  |  |  |

**row**

**column**

- SDM All-hands, October 2005

**Notes:**
Vertical organization examples: Kdb (1998), C-store (2005)

## Grid Collector

**Put FastBit and SRM together to improve the efficiency of STAR analysis jobs**
**John Wu, Junmin Gu, Jerome Lauret, Arthur M. Poskanzer, Arie Shoshani, Alexander Sim,**
**Wei-Ming Zhang**
_**[http://www.star.bnl.gov/](http://www.star.bnl.gov/STAR/comp/train/tut/GC/GridCollector.htm)**_

**Notes:**
Don’t say anything about URL

## Grid Collector Features

- Key features of the Grid Collector:
- Providing transparent object access
- Selecting objects based on their attribute values
- Improving analysis system’s throughput
- Enabling interactive distributed data analysis

- SDM All-hands, October 2005

**Notes:**
Here is what we get when they work together.

Refer to the picture first: (logical request, bitmap index, hrm, files back into cache, event iterator deliver the event to the analysis code)
Then say, this provides: (the point on the top)

## Grid Collector Speeds up Analyses

**Legend**
**Selectivity: fraction of events needed by the analysis**
**Speedup = ratio of time to read events without GC and with GC**
**Speedup = 1: speed of the existing system (without GC)**
**Results**
**When searching for rare events, say, selecting one event out of 1000 (selectivity = 0.001), using GC is 20 to 50 times faster**
**Even using GC to read 1/2 of events, speedup > 1.5**

- SDM All-hands, October 2005

**Notes:**
Speeding up scientific discovery!

1 == the base line, read all the data

Left plot in log-log scale, right plot in linear scale (both axes) to emphasis the behavior of selectivity > 0.1.

Three runs, 10,000 to 40,000 events (production P04ie, trigger setup name production62GeV). 

Machine name pdsfgrid5 (data located on /auto/pdsfdv65), read speed measured with ‘/usr/bin/time /bin/cat ... > /dev/null’.  
The speed of reading all events on pdsfgrid5 is about 26 events / second.

Previous tests on (the old) stargrid01 can read about 10 events / second.  Previous test used a set of data with production P04id and trigger setup name emcPed.  From physics view, that was simple test data and Production62GeV data is more appropriate for testing purposes.

## DEX: Using Efficient Bitmap Indices to Accelerate Scientific Visualization

**Kurt Stockinger, John Shalf, Wes Bethel, John Wu **
**Computational Research Division**
**Lawrence Berkeley National Laboratory**
**Berkeley, California**

## DEX: Dexterous Data Explorer

- Data

- Query

- Visualization Toolkit(VTK)

- 3D visualization of a
- Supernova explosion

- SDM All-hands, October 2005

## Performance Results with Scientific Data

- One of the simplest tasks DEX performs is to find isosurface
- DEX is on average a factor of three to four faster than the best isosurface algorithm of VTK.

- VTK rendering time: 0.2 – 2 seconds.

- SDM All-hands, October 2005

## Query-Driven Visualization of Combustion Data Set

- b) Q: temp < 3

- c) Q: CH4 > 0.3 AND          temp < 3

- d) Q: CH4 > 0.3 AND          temp < 4

- a) Query: CH4 > 0.3

- SDM All-hands, October 2005

## TBitmapIndex: An attempt to introduce FastBit to ROOT 

**Kurt Stockinger****1****, John Wu****1****, Rene Brun****2****, Philippe Canal****3**
**(1) Berkeley Lab, Berkeley, USA**
**(2) CERN, Geneva, Switzerland**
**(3) Fermi Lab, Batavia, USA **

## Current Status

**Built a prototype wrapper on FastBit called TBitmapIndex**
**Read one variable at a time into memory to build index**
**Each Index**** is currently stored in a binary file**
**Integrated bitmap indices to ****support****:**
**TTree::Draw**
**TTree::Chain**
**Verified the performance advantage of FastBit vs. ROOT’s TTreeFormula**

- SDM All-hands, October 2005

## Experiments With BaBar Data

**Software/Hardware:**
**Bitmap Index Software is implemented in C++**
**Tests carried out on:**
**Linux CentOS**
**2.8 GHz Intel Pentium 4 with 1 GB RAM**
**Hardware RAID with SCSI disk**
**Data:**
**7.6 million records**** with ~****100 attributes**** each**
**Babar**** data set:**
**Bitmap Indices (FastBit):**
**10 ****out of ~100**** attributes**
**1000 equality-encoded bins**
**100 range-encoded bins**

- SDM All-hands, October 2005

## Size of Compressed Bitmap Indices

- SDM All-hands, October 2005

## Query Performance - TTreeFormula vs. Bitmap Indices

**Bitmap indices 10X faster than TTreeFormula**

- SDM All-hands, October 2005

## An Application of TBitmapIndex-- Network Flow Data Analysis

**Kurt Stockinger, John Wu, Scott Campbell, Stephen Lau, Mike Fisk, Eugene Gavrilov, Alex Kent, Christopher E. Davis, Rick Olinger, Rob Young, Jim Prewett, Paul Weber, Thomas P. Caudell, E. Wes Bethel, Steve Smith**
**LBNL, LANL, UNM**

## Chasing the Track of a Network Scan

**IDS log shows**
**Jul 28 17:19:56 AddressScan 221.207.14.164 has scanned 19 hosts (62320/tcp)**
**Jul 28 19:19:56 AddressScan 221.207.14.88 has scanned 19 hosts (62320/tcp)**
**Using FastBit/ROOT to explore what else might be going on**
**Queries prepared by Scott Campbell.  More details at **_**[http://www.nersc.gov/~scottc/papers/ROOT/rootuse.prod.html](http://www.nersc.gov/~scottc/papers/ROOT/rootuse.prod.html)**_

- SDM All-hands, October 2005

## Are There More Scans?

**Query: select ts/(60*60*24)-12843, IPR_C, IPR_D where IPS_A=211 and IPS_B=207**
**More scans from the same subnet**

- SDM All-hands, October 2005

## Who Is Doing It?

**Query: select IPS_C, IPS_D where IPS_A==211 and IPS_B==207**
**Picture: the histogram of the IPS_C and IPS_D**
**Five IP addresses started most of the scans!**

- SDM All-hands, October 2005

## Future Plans

**Meet the challenges of searching in data intensive sciences**

## Types of Searching Problems

**Not practical to work on many terabytes of data simultaneously ******** work on a ****subset**** instead**
**Analyze the data collected last month**
**Analyze the data collected by Joe**
**Find**** the objects of interest**
**Find the flame front in combustion simulation**
**Find the top-talker in network communication**
**Knowledge ****discovery**
**Association rules**
**Cliques/connection subgraphs**

- SDM All-hands, October 2005

## Searching Problems From SciDAC2 Appendix

| B.1 Experimental Combustion Science | Feature identification and tracking | 20TB |
| --- | --- | --- |
| B.8 Empowering RHIC users with new analysis tools | Analyze subsets | ~GB/s |
| B.10 U.S. LHC Experiments | Analyze subsets | ~GB/s |
| B.13 The Solenoid Tracker at RHIC (STAR) | Analyze subsets | 1GB/s |
| B.2 Advanced Computing for LCLS | ?, classification | 200 MB/s |
| B.3 An Earth Science Knowledge System | Locating dataset of interest | PB |
| B.5 Enabling Discovery in Experimental Biological Science | High-dimensional data search, data versioning, semantic graphs (ontology), multiple sources |  |

- SDM All-hands, October 2005

## Searching Problems From SciDAC2 Appendix

| B.4 Remote operations of LHC, CMS and ITER | Streaming data |  |
| --- | --- | --- |
| B.9 ARM/ACRF Program | Instrument data streams |  |
| B.6 Enhancing Material Science Beamline | ND data array, real-time processing | 1GB/h ? |
| B.7 Large-Scale Computation for ITER | Data management |  |
| B.11 Nanoscience | Mining simulation data together with experimental data |  |
| B.12 The Spallation Neutron Source | Real-time image analysis, data comparison | 20MB/s |

- SDM All-hands, October 2005

## Features of These Search Problems

**Large****: many datasets are petabytes in size, billions records**
**Complex data****: multi-dimensional arrays, user-defined data types, mixed simulation data with experimental data, regular data with attribute defined with ontologies (semantic networks)**
**Complex searching****: data versioning, provenance-based search, catalog matching**
**Beyond searching****: data mining and knowledge discovery**
**Real-time response****: instrument control, interactive designed of experiments, computational steering**
**Integrated****: searching is only a part of the overall data analysis, need to improve the overall throughput**

- SDM All-hands, October 2005

## Improve Existing Searching Tools

**FastBit is efficient for range queries; need to support other types of queries, e.g., ****joins**
**FastBit is efficient for read-only data; need to support ****update**
**FastBit supports up to 2****32**** (4 billion) records; need to support at least ****2****64**** (16 quintillion) records**
**FastBit allows the user to choose from many different type of indices; need to automatically decide one for the user**

- SDM All-hands, October 2005

## Expand The Repertoire Of Searching Tools

**Support parallel index building and searching**
**Support search of semantic networks, combining ontology with structured data**
**Support data versioning (time stamps, provenance, ...)**
**Support robust recovery (a la POSTGRES)**
**Support user-defined data types (ROOT)**
**Support user-defined functions**
**Support commonly used B-trees and R-trees**
**Support combined searching of structured and semi-structured data, extend**

- SDM All-hands, October 2005

## Extend The Accessibility Of The Tools

**Extend the collaboration with ROOT to make FastBit seamlessly available to users**
**Implemented a prototype, need a more integrated way to read and write ROOT files**
**Read data from other common file formats; write indices to the same file formats**
**netCDF, HDF (4/5)**
**Extend the advantage of searching to other steps of analysis**
**Feature tracking; extending it to higher dimension; more general image analysis**
**Make FastBit available in other forms**
**Web service, an actor in Kepler, ...**

- SDM All-hands, October 2005

## Summary

**FastBit is efficient for range queries on read-only data**
**Integration of FastBit with ROOT is getting underway**
**TBitmapIndex prototype**
**Integration with other systems possible**
**Need to develop a short list based on target application area**
**Plan to extend FastBit**
**Integration with ROOT will bring up a list of requirements**
**Intend to target biological applications**

- SDM All-hands, October 2005