Жергілікті жерге байланысты хэштеу - Locality-sensitive hashing

Информатикада, жергілікті сезімтал хэштеу (LSH) - бұл ұқсас кіріс элементтерін бірдей «шелектерге» үлкен ықтималдықпен жинайтын алгоритмдік әдіс.^[1] (Шелектер саны мүмкін болатын элементтердің әлемінен әлдеқайда аз.)^[1] Ұқсас заттар бір шелекте болатындықтан, бұл әдісті қолдануға болады деректер кластері және жақын көршіні іздеу. Бұл ерекшеленеді кәдімгі хэштеу әдістері бұл хэш қақтығыстары барынша азайтылады, азайтылады. Сонымен қатар, техниканы жол ретінде қарастыруға болады өлшемділікті азайту жоғары өлшемді мәліметтер; элементтер арасындағы салыстырмалы қашықтықты сақтай отырып, жоғары өлшемді енгізу элементтерін төмен өлшемді нұсқаларға дейін азайтуға болады.

Хэштеуге негізделген шамамен жақын көршіні іздеу алгоритмдер әдетте хэштеу әдістерінің екі негізгі санаттарының бірін қолданады: деректерге тәуелді емес әдістер, мысалы, локализацияға байланысты хэштеу (LSH); немесе деректерге тәуелді әдістер, мысалы Жергілікті жерді сақтайтын хэштеу (LPH).^[2]^[3]

Анықтамалар

Ан LSH отбасы^[1]^[4]^[5] ${displaystyle {mathcal {F}}}$ үшін анықталады метрикалық кеңістік ${displaystyle {mathcal {M}} = (M, d)}$ , табалдырық ${displaystyle R> 0}$ және жуықтау коэффициенті ${displaystyle c> 1}$ . Бұл отбасы ${displaystyle {mathcal {F}}}$ функциялардың отбасы ${displaystyle h: M o S}$ метрикалық кеңістіктен шелекке дейінгі элементтерді бейнелейтін ${displaystyle sin S}$ . LSH отбасы кез-келген екі ұпай үшін келесі шарттарды орындайды ${displaystyle p, qin M}$ , функцияны қолдану ${displaystyle hin {mathcal {F}}}$ ол кездейсоқ түрде біркелкі таңдалады:

егер ${displaystyle d (p, q) leq R}$ , содан кейін ${displaystyle h (p) = h (q)}$ (яғни, $б$ және $q$ соқтығысу) кем дегенде ықтималдықпен ${displaystyle P_ {1}}$ ,
егер ${displaystyle d (p, q) geq cR}$ , содан кейін ${displaystyle h (p) = h (q)}$ ықтималдығы бойынша ${displaystyle P_ {2}}$ .

Отбасы қашан қызық болады ${displaystyle P_ {1}> P_ {2}}$ . Мұндай отбасы ${displaystyle {mathcal {F}}}$ аталады ${displaystyle (R, cR, P_ {1}, P_ {2})}$ - сезімтал.

Сонымен қатар^[6] бұл заттар әлеміне қатысты анықталады $U$ бар ұқсастық функциясы ${displaystyle phi: U imes U o [0,1]}$ . LSH схемасы - бұл отбасы хэш функциялары $H$ ұштастырылған ықтималдықтың таралуы $Д.$ функция сияқты функциялардың үстінен ${displaystyle hin H}$ сәйкес таңдалған $Д.$ қасиетін қанағаттандырады ${displaystyle Pr_ {hin H} [h (a) = h (b)] = phi (a, b)}$ кез келген үшін ${displaystyle a, bin U}$ .

Жергілікті жерді сақтайтын хэштеу

A жерді сақтайтын хэштеу Бұл хэш функциясы f көп өлшемді нүктені немесе нүктелерді бейнелейтін координаталық кеңістік скалярлық мәнге, егер бізде үш ұпай болса A, B және C осындай

{displaystyle | A-B | <| B-C | Оң жақ сызық | f (A) -f (B) | <| f (B) -f (C) |.,}

Басқаша айтқанда, бұл кіріс мәндері арасындағы салыстырмалы қашықтық шығатын хэш мәндері арасындағы салыстырмалы қашықтықта сақталатын хэш функциялары; бір-біріне жақын кіріс мәндері бір-біріне жақын шығыс хэш мәндерін шығарады.

Бұл айырмашылығы криптографиялық хэш функциялары және сома болуы үшін жасалған іргелес кірістер арасындағы кездейсоқ шығыс айырмасы.

Хэштерді сақтайтын елді мекен байланысты кеңістікті толтыратын қисықтар.^{[Қалай? ]}

