Omega-storage: A Self Organizing Muli-attribute Storage Technique for Very Large Main Memories

Main memory storage is continuously improving, both in its price and its capacity. With this comes new storage problems and new directions of possible usage. Just before the millennium, several main memory database systems are becoming commercially available. The hot areas for their deployment include boosting the performance of web-enabled systems, such as search-engines, and electronic auctioning systems. We present a novel data storage structure -- the Omega-storage structure, a high performance data structure, to index very large amounts of multi-attribute data. The experiments show excellent performance for point retrieval, and highly efficient pruning for pattern searches. It provides the balanced storage previously achieved by random kd-trees, but avoids their increased pattern match search times, by an effective assignment bits of attributes to index. Moreover, it avoids the sensitivity of the kd-tree to insert orders.