Abstracto

Integrating Run Length Encoding and Column oriented database execution using Binary Search Tree

Akhil Ramachandran, Anu Krishna Rajamohan

Column oriented databases have attracted significant amount of attention recently and database systems based on Column oriented technology are used extensively for analytical processing such as those found in data warehouses, decision support, and business intelligence and forecasting applications. Column oriented databases have enormous potential for data compression because of the similarity of adjacent records. This paper will discuss an algorithm that makes use of this similarity in a column oriented databases to integrate the compression and execution processes. It proposes a new indexing method called Binary Search Tree (BST) indexing that supports O (log n) insertion, deletion and look-up operations. Additionally, the paper also describes the implementation of these basic operations.