Digital Symposium Collection 2000  

 
 
 
 
 
 

 



















A Novel Index Supporting High Volume Data Warehouse Insertion

Chris Jermaine, Anindya Datta, and Edward Omiecinski

  View Paper (PDF)  

Return to Data Mining & Pattern Extraction

Abstract
While the desire to support fast, ad hoc query processing for large data warehouses has motivated the recent introduction of many new indexing structures, with a few notable exceptions (namely, the LSM-Tree [4] and the Stepped Merge Method [1]) little attention has been given to developing new indexing schemes that allow fast insertions. Since additions to a large warehouse may number in the millions per day, indices that require a disk seek (or even a significant fraction of a seek) per insertion are not acceptable.

In this paper, we offer an alternative to the B+-tree called the Y-tree for indexing huge warehouses having frequent insertions. The Y-tree is a new indexing structure supporting both point and range queries over a single attribute, with retrieval performance comparable to the B+-tree. For processing insertions, however, the Y-tree may exhibit a speedup of 100 times over batched insertions into a B+-tree.


References

Note: References link to DBLP on the Web.

[1]
H. V. Jagadish , P. P. S. Narayan , S. Seshadri , S. Sudarshan , Rama Kanneganti : Incremental Organization for Data Recording and Warehousing. VLDB 1997 : 16-25
[2]
...
[3]
...
[4]
Patrick E. O'Neil , Edward Cheng , Dieter Gawlick , Elizabeth J. O'Neil : The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica 33(4) : 351-385(1996)
[5]
Patrick E. O'Neil , Dallan Quass : Improved Query Performance with Variant Indexes. SIGMOD Conference 1997 : 38-49
[6]
Kerttu Pollari-Malmi , Eljas Soisalon-Soininen , Tatu Ylönen : Concurrency Control in B-Trees with Batch Updates. TKDE 8(6) : 975-984(1996)
[7]
Mendel Rosenblum , John K. Ousterhout : The Design and Implementation of a Log-Structured File System. TOCS 10(1) : 26-52(1992)
[8]
Betty Salzberg : Access Methods. Computing Surveys 28(1) : 117-120(1996)

Referenced by

  1. H. V. Jagadish : Review - A Novel Index Supporting High Volume Data Warehouse Insertion. ACM SIGMOD Digital Review 1 : (1999)

BIBTEX

@inproceedings{DBLP:conf/vldb/JermaineDO99,
  author    = {Chris Jermaine and
                Anindya Datta and
                Edward Omiecinski},
   editor    = {Malcolm P. Atkinson and
                Maria E. Orlowska and
                Patrick Valduriez and
                Stanley B. Zdonik and
                Michael L. Brodie},
   title     = {A Novel Index Supporting High Volume Data Warehouse Insertion},
   booktitle = {VLDB'99, Proceedings of 25th International Conference on Very
                Large Data Bases, September 7-10, 1999, Edinburgh, Scotland,
                UK},
   publisher = {Morgan Kaufmann},
   year      = {1999},
   isbn      = {1-55860-615-5},
   pages     = {235-246},
   crossref  = {DBLP:conf/vldb/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM