Ω-storage: a self organizing multi-attribute storage technique for very large main memories
Jonas Karlsson, Martin L. Kersten · 2002
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. Several main-memory database systems are now 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 /spl 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 of attribute bits to the index. Moreover, it avoids the sensitivity of the kd-tree to the insertion order.