Abstract
This paper initiates a new study on online partitioning algorithms that are sequentially optimized for a query sequence. As queries arrive one at a time, given the option to reconfigure the partition after each query so that it can best serve the next query, the objective is to minimize the query read cost and data migration cost. This is an online problem without an optimal solution; online heuristics are the only resort. We investigate this problem by formulating it as a multi-objective optimization and proposing an Evolutionary Algorithms (EA) framework incorporating several online heuristics to explore Pareto-optimal solutions. This study is driven by our conjecture that if an online heuristic helps EA converge faster to better partitioning solutions then practically this heuristic should be preferred for adapting the partition to the query sequence.