Күшейту

Берілген ${displaystyle (d_ {1}, d_ {2}, p_ {1}, p_ {2})}$ - сезімтал отбасы ${displaystyle {mathcal {F}}}$ , біз жаңа отбасылар құра аламыз ${displaystyle {mathcal {G}}}$ ЖӘНЕ-салу немесе Немесе-салу арқылы ${displaystyle {mathcal {F}}}$ .^[1]

ЖӘНЕ-құрылысын құру үшін біз жаңа отбасын анықтаймыз ${displaystyle {mathcal {G}}}$ хэш функциялары $ж$ , мұнда әр функция $ж$ бастап салынған $к$ кездейсоқ функциялар ${displaystyle h_ {1}, ..., h_ {k}}$ бастап ${displaystyle {mathcal {F}}}$ . Содан кейін біз хэш функциясы үшін деп айтамыз ${displaystyle gin {mathcal {G}}}$ , ${displaystyle g (x) = g (y)}$ егер және бәрі болса ғана ${displaystyle h_ {i} (x) = h_ {i} (y)}$ үшін ${displaystyle i = 1,2, ..., k}$ . Мүшелерінен бастап ${displaystyle {mathcal {F}}}$ кез-келгеніне тәуелсіз таңдалады ${displaystyle gin {mathcal {G}}}$ , ${displaystyle {mathcal {G}}}$ Бұл ${displaystyle (d_ {1}, d_ {2}, p_ {1} ^ {k}, p_ {2} ^ {k})}$ - сезімтал отбасы.

OR-құрылысын құру үшін біз жаңа отбасын анықтаймыз ${displaystyle {mathcal {G}}}$ хэш функциялары $ж$ , мұнда әр функция $ж$ бастап салынған $к$ кездейсоқ функциялар ${displaystyle h_ {1}, ..., h_ {k}}$ бастап ${displaystyle {mathcal {F}}}$ . Содан кейін біз хэш функциясы үшін деп айтамыз ${displaystyle gin {mathcal {G}}}$ , ${displaystyle g (x) = g (y)}$ егер және егер болса ${displaystyle h_ {i} (x) = h_ {i} (y)}$ үшін бір немесе бірнеше мәндер үшін $мен$ . Мүшелерінен бастап ${displaystyle {mathcal {F}}}$ кез-келгеніне тәуелсіз таңдалады ${displaystyle gin {mathcal {G}}}$ , ${displaystyle {mathcal {G}}}$ Бұл ${displaystyle (d_ {1}, d_ {2}, 1- (1-p_ {1}) ^ {k}, 1- (1-p_ {2}) ^ {k})}$ - сезімтал отбасы.

Қолданбалар

LSH бірнеше проблемалық домендерге қолданылды, соның ішінде:

Көшірмені анықтау^[7]
Иерархиялық кластерлеу^[8]^[9]
Жалпы геномды ассоциацияны зерттеу^[10]
Кескіннің ұқсастығын анықтау
- VisualRank
Ген экспрессиясы ұқсастықты сәйкестендіру^{[дәйексөз қажет ]}
Дыбыстың ұқсастығын анықтау
Көршіні іздеу
Дыбыстық саусақ ізі^[11]
Сандық саусақ іздері
Деректер қорын басқару жүйелеріндегі физикалық деректерді ұйымдастыру^[12]
Толығымен қосылған нейрондық желілерді оқыту^[13]

Әдістер

Хэмминг қашықтығы үшін бит сынамалары

LSH отбасын құрудың ең қарапайым әдістерінің бірі - іріктеу.^[5] Бұл тәсіл жұмыс істейді Хамминг қашықтығы d өлшемді векторлардан жоғары ${displaystyle {0,1} ^ {d}}$ . Міне, отбасы ${displaystyle {mathcal {F}}}$ хэш-функциялар - бұл жай нүктелердің бірінің барлық проекцияларының отбасы ${displaystyle d}$ координаттар, яғни ${displaystyle {mathcal {F}} = {h: {0,1} ^ {d} o {0,1} ортасы h (x) = x_ {i} {ext {кейбір}} iin {1, .. ., d}}}$ , қайда ${displaystyle x_ {i}}$ болып табылады ${displaystyle i}$ -ның координаты ${displaystyle x}$ . Кездейсоқ функция ${displaystyle h}$ бастап ${displaystyle {mathcal {F}}}$ жай кіру нүктесінен кездейсоқ битті таңдайды. Бұл отбасында келесі параметрлер бар: ${displaystyle P_ {1} = 1-R / d}$ , ${displaystyle P_ {2} = 1-cR / d}$ .^{[түсіндіру қажет ]}

