Нитки лш: Нитки полиэфирные ЛШ (штапельный лавсан)

Библиотека хэширования C++ с учетом местоположения

LSHKIT: LSHKIT: Библиотека хэширования C++ с учетом местоположения

  • Главная страница
  • Классы
  • Файлы

Эта библиотека является частью проекта CASS.

Автор:
Вэй Дун вдонг [@] cs.princeton.edu

2008-2009

лшкит 0.2.1 - 17 сентября 2009 г.
* Постериорный мультизонд LSH (include/lshkit/apost.h tools/apost-run.cpp)
* Спектральное хеширование (include/lshkit/spectral-hash.h)
лшкит пред-0.2 - 2009-03-02
* Представлен экспериментальный интерфейс сканера. Scanner — это унарный функциональный объект, который передается в
Индекс LSH для сканирования точек-кандидатов и обновления результатов K-NN. Есть несколько преимуществ
это изменение:
1. Метод запроса индекса LSH теперь является потокобезопасным (если сканеры являются потокобезопасными). Это делает параллель
возможно выполнение запроса.
2. Это упрощает реализацию.  Классы индекса LSH больше не должны поддерживать метод доступа и метрику.
объекты.
3. Без изменения API-интерфейса LSH-индекса теперь можно легко комбинировать LSH-индексирование и фильтрацию скетчей.
(используя эскизы для быстрой фильтрации кандидата LSH, а затем используя необработанные данные для ранжирования сокращенного набора кандидатов).
Это еще больше улучшит скорость запросов, когда LSH возвращает большое количество кандидатов. Пример
будет предоставлен в ближайшее время.
Ишкит 0.1.9- 02 марта 2009 г.
* Улучшен алгоритм моделирования MPLSH, чтобы он работал с векторами признаков с большими абсолютными значениями.
* Добавлена ​​предварительная реализация LSH Forest с примером программы tools/forest-run.cpp.
* Добавлен tools/embedder.cpp, пример программы встраивания случайной гистограммы.
* Добавлена ​​поддержка R-NN (запрос диапазона) в Topk.
* Добавлена ​​поддержка R-NN в tools/scan.cpp, tools/mplsh-run.cpp, tools/lsh-run.cpp, tools/sketch-run.cpp. Установите K = 0 для R-NN.
* Добавлен tools/txt2bin. cpp для преобразования текстового файла данных в двоичный.
Текущая реализация индекса не является потокобезопасной. Я собираюсь изменить индексный API в следующей версии (0.2). Это серьезное изменение. Это последний выпуск со старым индексным API.
Ишкит 0.1.2 - 2009-02-15
* Небольшое исправление прилагаемого буст-дистрибутива, не тронутый файл LSHKIT.
лшкит 0.1.1 - 14 февраля 2009 г.
 
