Отчет аспиранта

[yury_lifshits]

Сегодня прочитал доклад "Алгоритмы поиска ближайших соседей" в Яндексе - слайды, слайды для печати, mp3 (63 мин/29 mb). Продолжение на Колмогоровском семинаре МГУ - слайды, слайды для печатиПрочитал в Штутгарте четыре лекции, пытаясь описать в целом поле исследований по веб-алгоритмам и обозначить наиболее перспективные направления для дальнейших

Comments

Нижняя оценка на сложность

[mish_a]

Привет,

Я вчера упомянул статью Chavez et al 2001 ( http://citeseer.ist.psu.edu/456573.html ).

Там есть раздел "THE CURSE OF DIMENSIONALITY", начиная со стр. 35. Доказываются весьма практичные, на мой взгляд, теоремы о нижней оценке на количество сравнений для "точных" алгоритмов поиска похожих.
Правда, там рассматриваются range queries, но для nearest neighbours queries должно быть похоже.

Миша.

Re: Нижняя оценка на сложность

[yury_lifshits]

Отлично, я скопировал статью в свой "readlist". Рано или поздно я до нее доберусь.

[minaton]

а на русском языке эти статьи возможны?

[yury_lifshits]

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

[starik_x]

"Maximal Intersection.." и "Estimation of the Click Volume.." - одна и та же ссылка, хм

[yury_lifshits]

Спасибо, исправил.