S>Ты не мог бы поподробнее об этом рассказать? Я плохо представляю, как можно применить k-D деревья для пространств, где близко расположенными точками считаются те, которые совпадают по K координатам из N, независимо от расстояния по остальным N-K координатам.
Вместо одного поиска по N координатам делаем N поисков по одной координате.
S>>Ты не мог бы поподробнее об этом рассказать? Я плохо представляю, как можно применить k-D деревья для пространств, где близко расположенными точками считаются те, которые совпадают по K координатам из N, независимо от расстояния по остальным N-K координатам.
sch>Вместо одного поиска по N координатам делаем N поисков по одной координате.
А-а. С этим эффективнее справится совершенно обычный линейный индекс: заводим N индексов по каждой координате, строим union из N запросов и вуаля...
Кстати, это почти что то же самое, что и развертка в нормализованную таблицу коэффициентов — только индексов много, а не один.
k-d деревья, AFAIK, помогают тогда, когда селективность поиска по одной координате низка, так что join результатов отдельных запросов дорого стоит.
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
S>А-а. С этим эффективнее справится совершенно обычный линейный индекс: заводим N индексов по каждой координате, строим union из N запросов и вуаля...
Если распределение значенйи координаты абсолютно линейное, то фактически линейный индекс и k-D деревья будут очень похожими и дадут одинаковые результаты.
В обратном случае, особенно если функция распределения имеет большие скачки, k-D дерево конечно будет быстрее, но будет стоить больше памяти.
Хотя это все копейки, согласен?
S>k-d деревья, AFAIK, помогают тогда, когда селективность поиска по одной координате низка, так что join результатов отдельных запросов дорого стоит.
В пределах нашей задачи, насколько я понимл, join не нужен -- достаточно совпадения хотя бы по одной координате.
Здравствуйте, sch, Вы писали:
sch>Если распределение значенйи координаты абсолютно линейное, то фактически линейный индекс и k-D деревья будут очень похожими и дадут одинаковые результаты. sch>В обратном случае, особенно если функция распределения имеет большие скачки, k-D дерево конечно будет быстрее
Это почему? Че-то я не догоняю, каким образом распределение значения повлияет на B-tree линейный индекс. Кстати, не подскажешь, что такое "линейное" распределение? sch>Хотя это все копейки, согласен?
Дык вот именно. Хочется, чтобы объем сканирования был O(R + logN), где N — количество образцов, R — количество найденных. S>>k-d деревья, AFAIK, помогают тогда, когда селективность поиска по одной координате низка, так что join результатов отдельных запросов дорого стоит. sch>В пределах нашей задачи, насколько я понимл, join не нужен -- достаточно совпадения хотя бы по одной координате.
Неа, надо совпадение по K
В общем, я так понял, что никто с подобной задачей сам не сталкивался. Очень жаль
Кто прав в споре "линейные индексы vs k-D tree" — покажет практика.
Попробую реализовать систему в одном и в другои варантах и сделать сравнительное тестирование пока есть время. Пока я больше склонен к версии линейных индексов.
Если у кого возникнут ещё интересные варианты — готов рассмотреть
... << Тишина>>
Не восхрапи на работе, ибо храпом своим разбудишь начальника своего.
S>Это почему? Че-то я не догоняю, каким образом распределение значения повлияет на B-tree линейный индекс. Кстати, не подскажешь, что такое "линейное" распределение?
Струтура k-D дерева более адекватна исходным данным, поэтому поиск и будет быстрее. Хотя зависит от реализации.
Под "линейным" распределением я понимаю то, что вероятность попадания значения в интервал пропорциональна длине интервала (оно же равномерное распределение).
S>Дык вот именно. Хочется, чтобы объем сканирования был O(R + logN), где N — количество образцов, R — количество найденных.
Я имел в виду совершенно не то, что разница между O(n) и O(log(n)) -- копейки, а то, что и k-D дерево и линейный индекс дадут O(log(n)), но дерево побыстрее будет.
sch>>В пределах нашей задачи, насколько я понимл, join не нужен -- достаточно совпадения хотя бы по одной координате. S>Неа, надо совпадение по K
.
Ну вместо одного поиска делаем от K до N поисков, пока количество найденных результатов не станет равно K. Какая разница? O(C*f(x)) = O(f(x)), где C=const. Время все равно логарифмическое будет, хоть 1000 элементов, хоть 1000*1000.
Грубо говоря, мы с тобой говорим об одной и той же структуре, за тем исключением что ты предпологаешь считать критерием построения дерева его сбалансированность, а я предлагаю считать критерием построения дерева распределение ключей. Что, опять же, в конечном итоге -- одно и то же.
С другой стороны, я настаиваю на том, что не стоит полагаться в такой большой по объему данных задаче на БД, а стоит держать дерево целиком в памяти и искать самостоятельно, что даст огромный выигрыш по производительности.
Пусть у нас характеристический вектор 256-мерный. Тогда весь вектор займет килобайт. Если сообщений 30,000 -- памяти надо будет всего 30 мегабайт.
Опять же, можно развивать эту идею как угодно. Можно распаралелить поиск, можно хранить не все дерево в памяти.
Здравствуйте, sch, Вы писали:
S>>Это почему? Че-то я не догоняю, каким образом распределение значения повлияет на B-tree линейный индекс. Кстати, не подскажешь, что такое "линейное" распределение? sch>Струтура k-D дерева более адекватна исходным данным, поэтому поиск и будет быстрее.
Вот этого места я и не понимаю. B-tree уже сбалансировано независимо от распределения значений ключей. За счет чего должно получиться улучшение?
К тому же, kd-деревья совершенно четко специализированы для многомерных данных. А ты предлагаешь использовать их для линейного индекса. Ты не мог бы пролить чуть больше света? sch>Я имел в виду совершенно не то, что разница между O(n) и O(log(n)) -- копейки, а то, что и k-D дерево и линейный индекс дадут O(log(n)), но дерево побыстрее будет.
За счет чего? sch>>>В пределах нашей задачи, насколько я понимл, join не нужен -- достаточно совпадения хотя бы по одной координате. S>>Неа, надо совпадение по K
. sch>Ну вместо одного поиска делаем от K до N поисков, пока количество найденных результатов не станет равно K. Какая разница? O(C*f(x)) = O(f(x)), где C=const. Время все равно логарифмическое будет, хоть 1000 элементов, хоть 1000*1000.
По-моему, ты что-то путаешь. Никаким log(N) здесь и не пахнет. Каким алгоритмом ты собрался считать пересечение списков полученных на шагах 1-K? sch>Грубо говоря, мы с тобой говорим об одной и той же структуре, за тем исключением что ты предпологаешь считать критерием построения дерева его сбалансированность, а я предлагаю считать критерием построения дерева распределение ключей. Что, опять же, в конечном итоге -- одно и то же.
Я теряю ход твоей мысли. sch>С другой стороны, я настаиваю на том, что не стоит полагаться в такой большой по объему данных задаче на БД, а стоит держать дерево целиком в памяти и искать самостоятельно, что даст огромный выигрыш по производительности.
Все зависит от очень многих параметров. В частности, совершенно не факт, что все влезет в память. А смоае милое — это объем отладки. Как только ты включишь многопотоковость, тебя ждут многочисленные грабли. Вот ты, к примеру, сможешь навскидку вспомнить корректный алгоритм раздачи блокировок в дереве? Хоть в B, хоть в KD? sch>Пусть у нас характеристический вектор 256-мерный. Тогда весь вектор займет килобайт. Если сообщений 30,000 -- памяти надо будет всего 30 мегабайт.
К сожалению, речь идет о том, чтобы хранить порядка 500000 этих векторов. Это уже полгига чистых данных, а ведь нужны еще служебные структуры. Уже есть необходимость реализовывать кэширование и своп части данных на диск. sch>Опять же, можно развивать эту идею как угодно. Можно распаралелить поиск, можно хранить не все дерево в памяти.
Есть у меня подозрение, что при развитии ты придешь к самописаной RDBMS. Потому, что надо не только читать, но и модифицировать дерево, и flush-ить его на диск, а тут возникает вопрос об ACIDности...
1.1.4 stable rev. 510
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
1.1.4 stable rev. 510