* В пакет добавлены необходимые исходные файлы Boost, поэтому автономная установка boost не требуется.
* Уменьшена зависимость от Boost. Теперь для инструментов нужно связать только boost_program_option. Основная библиотека LSHKIT зависит только от заголовочных файлов Boost.
лшкит 0.1 - 11 февраля 2009 г.
* Это первоначальная версия LSHKIT.
* Проект перенесен на sourceforge.
    • Страница проекта Sourceforge: http://sourceforge.net/projects/lshkit/
    • Исходный код браузера: http://lshkit.cvs.sourceforge.net/lshkit/
    • Скачать выпуск: http://sourceforge. net/project/showfiles. php?group_id=253020
    • Список рассылки: http://sourceforge.net/mailarchive/forum.php?forum_name=lshkit-users
    • Пример набора данных: http://www.cs.princeton. edu/cass/audio.tar.gz

    Пример набора данных включает файл данных audio.data и файл эталона audio.query. Audio.data содержит 54 387 192-мерные векторы, а тест содержит 10 000 запросов по 200 NN.

    ПРИМЕЧАНИЕ. Вам не нужно собирать LSHKIT отдельно, если вы хотите использовать только библиотеку, но не инструментальные программы. Вместо этого вы можете напрямую объединить исходные файлы LSHKIT со своим проектом. Вы можете избежать установки CMake, сделав это. Подробности см. в разделе 3.2.

    Для LSHKIT требуются следующие библиотеки:

    • Научная библиотека Gnu
    • [ДОПОЛНИТЕЛЬНО] Boost Library > 1.36, используются следующие пакеты:
      • параметры программы

    LSHKIT использует кроссплатформенную систему сборки CMake.

    2.1 Microsoft Visual C++ Express 2008

    Этот метод, вероятно, сработает и для других версий Visual C++, но я не проверял.

    Вам придется сначала установить GSL и CMake, если вы еще этого не сделали. См. следующие страницы:

    • GSL: http://www.quantcode.com/modules/smartfaq/faq.php?faqid=33
    • CMake: http://www.cmake.org/

    После установки все еще нужны следующие конфигурации, чтобы CMake мог найти GSL:

    • Добавьте переменную среды GSL_ROOT_DIR, чтобы %GSL_ROOT_DIR%\include содержал заголовочные файлы GSL, а %GSL_ROOT_DIR%\lib содержал библиотеки GSL.
    • Скопируйте файл lshkit\FindGSL.cmake в \share\cmake-xxx\Modules, где — это место установки CMake.

    Если в вашей системе установлен Boost, вы можете использовать свою собственную установку Boost вместо минимальной, поставляемой с LSHKIT. Для этого добавьте переменную среды BOOST_ROOT, чтобы %BOOST_ROOT%\include содержал заголовочные файлы Boost, а %BOOST_ROOT%\lib содержал библиотеки Boost.

    Теперь мы готовы построить LSHKIT. Откройте командную строку Visual C++ (щелкнув «Пуск/Все программы/Microsoft Visual C++. ../Visual Studio Tools/Visual Studio 2008 Command Prompt») и выполните следующие действия:

  1. Создайте каталог сборки, который мы вызовите BULID_DIR, перейдите в каталог.
  2. Запустите «cmakesetup », где — корневой каталог LSHKIT.
  3. Появится окно настройки CMake. Нажмите кнопку «Настроить» в нижней части окна.
  4. Выберите «NMake Makefiles» во всплывающем окне и подтвердите.
  5. CMake будет работать некоторое время.
  6. После появления списка красных кэшированных значений снова нажмите кнопку «Настроить». Возможно, перед этим вы захотите изменить значение некоторых переменных, например, изменить CMAKE_BUILD_TYPE с «Отладка» на «Выпуск», чтобы включить оптимизацию.
  7. Кэшированные переменные теперь становятся серыми, нажмите кнопку «ОК» внизу.
  8. Создан Makefile, для его создания запустите «nmake».
  9. Процесс изготовления продлится какое-то время. После этого библиотека LSHKIT окажется в каталоге «lib», а исполняемые файлы — в каталоге «bin».

На шаге 4 вы также можете выбрать «Visual Studio 9 2008» (или другие версии), чтобы создать файл проекта, который вы можете построить с помощью Visual C++ IDE.

2.2 Линукс

  1. Скопируйте файл lshkit\FindGSL.cmake в /share/cmake-xxx/Modules, где — это место установки CMake, обычно это /usr.
  2. создать временный каталог здания, перейти в него.
  3. Запустите «cmake LSHKIT_DIR», где LSHKIT_DIR — это корневой каталог LSHKIT. Вы также можете использовать «cmake -DCMAKE_BUILD_TYPE=RELEASE LSHKIT_DIR» или «cmake -DCMAKE_BUILD_TYPE=DEBUG LSHKIT_DIR», чтобы указать тип сборки.
  4. Должен быть сгенерирован make-файл. Беги делай.
  5. Процесс изготовления продлится какое-то время. После этого библиотека LSHKIT окажется в каталоге «lib», а исполняемые файлы — в каталоге «bin».

Хотя программы инструментов LSHKIT зависят от boost_program_option для разбора параметров командной строки, основная библиотека LSHKIT зависит только от заголовков Boost. Если вы используете библиотеку LSHKIT в своем проекте, вам не нужно связываться с какой-либо из библиотек повышения (если вы не используете их в других частях вашего проекта).

