Не кинокритик. Не палеонтолог. (plakhov) wrote,
Не кинокритик. Не палеонтолог.
plakhov

Category:

LSH improvement

Товарищи из Yahoo! Research отжигают (pdf): сильно ускорили locality sensitive hashes в задаче поиска ближайших соседей в многомерном пространстве (и, в отличие от новых супер-алгоритмов умножения чисел, не только в теории, но и на практике: способ протестирован на всяких Web-dataset'ах, и действительно всё ускоряет). Прогресс быстрый - со времени изобретения SimHash не прошло и десяти лет.

Кратко для тех, кто не понимает, о чём это всё. Строятся структуры данных, поддерживающие примерно следующие операции: "запомнить" d-мерный вектор, затратив на это амортизированное время O(d); и по заданному d-мерному вектору за время O(...) найти ближайшего соседа среди запомненных векторов. Что будет стоять на месте многоточия, зависит от способа, но это должно быть что-то, что сильно меньше dN, где N - число "запомненных" векторов. В конце девяностых - начале двухтысячных стало понятно, что если добавить слова "с вероятностью не менее заранее заданной p, например, не менее 99%", то даже при очень больших d это вовсе не безнадежная задача. Такие структуры данных - запчасть, важная для построения strong AI (как минимум, ассоциативной памяти, но вообще я думаю, что не только), а также для всяких более приземленных задач типа поиска музыки или картинок.
Tags: math, search
Subscribe

  • Ссылки

    После того, как сей блог удачно попал на Лепру (или куда там), тут появилось ещё примерно сто новых читателей, и я теперь, как дурак, чувствую себя…

  • (no subject)

    Сегодня у меня день рождения. На свой день рождения я хочу следующий подарок: расскажите, пожалуйста, в комментариях что-нибудь интересное из вашей…

  • Выходя из шкафа

    Самая важная вещь, которую я узнал, читая /r/askhistorians, оказалась не про историков и даже не очень про прошлое. Так получается, что слово…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 11 comments

  • Ссылки

    После того, как сей блог удачно попал на Лепру (или куда там), тут появилось ещё примерно сто новых читателей, и я теперь, как дурак, чувствую себя…

  • (no subject)

    Сегодня у меня день рождения. На свой день рождения я хочу следующий подарок: расскажите, пожалуйста, в комментариях что-нибудь интересное из вашей…

  • Выходя из шкафа

    Самая важная вещь, которую я узнал, читая /r/askhistorians, оказалась не про историков и даже не очень про прошлое. Так получается, что слово…