Комментарии 38
Спасибо, очень интересно.
Так какие языки сейчас используются? Питон и Джава?
Так какие языки сейчас используются? Питон и Джава?
А построить мелкую сетку в местах скопления что принципиально мешает?
Ничего не мешает, нет надобности. Мы строим тепловую карту с ячейками одинакового размера на всей исследуемой территории, и чаще всего заказы от рекламный компаний, которым нужно знать в каких местах поставить рекламный щит или билборд. Как было сказано в статье, мы используем Uber H3 9 lvl (радиус ~200м) и 10 lvl (радиус ~75м). Этих размеров вполне достаточно, для такого рода исследований.
Или я не понял вопроса?
Или я не понял вопроса?
Думаю не поняли. Речь о том, что описывалась одна проблема, когда в центре крупного города в ячейку попадает слишком много треков, и обработка одной ячейки становится слишком напряженной. Можно ли это решить путем адаптивной сетки в некоторых районах, которые в принципе должны быть нам известны (ну, более-менее, мы же знаем, где у нас центр например)?
Данную аномалию мы не обрабатываем с помощью сетки, но размышляем в эту степь. Ну, а что касается высокочастотных-аномальных районов, тут не обязательно центр города. К примеру, в Бангкоке обнаружено 5 таких точек, 2 из них вот:
13.7618,100.5324 — точка1
13.7877,100.5068 — точка2
И, сейчас сходу не нашел в русских городах, но помню, в Казани была аномальная точка, которая располагалась на краю города, и один сайт говорил, что это и есть центр города.
13.7618,100.5324 — точка1
13.7877,100.5068 — точка2
И, сейчас сходу не нашел в русских городах, но помню, в Казани была аномальная точка, которая располагалась на краю города, и один сайт говорил, что это и есть центр города.
Ну т.е. мы не знаем где скопления?
На неизведанной территории пока не знаем. Это становится известно после прогона датасета по алгоритмам классификации и очистки. И уже в последнюю очередь мы смотрим аномальные высокочастотные точки. До недавних пор мы с этим не сталкивались, пока не начали сотрудничество с новым поставщиком данных. Они в свою очередь обещали тоже с этим разобраться.
Подозреваю, что это какой-то перекресток путей. Ну т.е. условно, если у вас в городе есть река — то аномальные точки всегда будут возле мостов, потому что летать и плавать большинство не умеет. Точно такую же роль будут играть железные дороги, магистрали типа 3 кольца в Москве, пересечь которые можно в отдельных точках, и т.п. Скажем, когда вы строите изохроны в городе, то пешеходные переходы через шоссе проявляются очень ярко.
Вычислить их заранее конечно задача неочевидная. Хотя возможно, если построить граф маршрутов, на нем они будут как-то ярко выражены.
Вычислить их заранее конечно задача неочевидная. Хотя возможно, если построить граф маршрутов, на нем они будут как-то ярко выражены.
Если бы. Часто просто скопление в чистом поле. Больше кажется что точки падают в default location, который возвращает SDK для административной единицы при невозможности взять точные координаты.
Ну, я бы наверное сказал, что это вариант номер 1… если бы у вас было геокодирование :) Но у вас его нет, а с SDK я не работал, и такая ассоциация у меня не сложилась.
На самом деле, одной из серьезных для нас проблем с геокодированием было то, что скажем ArcGIS не сомневаясь возвращает показатель score= 100%, если нашел улицу или номер дома — даже если не нашел при этом явно указанный населенный пункт. Т.е. мы получаем ответ — и не можем просто сказать по нему, что из адреса он нашел, а что — нет. Ну и в конечном счете — куча точек, попавших в центр населенного пункта.
На самом деле, одной из серьезных для нас проблем с геокодированием было то, что скажем ArcGIS не сомневаясь возвращает показатель score= 100%, если нашел улицу или номер дома — даже если не нашел при этом явно указанный населенный пункт. Т.е. мы получаем ответ — и не можем просто сказать по нему, что из адреса он нашел, а что — нет. Ну и в конечном счете — куча точек, попавших в центр населенного пункта.
В каком смысле «у нас его нет»?
Мы закупаем данные с координатами, а способ, которым они получены — SDK, показывающие рекламу и виджеты карт на устройствах пользователей. И каким образом чужой SDK получает локацию, зависит только от этого SDK. Ну и от того, что ему позволяют забрать ось и LBS на устройстве. LBS вполне может юзать и геокодинг, почему нет.
Мы закупаем данные с координатами, а способ, которым они получены — SDK, показывающие рекламу и виджеты карт на устройствах пользователей. И каким образом чужой SDK получает локацию, зависит только от этого SDK. Ну и от того, что ему позволяют забрать ось и LBS на устройстве. LBS вполне может юзать и геокодинг, почему нет.
>В каком смысле «у нас его нет»?
В том, что вы этого процесса не описывали. То что он возможно есть где-то внутри SDK — исключать не могу конечно, но с другой стороны — я не увидел у вас нигде адресов, одни координаты. Так что не очень понятно, даже если есть — то для чего?
В том, что вы этого процесса не описывали. То что он возможно есть где-то внутри SDK — исключать не могу конечно, но с другой стороны — я не увидел у вас нигде адресов, одни координаты. Так что не очень понятно, даже если есть — то для чего?
В комменте Гены, на который вы отвечали, речь шла об аномалиях — точках, где скапливается необъяснимо огромное количество сигналов. Не просто плотных облаков (это-то нормально), а в совпадениях значений координат до последнего знака у миллионов сигналов.
Я поясню другими словами — в моем окружении геокодированием обычно все-таки называют преобразование адреса в координаты и обратно. В нашем проекте это и есть источник аномалий, причем один из главных. Как правило — на выходе куча точек в центре населенного пункта.
Тогда о чём спорим? %) По нашим прикидкам именно из-за особенностей работы LBS такие «центры населённых пунктов» и вылазят в получаемых данных.
То, что мы не работаем с адресами сами, это факт, нам не интересны адреса. Но с адресами и геокодингом, как прямым, так и обратным, могут работать поставщики, которые не раскрывают подробностей того, как они работают.
Мы им не сильно верим (и я это говорил), и юзаем кучу эвристик для избавления от подобных артефактов, и прочих аномальных данных.
То, что мы не работаем с адресами сами, это факт, нам не интересны адреса. Но с адресами и геокодингом, как прямым, так и обратным, могут работать поставщики, которые не раскрывают подробностей того, как они работают.
Мы им не сильно верим (и я это говорил), и юзаем кучу эвристик для избавления от подобных артефактов, и прочих аномальных данных.
А нельзя ли перенести данные на какое-нибудь пространственное дерево и свести задачу к сложности меньшей чем N^2?
Бешаные триллионы вычислений расстояния и сравнений с пороговой константой.Добавлю, что эта задача известна в других областях как collision detection, имеет несколько эффективных решений. Вы предлагаете брутфорсить задачу, что не всегда оправданно, если датасеты имеют средний размер, как в примере. Альтернативные (более эффективные) решения — это quad trees, grid-based, sweep and prune, range trees, streaming segment tree и прочие. Эти альтернативы дают асимптотику примерно N*log(N) с разной константой, вместо N^2 или N*M (что то же самое) из вашего примера. В результате никаких «триллионов» вычислений не требуется и не нужен не то что Hadoop, а даже смартфона хватит.
Ну как бы quad trees прямо тут и упоминались же, нет?
прошу прощения, когда увидел, что предлагается решать столь вычислительно простую задачу с помощью Hadoop и прочих вариантов распределенных вычислений, не стал внимательно дочитывать. Исправлюсь.
к ни партиционируй по геометрии (хоть по Вороному, хоть quadtree), всё равно будут полигоны, где количество сравнений превышает разумные рамкичувствительность к плотности — это слабость grid-based. Деревья как раз и предназначены для того, что бы обходить эту проблему, ведь глубина веток автоматически подстраивается под плотность.
Чтобы подстроиться под плотность, надо сначала вычислить плотность.
Сейчас у нас реализован вариант с виртуальной сеткой, в котором этой проблемы вообще нет, и партиционирование равномерное.
Сейчас у нас реализован вариант с виртуальной сеткой, в котором этой проблемы вообще нет, и партиционирование равномерное.
Как обошли проблему? Quad-tree и R-trees вычисляют плотность «на ходу», подобно тому, как действует сортировка бинарным деревом.
Неизящно. Не могу рассказать в подробностях, потому что это часть патентованной эвристики :/
Без иллюстраций тут довольно сложно вообще объяснить, что не так с плотностью. Основной затык в том, что множеств точек два (сигналы и пои), и они независимые, поэтому независимое партиционирование по одному из них никак не уменьшает количество точек, которые попадают в парт из другого. А если партиционировать оба, это даст декартово произведение уже в количестве партов.
Может быть, мне стоит запилить отдельную статью с картинками по этому вопросу чуть позже.
Без иллюстраций тут довольно сложно вообще объяснить, что не так с плотностью. Основной затык в том, что множеств точек два (сигналы и пои), и они независимые, поэтому независимое партиционирование по одному из них никак не уменьшает количество точек, которые попадают в парт из другого. А если партиционировать оба, это даст декартово произведение уже в количестве партов.
Может быть, мне стоит запилить отдельную статью с картинками по этому вопросу чуть позже.
Я правильно понимаю, что это стандартная проблема bipartite collision detection? В игровых движках такое для снарядов используют.
если партиционировать оба, это даст декартово произведение уже в количестве партов.Почему декартово? В худшем случае же O((N+M)*log(N+M))?
отдельную статью с картинками по этому вопросунаверное так проще :), было бы здорово!
В нашем случае есть ещё одна сетка, уже самой тепловой карты, и мы смогли использовать прямо её уже на этом уровне. Получилось вообще не очевидное решение на грани трюкачества, в силу особенностей алгоритма. Сложность близкая к логарифму, да. Если начать его расписывать, можно ненароком раскрыть сам алгоритм, а я не имею права его раскрывать.
Описать в общем виде попробовать можно, но я не знаю, когда у меня найдётся время на такую статью, и не уверен, что здесь она будет хоть кому-то интересна, кроме нас с вами. Но я добавлю в список пожеланий.
Описать в общем виде попробовать можно, но я не знаю, когда у меня найдётся время на такую статью, и не уверен, что здесь она будет хоть кому-то интересна, кроме нас с вами. Но я добавлю в список пожеланий.
А на сколько оно быстрее стандартных реализаций bipartite collision detection? И если оно O(N*log(N)), то зачем распределенные вычисления? По моим прикидкам, 10 миллионов точек должны за несколько секунд на одном десктопе рассчитываться.
Понятия не имею. Мы изначально исходили из собственной алгоритмики, ограничивающей радиус, и раскладывающей пары по подклассам удалённости. Как отдельную задачу даже не пытались решать, потому что смысла в ней нет.
А точек у нас давно сильно больше, чем может потянуть одиночный десктоп.
А точек у нас давно сильно больше, чем может потянуть одиночный десктоп.
N 000 000 000 000 расстоянийПонятно, просто из мотивационной части и выделенного жирным примера расчётов «в лоб» у меня сложилось впечатление, что именно эта часть и есть основная причина всех этих наворотов с Hadoop и Spark. В то же время, если я правильно понял по вашему примеру с умной разбивкой, расчёт «не в лоб» снижает число необходимых вычислений на много порядков и тогда становится неясно, зачем Spark.
А сколько у вас точек примерно, если не секрет?
собственной алгоритмики, ограничивающей радиус, и раскладывающей пары по подклассам удалённостиА алгоритмы collision detection тут не подходят? По описанию звучит так, будто это одинаковые задачи.
Уточню ещё. Мало для каждой пары расстояние вычислить и отбросить те, которые далеки. Ещё надо найти её соседей (и я об этом сказал в статье), то есть пары с расстояниями, близкими к вычисленному. И всё это надо делать за один проход.
Не думаю, что понятнее стало :)
Не думаю, что понятнее стало :)
Вроде, вполне понятно. Именно это и делают алгоритмы collision detection. Более того, оказывается, что бы отбросить те пары, которые далеки — не нужно вычислять все расстояния для всех возможных пар, это всё равно что сортировать пузырьком — эффективно только в особых случаях, то же касается и поиска соседей.
Схожая задача возникает также в multi-body physics simulations и при реализации в «лоб» их сложность растёт по квадрату, как в примере из статьи. Там есть «близкие» взаимодействия и «дальнодействующие», потому нужно знать соседей и «анти»-соседей. В продакшн-коде используется иерархическая или адаптивная разбивка пространства и выходит N*log(N). В Multi-body physics на сегодняшний день на просчёт всего этого для миллиона частиц уходит меньше 10 миллисекунд на одном GPU типа GTX 2080Ti.
Схожая задача возникает также в multi-body physics simulations и при реализации в «лоб» их сложность растёт по квадрату, как в примере из статьи. Там есть «близкие» взаимодействия и «дальнодействующие», потому нужно знать соседей и «анти»-соседей. В продакшн-коде используется иерархическая или адаптивная разбивка пространства и выходит N*log(N). В Multi-body physics на сегодняшний день на просчёт всего этого для миллиона частиц уходит меньше 10 миллисекунд на одном GPU типа GTX 2080Ti.
Правда, в это для варианта с примерно однородной плотностью. Задача с разбросом плотностей, возникает в орбитальной динамике и симуляциях галактик, какой там performance — не знаю, но что-то похожее.
Слишком всё это rocket science. Но я вообще не scientist, так, Senior Java Макака с кучей всяких поверхностных знаний с предыдущих проектов.
Алгоритмы мне спускают люди с докторской степенью, а я в меру своего невежества применяю такую оптимизацию, которая в рамках моего понимания. Где-то строю bitmap index для чего-то похожего на flood fill, где-то юзаю конечные автоматы, ну или ещё что.
Будь у меня толпа разработчиков и куча времени, я бы мог потратить его на изучение всяких умных штук, но я неспроста написал, что мы проект, а не контора. Если вам интересно в нём поучаствовать, можете найти контакты лондонского Полякова и предложить ему свои услуги по алгоритмистике.
Алгоритмы мне спускают люди с докторской степенью, а я в меру своего невежества применяю такую оптимизацию, которая в рамках моего понимания. Где-то строю bitmap index для чего-то похожего на flood fill, где-то юзаю конечные автоматы, ну или ещё что.
Будь у меня толпа разработчиков и куча времени, я бы мог потратить его на изучение всяких умных штук, но я неспроста написал, что мы проект, а не контора. Если вам интересно в нём поучаствовать, можете найти контакты лондонского Полякова и предложить ему свои услуги по алгоритмистике.
Да не, там ничего сложного, фактически это просто адаптация бинарного дерева для 2d случая. Я просто описал как-то закручено, наверное. Подозреваю, что у вас там какие-то свои сложности. Да и у вас сложность тоже логлинейная получилась, значит вы тоже не все пары просчитываете, то есть фактически у вас реализовано что-то похожее. Я потому и спрашиваю, потому что во введении вы ссылаетесь на квадрат, а потом выходит логлинейная. А сколько точек у вас?
есть ещё одна сетка, уже самой тепловой карты, и мы смогли использовать прямо её уже на этом уровне.Есть такое типовое решение: строится 2d гистограмма (heatmap), затем на основе этой гистограммы склеивают несколько сеток с разным шагом либо делают вложенные сетки для пиков. Для некоторых частных случаев можно получить около-линейную асимптотику. Правда «вложенные сетки для пиков» — это и есть пространственные деревья…
>Не на JSF же мне его склепать, эт будет даже не ретро, а уже какое-то некро.
Ну, вы знаете, есть масса людей, которые плюются от Flash, при этом я всего пару лет назад повторил свой опыт написания приложения на Flex, и в итоге получил окошко с картой и приличной допольнительной функциональностью примерно за пару дней.
В смысле — не все старое плохое.
Ну, вы знаете, есть масса людей, которые плюются от Flash, при этом я всего пару лет назад повторил свой опыт написания приложения на Flex, и в итоге получил окошко с картой и приличной допольнительной функциональностью примерно за пару дней.
В смысле — не все старое плохое.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
[кейс Locomizer] Как за два с половиной года ускорить расчёт тепловой карты в 20 000 раз