Минималды тәуелсіз ауыстырулар

Айталық $U$ санамаланатын элементтердің кейбір жиынтық жиынтықтарынан тұрады $S$ және қызығушылықтың ұқсастық функциясы болып табылады Джеккард индексі $Дж$ . Егер $π$ индекстері бойынша ауыстыру болып табылады $S$ , үшін ${displaystyle Asubseteq S}$ рұқсат етіңіз ${displaystyle h (A) = min _ {ain A} {pi (a)}}$ . Әрбір мүмкін таңдау $π$ бір хэш функциясын анықтайды $сағ$ элементтерін енгізу жиынтықтарын бейнелеу $S$ .

Функцияның отбасын анықтаңыз $H$ барлық осындай функциялардың жиынтығы болу керек $Д.$ болуы біркелкі үлестіру. Екі жиынтық берілген ${displaystyle A, Bsubseteq S}$ бұл оқиға ${displaystyle h (A) = h (B)}$ минимизатор болатын оқиғаға дәл сәйкес келеді $π$ аяқталды ${displaystyle Acup B}$ ішінде жатыр ${displaystyle Acap B}$ . Қалай $сағ$ кездейсоқ түрде біркелкі таңдалған, ${displaystyle Pr [h (A) = h (B)] = J (A, B),}$ және ${displaystyle (H, D),}$ Жакард индексі үшін LSH схемасын анықтаңыз.

Себебі симметриялық топ қосулы $n$ элементтер мөлшері бар $n$ !, шынымен таңдау кездейсоқ ауыстыру толық симметриялы топтан тіпті орташа өлшемді адамдар үшін мүмкін емес $n$ . Осы жағдайға байланысты, «минималды тәуелсіз» пермутациялар тобын - доменнің әрбір элементі кездейсоқ таңдалған жағдайда минимумға тең болу ықтималдығы бар ауыстыру отбасын табу бойынша айтарлықтай жұмыстар жүргізілді. $π$ . Минималды тәуелсіз ауыстыру отбасының мөлшері кем дегенде болатындығы анықталды ${displaystyle операторының аты {lcm} (1,2, cdots, n) geq e ^ {n-o (n)}}$ ,^[14] және бұл қатаң.^[15]

Минималды тәуелсіз отбасылар практикалық қолдану үшін өте үлкен болғандықтан, минималды тәуелсіздіктің екі нұсқасы енгізілген: шектеулі тәуелсіз пермутациялардың отбасылары және минималды тәуелсіз отбасылар. тәуелсіздік қасиеті ең көп мөлшерде белгілі бір жиынтықпен шектелген $к$ .^[16]Шамамен тәуелсіз тәуелсіздік мүліктен максималды түрде ерекшеленеді $ε$ .^[17]

Ашық бастапқы әдістер

Нильсимса Хэш

Нильсимса - локализацияға қатысты хэштеу алгоритмі спамға қарсы күш.^[18] Нильсимсаның мақсаты - екі ұқсас хабарламаның дайджесттері бір-біріне ұқсас болатындай электрондық пошта хабарламасының хэш-дайджестін құру. Мақалада Nilsimsa-ның үш талапқа сай екендігі айтылады:

Әр хабарламаны анықтайтын дайджест автоматты түрде жасалуы мүмкін өзгерістер үшін айтарлықтай өзгермеуі керек.
Кодтау қасақана шабуылдарға қарсы берік болуы керек.
Кодтау жалған позитивтің өте төмен қаупін қамтамасыз етуі керек.

TLSH

TLSH қауіпсіздік пен цифрлық сот-медициналық қосымшаларға арналған локалды хэштеу алгоритмі.^[19] TLSH-тің мақсаты - егер екі дайджесттің арақашықтығы аз болса, онда хабарламалар бір-біріне ұқсас болуы мүмкін болатын хэш-дайджест құру.

Файл түрлерінің бірқатарында қағазда жүргізілген тестілеу Nilsimsa хэшін TLSH, Ssdeep және Sdhash сияқты басқа ұқсастықты дайджест схемаларымен салыстырғанда айтарлықтай жоғары жалған оң деңгейге ие деп анықтады.

TLSH енгізу мүмкіндігі келесідей ашық бастапқы бағдарламалық жасақтама.^[20]

Кездейсоқ проекция

Шағын бұрыштар үшін (ортогональға жақын емес),

{displaystyle 1- {frac {heta} {pi}}}

жуықтау болып табылады

{displaystyle cos (heta)}

.