3.1 Использовать LSHKIT в качестве библиотеки

  1. Сборка ЛШКИТ.
  2. Настройте среду сборки так, чтобы «LSHKIT_DIR/include» и библиотека LSHKIT могли быть найдены вашим компилятором C++. Если в вашей системе не установлен Boost, вам также необходимо добавить «LSHKIT/3rd-party/boost» в путь поиска включаемых файлов вашего компилятора.
  3. Добавьте «#include » в исходный код C++, и вы сможете использовать большинство функций LSHKIT.
  4. Свяжите libgsl и libgslcblas (они могут называться по-разному в зависимости от вашей системы) с вашей программой.

3.2 Напрямую добавьте исходный код LSHKIT в свой проект

Используя напрямую исходный код LSHKIT, вы можете избежать установки CMake.

  1. Настройте среду сборки так, чтобы «LSHKIT_DIR/include» и библиотека LSHKIT могли быть найдены вашим компилятором C++. Если в вашей системе не установлен Boost, вам также необходимо добавить «LSHKIT/3rd-party/boost» в путь поиска включаемых файлов вашего компилятора.
  2. Убедитесь, что GSL правильно установлен в вашей системе и ваш компилятор может найти заголовочные файлы GSL.
  3. Добавьте в проект все исходные файлы C++ из «LSHKIT/src».
  4. Добавьте «#include » в исходный код C++, и вы сможете использовать большинство функций LSHKIT.
  5. Свяжите libgsl и libgslcblas (они могут называться по-разному в зависимости от вашей системы) с вашей программой.

(См. документацию по указанным исходным файлам.)

  • Формат файла, используемый инструментальными программами: matrix.h
  • (Полуавтоматическая) настройка параметров для Multi-Probe LSH и запуск тестов: mplsh-tune.cpp
  • Построение индекса Multi-Probe LSH: mplsh.h
  • Использование LSH для создания скетчей: sketch.h
  • Использование LSH для построения случайных гистограмм для сопоставления наборов признаков: histogram. h
  • Поддерживаемые классы LSH: lsh.h
  • Как построить сложные классы LSH из базовых: Composite.h
  • Как добавить свои собственные классы LSH : концепция.h
  • scan.cpp
  • lsh-run.cpp
  • mplsh-run.cpp
  • fitdata.cpp
  • mplsh-predict.cpp
  • mplsh-tune.cpp

0c 0.4pp-run скетч
LSHKIT распространяется на условиях Стандартной общественной лицензии GNU (GPL).

Я не собираюсь использовать строгую лицензию GPL. Однако часть пакета, связанная с моделированием производительности, зависит от научной библиотеки Gnu под лицензией GPL для регрессии, поиска корней и численного интегрирования. Если вы хотите использовать LSHKIT в своем программном обеспечении с закрытым исходным кодом и хотите избавиться от части моделирования производительности (в принципе, вы все равно сможете использовать его для настройки производительности, если вы не распространяете его; результаты могут быть жестко запрограммированы в ваше программное обеспечение, не распространяемое под GPL), свяжитесь со мной, и, возможно, мы сможем найти способ.

Вей Дун, Чжэ Ван, Уильям Джозефсон, Мозес Чарикар, Кай Ли. Моделирование LSH для настройки производительности. В материалах 17-й конференции по управлению информацией и знаниями. Долина Напа, Калифорния, США. Октябрь 2008 г.

Вэй Дун, Чжэ Ван, Мозес Чарикар, Кай Ли. Эффективное сопоставление наборов признаков со случайными гистограммами. В материалах 16-й Международной конференции ACM по мультимедиа. Ванкувер, Канада. Октябрь 2008 г.

Вей Донг, Мозес Чарикар, Кай Ли. Асимметричная оценка расстояния с помощью эскизов для поиска сходства в многомерных пространствах. В материалах 31-й ежегодной международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска. Сингапур. Июль 2008.


идей LSH

идей LSH

