линейная масштабируемость

[109]

в продолжение.
откуда вообще взялся странный миф, что любая произвольная система должна линейно масштабироваться? это же всё равно что сказать, что для любой задачи должно существовать решение алгоритмической сложности O(N).

Comments

[109.livejournal.com]

read-only queries масштабируются линейно, спору нет. и вообще с этим текстом я полностью согласен, as long as the message is "кое-что масштабируется линейно", а не "всё масштабируется линейно".

кстати можешь вспомнить какой нибудь реальный алгоритм которые регулярно отрабатывает на больше, чем на 1000 машин и имеет сложность как минимум n*n и находится в условиях экспоненциального увеличения данных в зависимости от роста интернета например?

мнэ... может не в точности что ты спрашиваешь, но вот один из моих проектов. есть у нас local entity feeds. local entity - это что угодно, имеющее координаты. магазин, ресторан, человек, мост через речку. feeds поступают как от фирм, продающих эти данные, так и от кроулинга интернета.

проблемы: 1. есть существенное перекрытие в данных и 2. данные не идеальны (где-то телефон неправильный, где-то название с ашипкой, и т.д.)

соответственно, надо дедупить, матч/мёржить и автокорректить. сложность, как очевидно, О(n*n) от размера данных. гм... может, не очевидно - поясняю. данные, которые мы получаем, уже покрывают практически каждый бизнес в штатах; большинство бизнесов - несколько раз. дальнейший рост размера данных будет происходить за счёт увеличения оверлапа.

[anatolix.livejournal.com]

Ну во первых идя которую ты описал она все-таки не про online запросы.

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

[109.livejournal.com]

нет, конечно не со всеми. сравниваем с маленьким сабсетом, размер которого, тем не менее, пропорционален произведению суммарного количества данных на долю дупликатов. то есть N*N.