Байланысты LSH-дің кездейсоқ проекциялау әдісі Мұса Чарикар^[6] деп аталады SimHash (кейде оны аркос деп те атайды^[21]) жуықтау үшін жасалған косинус қашықтығы векторлар арасында. Бұл техниканың негізгі идеясы кездейсоқ таңдау болып табылады гиперплан (қалыпты бірлік векторымен анықталады $р$ ) кіріс векторларын хештеу үшін гиперпланды қолданыңыз.

Кіріс векторы берілген $v$ және анықталған гиперплан $р$ , біз рұқсат етеміз ${displaystyle h (v) = sgn (vcdot r)}$ . Бұл, ${displaystyle h (v) = pm 1}$ гиперпланеттің қай жағына байланысты $v$ өтірік

Әрбір мүмкін таңдау $р$ бір функцияны анықтайды. Келіңіздер $H$ барлық осы функциялардың жиынтығы болыңыз $Д.$ тағы да біркелкі үлестірім болыңыз. Мұны екі вектор үшін дәлелдеу қиын емес ${displaystyle u, v}$ , ${displaystyle Pr [h (u) = h (v)] = 1- {frac {heta (u, v)} {pi}}}$ , қайда ${displaystyle heta (u, v)}$ арасындағы бұрыш $сен$ және $v$ . ${displaystyle 1- {frac {heta (u, v)} {pi}}}$ -мен тығыз байланысты ${displaystyle cos (heta (u, v))}$ .

Бұл жағдайда хэштеу тек бір бит шығарады. Екі вектор биті олардың арасындағы бұрыштың косинусына пропорционалды ықтималдықпен сәйкес келеді.

Тұрақты үлестірулер

Хэш функциясы^[22] ${displaystyle h_ {mathbf {a}, b} ({oldsymbol {upsilon}}): {mathcal {R}} ^ {d} o {mathcal {N}}}$ карталар а г. өлшемді вектор ${displaystyle {oldsymbol {upsilon}}}$ бүтін сандар жиынтығына. Отбасындағы әрбір хэш функциясы кездейсоқ таңдау арқылы индекстеледі ${displaystyle mathbf {a}}$ және ${displaystyle b}$ қайда ${displaystyle mathbf {a}}$ Бұл г. а-дан тәуелсіз таңдалған өлшемді векторлық талдаулар тұрақты таралу және ${displaystyle b}$ [0, r] ауқымынан біркелкі таңдалған нақты сан. Бекітілген үшін ${displaystyle mathbf {a}, b}$ хэш функциясы ${displaystyle h_ {mathbf {a}, b}}$ арқылы беріледі ${displaystyle h_ {mathbf {a}, b} ({oldsymbol {upsilon}}) = leftlfloor {frac {mathbf {a} cdot {oldsymbol {upsilon}} + b} {r}} ightfloor}$ .

Деректерге сай болу үшін хэш функциялары үшін басқа құрылыс әдістері ұсынылды. ^[23]Атап айтқанда k-хэш функциялары проекцияға негізделген хэш функцияларына қарағанда тәжірибеде жақсы, бірақ теориялық кепілдемесіз.

Жақын көршіні іздеуге арналған LSH алгоритмі

LSH-дің негізгі қосымшаларының бірі тиімді жуықтау әдісін ұсыну болып табылады жақын көршіні іздеу алгоритмдер. LSH отбасын қарастырайық ${displaystyle {mathcal {F}}}$ . Алгоритмде екі негізгі параметр бар: ен параметрі $к$ және хэш-кестелер саны $L$ .

Бірінші қадамда біз жаңа отбасын анықтаймыз ${displaystyle {mathcal {G}}}$ хэш функциялары $ж$ , мұнда әр функция $ж$ біріктіру арқылы алынады $к$ функциялары ${displaystyle h_ {1}, ..., h_ {k}}$ бастап ${displaystyle {mathcal {F}}}$ , яғни, ${displaystyle g (p) = [h_ {1} (p), ..., h_ {k} (p)]}$ . Басқаша айтқанда, кездейсоқ хэш-функция $ж$ біріктіру арқылы алынады $к$ кездейсоқ таңдалған хэш функциялары ${displaystyle {mathcal {F}}}$ . Алгоритм содан кейін құрастырылады $L$ әрқайсысы кездейсоқ таңдалған хэш функциясына сәйкес келетін хэш кестелері $ж$ .

Алдын ала өңдеу кезеңінде біз бәрін хэштейміз $n$ деректер жиынтығынан ұпайлар $S$ әрқайсысына $L$ хэш кестелер. Нәтижесінде пайда болатын хэш кестелерде тек бар $n$ нөлдік емес жазбалар, әрбір хэш-кестеде қолданылатын жад көлемін азайтуға болады ${displaystyle O (n)}$ стандартты қолдану хэш функциялары.

