$ Omega $ -storage : a self organizing multi-attribute storage technique for very large main memories
Jonas Karlsson, Martin L. Kersten · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1999
Main memory is continuously improving both in price and capacity. With this comes new storage problems as well as new directions of usage. Just before the millennium, several main memory database systems are becoming commercially available. The hot areas include boosting the performance of web-enabled systems, such as search-engines, and auctioning systems. We present a novel data storage structure -- the# -storage structure, a high performance data structure, allowing automatically indexed storage of very large amounts of multi-attribute data. The experiments show excellent performance for point retrieval, and highly e#cient 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 e#ective assignment bits of attributes. Moreover, it avoids the sensitivity of the kd-tree to insert orders. 1991 ACM Computing Classification System: D.4.2 : Storage Management -- Main Memor...