Most of the framework for supporting OLAP operations over immense amounts of spatio-temporal data is based on multi-tree structures. The multi-tree frameworks, however, are hardly applicable to spatio-temporal OLAP in practice, due mainly to high management costs and low query efficiency. To overcome the limitations of such multi-tree frameworks, we propose a new approach called ST-Cube (spatio-temporal cube), which is an adaptive cell-based, total-ordered and prefix-summed cube for spatio-temporal data warehouses. Our extensive performance studies show that the ST-Cube requires less space and achieves higher query performance than multi-tree frameworks, under various operational conditions.