Запоминать уже загруженные области

[xcoder]

Привет.

Мне кажется тема должна была где-то обсуждаться, но поиском ничего не нашел.

Я пишу приложение для мобильного устройства, которое с помощью некоторого API получает с сервера географические координаты объектов, ближайших к пользователю и отображает их на карте. (при этом пользователь может двигаться и информация подгружается по мере передвижения пользователя)

Информация об объектах кэшируется локально на устройстве в базе sqlite, так как запросы к api могут идти по медленному edge или gprs каналу.

Подскажите пожалуйста, как можно было бы запоминать области, для которых объекты уже загружены в базу? Чтобы, допустим, если пользователь ездит каждый день по одному и тому же маршруту, не грузить каждый раз объекты заново.

У меня есть две идеи:
1) После API запроса cохранять области в виде пар точек (левая-верх, правая-низ) в базу и перед другим API-запросом к серверу проверять, нет ли уже этой области в базе, или области которая покрывала бы эту новую область. Если есть - загружаем объекты из базы.

Сложность в том, что пользователь передвигается. Даже если кэшировать в базу области "с запасом" (отображаем, например, объекты в радиусе 5 километров, а загружаем с сервера область в 10 километров), и делать запросы когда пользователь переместится так, что "запас" кончится - то в базе все равно будет куча областей которые частично пересекаются, а чем больше областей в базе - тем (как мне кажется) больше ресурсов требуется на обработку запроса к БД.

2) Опираться на среднее количество объектов для области. То есть если для 10 предидущих загруженных областей в среднем было 5 объектов, то если для текущей области есть в локальной базе 5 объектов - отображаем их и не делаем запрос к API.

Этот вариант мне вобще не нравится, так как важно, чтобы пользователь видел все объекты вокруг него. Понятно, что при втором подходе довольно большая часть объектов не будет загружена.

Я склоняюсь к первому варианту, но меня терзают сомнения. Проблема еще в том, что приложение будет использоваться только интерактивно - пользователь идет/едет - запускает приложение, пришел/приехал - приложение отключил. Так бы во время простоя, когда нет необходимости грузить/показывать близлежащие объекты, можно было бы суммировать соседние/частично покрывающиеся области, подгружать недостающие объекты из получившихся областей.

Есть ли что - нибудь что я упускаю? Как лучше реализовать эту задачу, учитывая мобильность устройства и ограниченность системных ресурсов.

[ericsson]

Кэшировать надо не просто точки, т.к. это не даст абсолютно ничего. Нужно кэшировать запросы и их результаты.
Пространство должно быть, например, поделено заранее на клетки-сектора, которые запрашиваются, если пользователь при движении приближается к их границам. Соответственно, так и запрос будет короче (индексный номер сектора вычисляется на стороне клиента и передается вместо координат) и проверять на стороне клиента, есть ли в кэше ответ на такой запрос, будет возможно. Ну а далее вступают в силу традиционные алгоритмы обслуживания кэша. Плюс, можно добавить более хитрые условия предвыборки, если они придут в голову.

[xcoder]

Кэшировать надо не просто точки, т.к. это не даст абсолютно ничего. Нужно кэшировать запросы и их результаты.
Пространство должно быть, например, поделено заранее на клетки-сектора, которые запрашиваются, если пользователь при движении приближается к их границам. Соответственно, так и запрос будет короче (индексный номер сектора вычисляется на стороне клиента и передается вместо координат) и проверять на стороне клиента, есть ли в кэше ответ на такой запрос, будет возможно. Ну а далее вступают в силу традиционные алгоритмы обслуживания кэша. Плюс, можно добавить более хитрые условия предвыборки, если они придут в голову.

Спасибо за ответ.

API используются сторонние, то есть что-то в них изменить я, к сожалению, не могу. На той стороне просто скрипт, который принимает области в виде двух крайних точек: /api.php?minlat=A&minlon=B&maxlat=C&maxlon=D
и возвращает некоторый XML, в котором кроме точек и нужных данных о них (название, адрес) содержатся еще лишние данные.