Сұрау нүктесі берілген $q$ , алгоритм қайталанады $L$ хэш функциялары $ж$ . Әрқайсысы үшін $ж$ қарастырылған болса, ол бірдей шелекке салынған деректер нүктелерін алады $q$ . Процесс қашықтықтағы нүкте ретінде тоқтатылады ${displaystyle cR}$ бастап $q$ табылды.

Параметрлерді ескере отырып $к$ және $L$ , алгоритмде келесі өнімділік кепілдіктері бар:

алдын ала өңдеу уақыты: ${displaystyle O (nLkt)}$ , қайда $т$ функцияны бағалау уақыты ${displaystyle hin {mathcal {F}}}$ кіріс нүктесінде $б$ ;
ғарыш: ${displaystyle O (nL)}$ , деректер нүктелерін сақтауға арналған орын;
сұрау уақыты: ${displaystyle O (L (kt + dnP_ {2} ^ {k}))}$ ;
алгоритм қашықтықтағы нүктені табуға жетеді ${displaystyle cR}$ бастап $q$ (егер қашықтықта нүкте болса) $R$ ) кем дегенде ықтималдықпен ${displaystyle 1- (1-P_ {1} ^ {k}) ^ {L}}$ ;

Бекітілген жуықтау коэффициенті үшін ${displaystyle c = 1 + эпсилон}$ және ықтималдықтар ${displaystyle P_ {1}}$ және ${displaystyle P_ {2}}$ , біреуін орнатуға болады ${displaystyle k = lceil {log n log 1 / P_ {2}} ceil}$ және ${displaystyle L = lceil P_ {1} ^ {- k} ceil = O (n ^ {ho} P_ {1} ^ {- 1})}$ , қайда ${displaystyle ho = {log P_ {1} журналдың P_ үстінен {2}}}$ . Содан кейін келесі өнімділік кепілдіктері бар:

алдын ала өңдеу уақыты: ${displaystyle O (n ^ {1 + ho} P_ {1} ^ {- 1} kt)}$ ;
ғарыш: ${displaystyle O (n ^ {1 + ho} P_ {1} ^ {- 1})}$ , деректер нүктелерін сақтауға арналған орын;
сұрау уақыты: ${displaystyle O (n ^ {ho} P_ {1} ^ {- 1} (kt + d))}$ ;

Сондай-ақ қараңыз

Пайдаланылған әдебиеттер

