  A key problem in location-based modeling and forecasting lies in identifying
suitable spatial and temporal resolutions. In particular, judicious spatial
partitioning can play a significant role in enhancing the performance of
location-based forecasting models. In this work, we investigate two widely used
tessellation strategies for partitioning city space, in the context of
real-time taxi demand forecasting. Our study compares (i) Geohash tessellation,
and (ii) Voronoi tessellation, using two distinct taxi demand datasets, over
multiple time scales. For the purpose of comparison, we employ classical
time-series tools to model the spatio-temporal demand. Our study finds that the
performance of each tessellation strategy is highly dependent on the city
geography, spatial distribution of the data, and the time of the day, and that
neither strategy is found to perform optimally across the forecast horizon. We
propose a hybrid tessellation algorithm that picks the best tessellation
strategy at each instant, based on their performance in the recent past. Our
hybrid algorithm is a non-stationary variant of the well-known HEDGE algorithm
for choosing the best advice from multiple experts. We show that the hybrid
tessellation strategy performs consistently better than either of the two
strategies across the data sets considered, at multiple time scales, and with
different performance metrics. We achieve an average accuracy of above 80% per
km^2 for both data sets considered at 60 minute aggregation levels.
