1. A method for partitioning a set of data records having a plurality of ranges to which a plurality of queries for specific ranges can be applied, the method comprising: at least one or more processors, transforming a plurality of current data records, which each has a start time and an end time, into a two dimensional (2D) space having a first dimension upon which each data record's start time is mapped and a second dimension upon which each data record's end time is mapped; at the at least one or more processors, obtaining a plurality of historical queries that each specifies a data range, a response being previously sent for each historical query and specifying a sub-portion of the current data records that overlap with such historical query's specified data range; at the at least one or more processors, generating a plurality of partitioning schemes for the current data records in the 2D space; at the at least one or more processors, selecting an optimum one of the partitioning schemes based on a cost of executing the historical queries with respect to each of the partitioning schemes, wherein the optimum partitioning scheme has a lowest cost of the partitioning schemes; and at the at least one or more processors, applying the optimum partitioning scheme on the current data records, including newly received data records, in the 2D space so that any subsequently received queries are applied against the current data records as partitioned by the optimum partitioning scheme in the 2D space.