^ ^а ^б ^c ^г. Раджараман, А .; Ульман, Дж. (2010). «Массивтік деректерді өндіру, 3-б.».
^ Чжао, Кан; Лу, Хонтао; Mei, Jincheng (2014). «Хэштеуді сақтайтын аймақ». 2874–2880 беттер.
^ Цай, И-Хсуан; Янг, Мин-Хсуан (қазан 2014). «Хэштеуді сақтайтын аймақ». 2014 IEEE бейнелерді өңдеу жөніндегі халықаралық конференция (ICIP). 2988–2992 бет. дои:10.1109 / ICIP.2014.7025604. ISBN 978-1-4799-5751-4. ISSN 1522-4880. S2CID 8024458.
^ Джонис, А .; Ындық, П.; Мотвани, Р. (1999). «Хэштеу арқылы жоғары өлшемдердегі ұқсастықты іздеу». 25-ші өте үлкен мәліметтер базасы (VLDB) конференциясының материалдары.
^ ^а ^б Индик, Пиотр.; Мотвани, Раджеев. (1998). «Шамамен жақын көршілер: өлшемділіктің қарғысынан арылуға қарай».. Есептеу теориясы бойынша 30-шы симпозиум материалдары.
^ ^а ^б Чарикар, Муса С. (2002). «Дөңгелектеу алгоритмдеріндегі ұқсастықты бағалау әдістері». Есептеулер теориясы бойынша 34-ші ACM симпозиумының материалдары. 380-388 бет. CiteSeerX 10.1.1.147.4064. дои:10.1145/509907.509965.
^ Дас, Абхинандан С .; т.б. (2007), «Google жаңалықтарын жекелендіру: ауқымды интерактивті сүзу», Дүниежүзілік желідегі 16-шы халықаралық конференция материалдары: 271, дои:10.1145/1242572.1242610, ISBN 9781595936547, S2CID 207163129.
^ Кога, Хисаши; Тетсуо Ишибаши; Тошинори Ватанабе (2007), «Орналасқан жерді сезінетін хэштеуді қолдану арқылы жылдам агломеративті иерархиялық кластерлеу алгоритмі», Білім және ақпараттық жүйелер, 12 (1): 25–53, дои:10.1007 / s10115-006-0027-5, S2CID 4613827.
^ Кочес, Майкл; Моу, Хао (2015), «Twister Tries: Сызықтық уақыттағы орташа қашықтық үшін шамамен иерархиялық агломеративті кластерлеу», SIGMOD '15 процедурасы 2015 ACM SIGMOD деректерді басқару жөніндегі халықаралық конференция материалдары: 505–517, дои:10.1145/2723372.2751521, ISBN 9781450327589, S2CID 14414777.
^ Бринза, Думитру; т.б. (2010), «Геном бойынша ассоциация зерттеулерінде ген-гендердің өзара әрекеттесуін жедел анықтау», Биоинформатика, 26 (22): 2856–2862, дои:10.1093 / биоинформатика / btq529, PMC 3493125, PMID 20871107
^ dejavu - саусақ іздерін аударту және Python-да тану, 2018-12-19
^ Алуч, Күнеш; Өзсу, М.Тамер; Дауджи, Хузайма (2018), «Tunable-LSH көмегімен RDF дерекқорларын құру», VLDB журналы, 28 (2): 173–195, дои:10.1007 / s00778-018-0530-9, S2CID 53695535
^ Чен, Бейди; Медини, Тарун; Фарвелл, Джеймс; Гобриэль, Самех; Тай, Чарли; Шривастава, Аншумали (2020-02-29). «SLIDE: Ірі масштабтағы терең оқыту жүйелері үшін аппараттық жеделдетудің ақылды алгоритмдерін қорғау». arXiv:1903.03129 [cs.DC ].
^ Broder, A.Z.; Чарикар, М.; Фриз, А.М.; Миценмахер, М. (1998). «Минималды тәуелсіз ауыстырулар». Есептеу теориясы бойынша ACM жыл сайынғы симпозиумының материалдары. 327–336 бб. CiteSeerX 10.1.1.409.9220. дои:10.1145/276698.276781. Алынған 2007-11-14.
^ Такей, Ю .; Итох Т .; Шинозаки, Т. «Дәл минималды тәуелсіз ауыстырудың оңтайлы құрылысы». Техникалық есеп COMP98-62, IEICE, 1998 ж.
^ Матушек, Дж .; Стоякович, М. (2002). «Пермутаттардың шектеулі минималды тәуелсіздігі туралы». Алдын ала басып шығару. Алынған 2007-11-14.
^ Сакс, М.; Сринивасан, А .; Чжоу, С .; Цукерман, Д. (2000). «Сәйкессіздіктер жиынтығы шамамен минималды тәуелсіз ауыстыру отбасыларына әкеледі». Ақпаратты өңдеу хаттары. 73 (1–2): 29–32. CiteSeerX 10.1.1.20.8264. дои:10.1016 / S0020-0190 (99) 00163-5. Алынған 2007-11-14.
^ Дамиани; т.б. (2004). «Спамдарды анықтауға арналған дайджестке негізделген ашық әдіс» (PDF). Алынған 2013-09-01.
^ Оливер; т.б. (2013). «TLSH - жергілікті сезімтал хэш». 4-ші киберқылмыс және сенімді компьютерлік семинар. Алынған 2015-04-06.
^ «TLSH». Алынған 2014-04-10.
^ Александр Андони; Ындық, П. (2008). «Үлкен өлшемдердегі жақын көршінің жақын оптималды хэштеу алгоритмдері». ACM байланысы. 51 (1): 117–122. CiteSeerX 10.1.1.226.6905. дои:10.1145/1327452.1327494. S2CID 6468963.
^ Датар, М .; Immorlica, Н.; Ындық, П.; Миррокни, В.С. (2004). «Тұрақты үлестіруге негізделген локализацияны сезгіштікпен тазарту схемасы». Есептеу геометриясы бойынша симпозиум материалдары.
^ Паулеве, Л .; Джегу, Х .; Амсалег, Л. (2010). «Локалды хэштеу: хэш функцияларының түрлерін және сұрау тетіктерін салыстыру». Үлгіні тану хаттары. 31 (11): 1348–1358. дои:10.1016 / j.patrec.2010.04.004.
^ Горман, Джеймс және Джеймс Р. «Үлкен корпорацияларға үлестірім үлестірімінің ұқсастығы.» Компьютерлік лингвистика бойынша 21-ші халықаралық конференция мен компьютерлік лингвистика қауымдастығының 44-ші жыл сайынғы мәжілісінің материалдары. Компьютерлік лингвистика қауымдастығы, 2006 ж.

