Saving these locations with the name of the locations(Title + latitude and longitude) in the app takes quite a lot of space. How can I reduce the size of the app? Any suggestions would make me greatful.

And also this will probably slow down the performance of the app, any suggestions considering that?

EDIT1:
It just hit me that if I save everything on an online server and query that for "tiles of annotations" just as google map does that might be the solution. So my question now is: Does anyone know a good algorithm for querying for "tiles of annotations"? This might be quite tricky since the map contains of several zoomLevels etc.
For starters, I will probably create several quadtrees(one for each zoomLevel) where I store which tiles that I already have queried for.

Do you guys think that this approach might be good? Or will it be too slow to run on 3G?

Thanks in advance.