[Дата Предыдущая][Дата Следующая][Предыдущая Тема][Следующая Тема][Указатель Даты][Указатель Темы]

  • Для : [email protected]
  • Тема : Идеи LSH
  • Из : Суббарао Камбхампати 2)
    Идея, которую мы попытаемся использовать, состоит в том, чтобы сделать какую-то схему хеширования и
    хешируйте каждый документ, как только он появится, в ведро. Документы втиснуты в
    одинаковые ведра (т. е. те, которые «сталкиваются») считаются
    «похожий»
    Для этого нам нужно сделать хеш-функцию такой, что
    два документа сталкиваются с этой хэш-функцией, только если они похожи.
    — Небольшая проблема: обратите внимание, что мы действуем так, как будто сходство является бинарным
    концепция. Мы можем сделать это, предположив, что любая пара страниц,
    числовая метрика сходства выше определенного порога
    считать похожими и неодинаковыми в остальном.
    Невозможно точно гарантировать это ни для какого определения
    сходство. Но мы можем попытаться гарантировать это в «вероятностной»
    смысл. В частности, нам могут понадобиться хэш-функции w.r.t. который
    вероятность столкновения между двумя документами пропорциональна их
    сходство.
    Этим свойством обладают «минимальные» хэш-функции.
    В частности, мы генерируем поминутные хэш-значения набора из двух документов как
    следует:
    Шаг 1. Сделайте случайную перестановку p всех слагаемых
    Шаг 2. Хэш-значение документа d под p — это терм t в d, который
    появляется первым в перестановке p
    Предположим, что в нашей вселенной есть термины «кошка», «собака», «мышь» и «банан».
    у нас есть два документа d1={мышь,собака} d2={кошка,мышь}
    Случайная перестановка p в терминах: {кошка—собака—мышь—банан}
    согласно p, хеш-значение d1 — это собака, а хэш-значение d2 — это кошка.
    Другой случайной перестановкой p2 является {банан—мышь—кошка—собака} и хэш
    значения относительно p2 для d1 — мышь, а для d2 — мышь.
    Предположим, мы делаем m разных хеш-значений для каждого из документов.
    Пусть m’ будет числом случаев, когда d1 и d2 имеют одно и то же значение.
    Теперь **ВАЖНОЕ**
    Можно показать, что m’/m стремится к
    |d1 .пересечение. d2|/|d1 .союз. d2| для больших значений m
    Другими словами, вероятность столкновения равна подобию
    между документами (по нашей мере сходства). Как удобно, а?
    (это объясняет, почему мы так удобно определяем сходство в
    условия пересечения и объединения).
    ===============================
    Теперь проблема с использованием только минимальных хеш-функций заключается в том, что в то время как
    они помещают похожие документы в одно ведро, они также могут помещать
    разные документы в одном сегменте.
    Чтобы уменьшить вероятность столкновения двух непохожих документов, мы
    нужно сделать так, чтобы документы стали похожими.
    Итак, мы говорим, что недостаточно, чтобы два документа согласовали хотя бы один
    минимальное значение хеш-функции, но они должны согласовать некоторое количество k
    минимальные хэш-значения.
    Это формализуется с помощью схемы хеширования на основе локальности.
    Предположим, мы создали m разных значений хеш-функции для каждого документа.
    Мы можем создать подпись LSH размером k, выбрав сначала k случайных чисел.
    от 1 до m и объединяя эти k значений хеш-функции поминутно, чтобы получить
    хеш-подпись.
    Например, предположим, что у нас есть
    документ А:
    {мышь, собака, лошадь, муравей}
    и документ Б:
    {кот, лед, туфелька, мышь}
    предположим, что мы сгенерировали m=4 хеш-значения для каждого документа (используя 4 случайных
    перестановки слов мышь, собака, лошадь, муравей, кошка, лед, башмак
    для документа А
    Mh2 = лошадь
    Mh3 = мышь
    Mh4 = муравей
    Mh5 = собака
    для docB
    Мh2 = кошка
    Mh3 = мышь
    Mh4 = лёд
    Mh5 = башмак
    Чтобы получить подпись LSH длины k=3, мы сначала выбираем 3 числа между
    1 и 4 (скажем, 1,3,4) и получить подписи LSH для документов A и B как
    ЛШ234 = кошка-ледокол (док А)
    ЛШ234 = лошадь-муравей-собака (док Б)
    Теперь мы хотим, чтобы A и B считались подобными только в том случае, если они согласуются друг с другом.