Non-relational databases are the common means of data storage in the Cloud, and optimizing the data access is of paramount importance into determining the overall Cloud system performance. In this paper, we present GAIA, a novel model for retrieving and managing correlated geo-localized data in the cloud environment. We survey and compare the existing models used mostly in Geographical Information Systems (GIS), mainly the Grid model and the Coordinates Projection model. Besides, we present a benchmark comparing the efficiency of the models. Using extensive experimentation, we show that GAIA outperforms the existing models by its high efficiency which is of O(log(n)), and this mainly thanks to its combination of projection with cell decomposition. The other models have a linear efficiency of O(n). The presented model is designed from the ground up to support GIS and is designed to suit both cloud and parallel computing.