Әрі қарай оқу

Samet, H. (2006) Көп өлшемді және метрикалық мәліметтер құрылымдарының негіздері. Морган Кауфман. ISBN 0-12-369446-9

Индик, Пиотр; Мотвани, Раджеев; Рагхаван, Прабхакар; Вемпала, Сантош (1997). «Көп өлшемді кеңістіктегі хэштеуді сақтайтын». Есептеулер теориясы бойынша жиырма тоғызыншы ACM симпозиумының материалдары. 618–625 бет. CiteSeerX 10.1.1.50.4927. дои:10.1145/258533.258656. ISBN 978-0-89791-888-6. S2CID 15693787.
Чин, Эндрю (1994). «Жалпы мақсаттағы параллельді есептеу үшін орынды сақтайтын хэш функциялары» (PDF). Алгоритмика. 12 (2–3): 170–181. дои:10.1007 / BF01185209. S2CID 18108051.

Сыртқы сілтемелер

Алекс Андонидің LSH-тің басты беті
LSHKIT: C ++ локальды сезімтал хэштеу кітапханасы
Rytis арқылы табандылықты қолдайтын Python Locational Sensitive Hashing кітапханасы
Caltech үлкен масштабты кескінді іздеу құралдар тақтасы: Kd-Trees, иерархиялық K-құралдары және Inverted File іздеу алгоритмдерінен басқа бірнеше LSH хэш функцияларын жүзеге асыратын Matlab құралдар жинағы.
Slash: C ++ LSH кітапханасы, сфералық LSH-ны Терасава, К., Танака, Ю
LSHBOX: суретті үлкен көлемде іздеу үшін орналасуға сезімтал хэштеудің ашық көзі C ++ құралдар жинағы, сонымен қатар Python және MATLAB қолдайды.
SRS: p-тұрақты кездейсоқ проекциялау негізінде C ++ жадында, кеңістікті тиімді, жақын маңдағы көршінің сұранысын өңдеу алгоритмін жүзеге асыру
Github-тағы TLSH ашық көзі
Node.js модулі ретінде жинақталған TLSH (Trend Micro Locality Sensitive Hashing) JavaScript порты
TLSH Java порты (Trend Micro Locational Sensitive Hashing) мата пакеті ретінде жинақталған

[MOMD-1] а ^б ^c ^г. Раджараман, А .; Ульман, Дж. (2010). «Массивтік деректерді өндіру, 3-б.».

[2] Чжао, Кан; Лу, Хонтао; Mei, Jincheng (2014). «Хэштеуді сақтайтын аймақ». 2874–2880 беттер.

[3] Цай, И-Хсуан; Янг, Мин-Хсуан (қазан 2014). «Хэштеуді сақтайтын аймақ». 2014 IEEE бейнелерді өңдеу жөніндегі халықаралық конференция (ICIP). 2988–2992 бет. дои:10.1109 / ICIP.2014.7025604. ISBN 978-1-4799-5751-4. ISSN 1522-4880. S2CID 8024458.

[GIM1999-4] Джонис, А .; Ындық, П.; Мотвани, Р. (1999). «Хэштеу арқылы жоғары өлшемдердегі ұқсастықты іздеу». 25-ші өте үлкен мәліметтер базасы (VLDB) конференциясының материалдары.

[IndykMotwani98-5] а ^б Индик, Пиотр.; Мотвани, Раджеев. (1998). «Шамамен жақын көршілер: өлшемділіктің қарғысынан арылуға қарай».. Есептеу теориясы бойынша 30-шы симпозиум материалдары.

[Charikar2002-6] а ^б Чарикар, Муса С. (2002). «Дөңгелектеу алгоритмдеріндегі ұқсастықты бағалау әдістері». Есептеулер теориясы бойынша 34-ші ACM симпозиумының материалдары. 380-388 бет. CiteSeerX 10.1.1.147.4064. дои:10.1145/509907.509965.

[7] Дас, Абхинандан С .; т.б. (2007), «Google жаңалықтарын жекелендіру: ауқымды интерактивті сүзу», Дүниежүзілік желідегі 16-шы халықаралық конференция материалдары: 271, дои:10.1145/1242572.1242610, ISBN 9781595936547, S2CID 207163129.

[8] Кога, Хисаши; Тетсуо Ишибаши; Тошинори Ватанабе (2007), «Орналасқан жерді сезінетін хэштеуді қолдану арқылы жылдам агломеративті иерархиялық кластерлеу алгоритмі», Білім және ақпараттық жүйелер, 12 (1): 25–53, дои:10.1007 / s10115-006-0027-5, S2CID 4613827.