В принципе я думаю над тем, чтобы в будущем сделать своеобразный прокси, который делал бы запросы к стороннему АПИ, выбирал только нужные данные и отправлял бы в более удобной форме на устройства, но это, скорее всего, только в будущем.

Насчет заранее приготовленных клеток-секторов очень интересная идея. Даже при нынешнем API это бы серьезно упростило задачу. Что можно почитать по этому поводу? Есть ли готовое описание какого-нибудь быстрого алгоритма, позволяющего вычислять индекс для клетки в которой находится (и/или к которой приближается) пользователь (имея текущие георгафические координаты пользователя) и в другую сторону - имея индекс клетки вычислять ее минимальные/максимальные географические координаты (для запроса к существующему API).

Мне кажется тогда можно было бы действовать по алгоритму вроде: "мы находимся в клетке Х, данные для нее есть в базе, загружаем из базы все объекты у которых указана клетка Х в качестве расположения и размещаем их на карте в соответствии с координатами". Или "мы находимся в клетке Х, данных для нее нет(или загружены более трех дней назад), конвертируем индекс клетки в координаты и делаем запрос к АПИ, сохраняем полученные данные в базу, дописывая в отдельное поле, что объект находится в клетке с индексом Х". Правильно ли я мыслю?

[ericsson]

Подборка размера клетки и способ их кодирования - это уже вопрос конкретной реализации, не думаю, чтобы готовые примеры с пояснениями уже были. Простейший способ такого индекса - это просто координаты одного из углов ячейки, указанные с ограниченной точностью (скажем, при ячейке минута на минуту - с точностью до единиц минут).

Единственное - если ваше "стороннее api" работает с географическими координатами (которые в градусах), то создание условной сетки на ее основе будет связано с изменением истинной площади ячеек с севера на юг. Хотя если проект - городского масштаба, то это не важно (слишком мала протяженность с севера на юг).
Алгоритм описан правильно, единственное - стоит еще предусмотреть сбор статистики по обращениям к клеткам, чтобы при приближении к лимиту объема кэша выкидывать те ячейки, которые запрашивались или должны были запрашиваться наименьшее число раз и максимально давно.

[xcoder]

Подборка размера клетки и способ их кодирования - это уже вопрос конкретной реализации, не думаю, чтобы готовые примеры с пояснениями уже были. Простейший способ такого индекса - это просто координаты одного из углов ячейки, указанные с ограниченной точностью (скажем, при ячейке минута на минуту - с точностью до единиц минут).

У меня все координаты в виде десятичных дробей с точностью до стотысячных, но кажется я понял что я должен делать

Если я буду индексировать ячейки по левому нижнему углу (мне кажется так проще всего), а размер ячейки возьму как,например, 0,2 градуса, то мне кажется что индексы получится считать так:

Индекс по координатам = координату разделить на 0.2 и округлить вниз до ближайшего целого.
Координаты угла ячейки по индексу = индекс умножить на 0.2

Единственное - если ваше "стороннее api" работает с географическими координатами (которые в градусах), то создание условной сетки на ее основе будет связано с изменением истинной площади ячеек с севера на юг. Хотя если проект - городского масштаба, то это не важно (слишком мала протяженность с севера на юг).

Проект глобальный, но мне кажется эту проблему можно довольно просто обойти - например, чем севернее/южнее точка, в которой находится пользователь, тем больше близлежащих ячеек скачивать в кэш. То есть, например, если широта 0 градусов, то скачиваем одну ячейку, если 40, то две-три близлежащие итд.

Алгоритм описан правильно, единственное - стоит еще предусмотреть сбор статистики по обращениям к клеткам, чтобы при приближении к лимиту объема кэша выкидывать те ячейки, которые запрашивались или должны были запрашиваться наименьшее число раз и максимально давно.

Хмм, это хорошая мысль, спасибо, возьму на заметку.