[9] Кочес, Майкл; Моу, Хао (2015), «Twister Tries: Сызықтық уақыттағы орташа қашықтық үшін шамамен иерархиялық агломеративті кластерлеу», SIGMOD '15 процедурасы 2015 ACM SIGMOD деректерді басқару жөніндегі халықаралық конференция материалдары: 505–517, дои:10.1145/2723372.2751521, ISBN 9781450327589, S2CID 14414777.

[10] Бринза, Думитру; т.б. (2010), «Геном бойынша ассоциация зерттеулерінде ген-гендердің өзара әрекеттесуін жедел анықтау», Биоинформатика, 26 (22): 2856–2862, дои:10.1093 / биоинформатика / btq529, PMC 3493125, PMID 20871107

[11] dejavu - саусақ іздерін аударту және Python-да тану, 2018-12-19

[12] Алуч, Күнеш; Өзсу, М.Тамер; Дауджи, Хузайма (2018), «Tunable-LSH көмегімен RDF дерекқорларын құру», VLDB журналы, 28 (2): 173–195, дои:10.1007 / s00778-018-0530-9, S2CID 53695535

[13] Чен, Бейди; Медини, Тарун; Фарвелл, Джеймс; Гобриэль, Самех; Тай, Чарли; Шривастава, Аншумали (2020-02-29). «SLIDE: Ірі масштабтағы терең оқыту жүйелері үшін аппараттық жеделдетудің ақылды алгоритмдерін қорғау». arXiv:1903.03129 [cs.DC ].

[Broder1998-14] Broder, A.Z.; Чарикар, М.; Фриз, А.М.; Миценмахер, М. (1998). «Минималды тәуелсіз ауыстырулар». Есептеу теориясы бойынша ACM жыл сайынғы симпозиумының материалдары. 327–336 бб. CiteSeerX 10.1.1.409.9220. дои:10.1145/276698.276781. Алынған 2007-11-14.

[15] Такей, Ю .; Итох Т .; Шинозаки, Т. «Дәл минималды тәуелсіз ауыстырудың оңтайлы құрылысы». Техникалық есеп COMP98-62, IEICE, 1998 ж.

[Matousek2002-16] Матушек, Дж .; Стоякович, М. (2002). «Пермутаттардың шектеулі минималды тәуелсіздігі туралы». Алдын ала басып шығару. Алынған 2007-11-14.

[Saks2000-17] Сакс, М.; Сринивасан, А .; Чжоу, С .; Цукерман, Д. (2000). «Сәйкессіздіктер жиынтығы шамамен минималды тәуелсіз ауыстыру отбасыларына әкеледі». Ақпаратты өңдеу хаттары. 73 (1–2): 29–32. CiteSeerX 10.1.1.20.8264. дои:10.1016 / S0020-0190 (99) 00163-5. Алынған 2007-11-14.

[18] Дамиани; т.б. (2004). «Спамдарды анықтауға арналған дайджестке негізделген ашық әдіс» (PDF). Алынған 2013-09-01.

[19] Оливер; т.б. (2013). «TLSH - жергілікті сезімтал хэш». 4-ші киберқылмыс және сенімді компьютерлік семинар. Алынған 2015-04-06.

[20] «TLSH». Алынған 2014-04-10.

[Andoni2008-21] Александр Андони; Ындық, П. (2008). «Үлкен өлшемдердегі жақын көршінің жақын оптималды хэштеу алгоритмдері». ACM байланысы. 51 (1): 117–122. CiteSeerX 10.1.1.226.6905. дои:10.1145/1327452.1327494. S2CID 6468963.

[DIIM04-22] Датар, М .; Immorlica, Н.; Ындық, П.; Миррокни, В.С. (2004). «Тұрақты үлестіруге негізделген локализацияны сезгіштікпен тазарту схемасы». Есептеу геометриясы бойынша симпозиум материалдары.

[PJA10-23] Паулеве, Л .; Джегу, Х .; Амсалег, Л. (2010). «Локалды хэштеу: хэш функцияларының түрлерін және сұрау тетіктерін салыстыру». Үлгіні тану хаттары. 31 (11): 1348–1358. дои:10.1016 / j.patrec.2010.04.004.

[24] Горман, Джеймс және Джеймс Р. «Үлкен корпорацияларға үлестірім үлестірімінің ұқсастығы.» Компьютерлік лингвистика бойынша 21-ші халықаралық конференция мен компьютерлік лингвистика қауымдастығының 44-ші жыл сайынғы мәжілісінің материалдары. Компьютерлік лингвистика қауымдастығы, 2006 ж.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]