一般社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,INFORMATION AND COMMUNICATION ENGINEERS

信学技報
IEICE Technical Report
SS2017-74 (2018-03)‫ॴہ‬ੑӶහ‫ܕ‬ϋογϡΛ༻͍ͨίʔυΫϩʔϯ‫ݕ‬ग़ͷͨΊͷύϥϝʔλܾఆख๏ಙҪ ᠳ‫†ޜ‬٢ా ଇ༟††ቐԸಬ††† Ҫ্ ࠀ࿠†† େࡕେֶେֶӃ৘ใՊֶ‫ڀݚ‬Պ, ˟ 560-0871 େࡕ෎ਧాࢢࢁాٰ 1-5†† ໊‫ݹ‬԰େֶେֶӃ৘ใֶ‫ڀݚ‬Պ, ˟ 464-8601 Ѫ஌‫ݹ໊ݝ‬԰ࢢઍछ۠ෆ࿝ொ††† ಸྑઌ୺Պֶٕज़େֶӃେֶ৘ใՊֶ‫ڀݚ‬Պ, ˟ 630-0192 ಸྑ‫ݝ‬ੜۨࢢߴࢁொ 8916-5
E-mail: †{s-tokui,inoue}@ist.osaka-u.ac.jp, ††yoshida@ertl.jp, †††choi@is.naist.jp͋Β·͠ ‫ॴہ‬ੑӶහ‫ܕ‬ϋογϡ (LSH) ͱ͸ɼߴ࣍‫ͳݩ‬σʔλΛ֬཰తʹϋογϡ͠ɼۙ๣఺Λ‫͚ͭݟ‬ΔΞϧΰϦζϜͰ͋ΔɽΫϩʔϯ‫ݕ‬ग़ʹ͓͍ͯ LSH ͷॲཧʹେ͖ͳ࣌ؒΛ઎Ί͓ͯΓɼLSH ͷॲཧ଎౓Λ޲্ͤ͞Δ͜ͱ͕‫ٻ‬ΊΒΕ͍ͯΔɽຊ‫Ͱڀݚ‬͸ɼ‫ݕ‬ग़ਫ਼౓Λม͑ͣʹߴ଎ʹ LSH ͷॲཧΛ͢ΔͨΊʹɼLSH ʹ༩͑ΔύϥϝʔλΛɼର৅ιʔείʔυ͔Βܾఆ͢Δख๏ΛఏҊ͢ΔɽΩʔϫʔυίʔυΫϩʔϯɼ‫ॴہ‬ੑӶහ‫ܕ‬ϋογϡɼίʔυϒϩοΫ

A Determination Method of Locality Sensitive Hashing Parameters
for Code Clone Detection
Shogo TOKUI† , Norihiro YOSHIDA†† , Eunjong CHOI††† , and Katsuro INOUE†† Graduate School of Information Science and Technology, Osaka University, 1-5, Yamadaoka, Suita, Osaka,565-0871, Japan†† Graduate School of Informatics, Nagoya University, Furo-cho, Chikusa-ku, Nagoya, Aichi, 464-8601, Japan††† Graduate School of Information Science, Nara Institute of Science and Technology, 8916-5, Takayama,Ikoma, Nara, 630-0192,Japan
E-mail: †{s-tokui,inoue}@ist.osaka-u.ac.jp, ††yoshida@ertl.jp, †††choi@is.naist.jp
Abstract LSH (Locality-Sensitive Hashing) is a near neighbor search algorithm that performs probabilistic hashing of high-dimensional data. For reducing the detection time of code clones, the execution time of LSH needs tobe speeded up. In this study, we propose an approach to determine LSH parameters based on source code analysis
in order to not only speed up code clone detection but also keep the preciseness of it.
Key words Code Cloneɼ Locality-Sensitive HashingɼCode blockཧ͕ྨࣅͨ͠ίʔυϒϩοΫ୯ҐͷίʔυΫϩʔϯʢϒϩοΫΫ

1. · ͑ ͕ ͖ϩʔϯʣΛ‫ݕ‬ग़͢ΔϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ [3] ΛఏҊ͠ɼ༗ޮιϑτ΢ΣΞͷอकʹ͓͚Δ໰୊ͷ 1 ͭͱͯ͠ɼίʔυΫੑΛ֬ೝͨ͠ɽϒϩοΫΫϩʔϯ‫ݕ‬ग़๏Ͱ͸ɼ·ͣɼ৘ใ‫ٕࡧݕ‬ϩʔϯ͕ࢦఠ͞Ε͍ͯΔ [1], [2]ɽίʔυΫϩʔϯͱ͸ɼιʔεज़ͷҰछͰ͋Δ TF-IDF (Term Frequency-Inverse Documentίʔυதʹ‫·ؚ‬ΕΔ‫ʹ͍ޓ‬Ұக·ͨ͸ྨࣅͨ͠෦෼Λ࣋ͭίʔFrequency) ๏ [4] Λ༻͍ͯɼιʔείʔυதͷࣝผࢠ΍༧໿‫ޠ‬υยͷ͜ͱͰ͋ΓɼҰൠతʹɼίʔυΫϩʔϯͷଘࡏ͸ιϑτʹར༻͞ΕΔ୯‫ʹޠ‬ରͯ͠ॏΈ෇͚Λߦ͍ɼ֤ίʔυϒϩοΫ΢ΣΞͷอकΛࠔ೉ʹ͢Δͱ‫ݴ‬ΘΕ͍ͯΔɽେ‫ن‬໛ͷιʔεΛಛ௃ϕΫτϧʹม‫͢׵‬Δɽಛ௃ϕΫτϧؒͷ༨‫͕౓ࣅྨݭ‬ᮢίʔυ͔Β͸ଟ͘ͷίʔυΫϩʔϯ͕‫ݕ‬ग़͞ΕΔͨΊɼख࡞‫ۀ‬஋Ҏ্ͷΫϩʔϯϖΞΛɼ‫ॴہ‬ੑӶහ‫ܕ‬ϋογϡ (LSH) [5] ΛͰͦΕΒΛ؅ཧ͢Δ͜ͱ͸ࠔ೉Ͱ͋Δɽͦ͜ͰɼίʔυΫϩʔ༻͍ͨྨࣅ୳ࡧʹΑͬͯߴ଎ʹ‫ٻ‬ΊɼίʔυΫϩʔϯͷ‫ݕ‬ग़ΛϯΛࣗಈతʹ‫ݕ‬ग़͢Δ͜ͱΛ໨తͱͨ͠͞·͟·ͳίʔυΫߦ͏ɽϩʔϯ‫ݕ‬ग़ख๏͕ఏҊ͞Ε͍ͯΔɽ

͔͠͠ɼ20MLOC ͷେ‫ن‬໛ϓϩδΣΫτʹରͯ͠ϒϩοΫԣҪΒ͸৘ใ‫ٕࡧݕ‬ज़Λར༻͢Δ͜ͱʹΑͬͯɼҙຯతʹॲΫϩʔϯ‫ݕ‬ग़๏ΛదԠͨ͠৔߹ɼ֤εςοϓຖʹ͔͔Δ࣌ؒΛ

― 57 ―
This article is a technical report without peer review, and its polished and/or extended version may be published elsewhere.
Copyright ©2018 by IEICEද1‫ܭ‬ଌͨ͠ͱ͜Ζɼ21 ෼ͷ‫ݕ‬ग़࣌ؒͷ಺ɼಛ௃ϕΫτϧؒͷྨࣅϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ͷ֤εςοϓʹ͔͔Δ࣌ؒ୳ࡧʹ 18 ෼͔͔͍ͬͯͨࣄΛ֬ೝͨ͠ɽLSH Λ༻͍ͨྨࣅ୳ࡧʹ໿ 90%ͷ͕͔͔͓࣌ؒͬͯΓɼશମͷ‫ؒ࣌ࢉܭ‬Λ࡟‫͢ݮ‬ΔϓϩδΣΫτ໊ߦఔ‫[ ؒ࣌ࢉܭ‬s]૬ର࣌ؒͨΊʹɼྨࣅ୳ࡧͷߴ଎Խ͕ඞཁͱͳΔɽͨͩ͠ɼLSH ͸ɼ‫ܭ‬

PostgreSQL 10.1

STEP1

4.20.06

STEP2

0.40.01ࢉ࣌ؒͱ୳ࡧਫ਼౓͕τϨʔυΦϑͷؔ܎ʹ͋Δɽ
ͦ͜Ͱɼຊ‫Ͱڀݚ‬͸ɼϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ʹ͓͍ͯߴ଎
ԽΛ͢ΔͨΊͷɼLSH ͷύϥϝʔλܾఆख๏ΛఏҊ͢ΔɽධՁ

STEP3

0.20.01

STEP4

65.6

0.93

શߦఔ

70.4

1.00

࣮‫Ͱݧ‬͸ɼ͜Ε·ͰϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ʹͯ࢖༻͞Ε͍ͯ

Linux Kernel 4.14 STEP1

157.70.12ͨύϥϝʔλͱɼຊख๏Λ༻͍ܾͯఆͨ͠ύϥϝʔλΛϒϩο

STEP2

1.30.01ΫΫϩʔϯ‫ݕ‬ग़๏ʹద༻ͨ͠৔߹ͷɼྨࣅ୳ࡧʹඅ΍࣌ؒ͢ͱSTEP35.8

0.01୳ࡧਫ਼౓ͷ‫͔఺؍‬ΒൺֱΛߦͬͨɽSTEP4

1098.10.87

શߦఔ

1262.91.00

Ҏ߱ɼ2 ষͰ͸ɼLSH ϥΠϒϥϦͷ 1 ͭͰ͋Δ FALCONN[6]ʢ஫ 1ʣͱϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ͷΞϧΰϦζϜʹ͍ͭͯड़΂Δɽ3 ষͰ͸ɼFALCONN ʹ༩͑Δύϥϝʔλͷछྨͱɼຊ‫ݚ‬Λ೚ҙͷճ਺࣮ߦ‫Ͱڀ‬ఏҊ͢Δύϥϝʔλͷܾఆख๏Λड़΂Δɽ4 ষͰ͸ɼҰ෦

STEP C ୯Ґ‫ٿ‬ΛҰఆͷ೚ҙͷେ͖͞ʹ෼ׂ͠ɼͦͷ఺͕ͷύϥϝʔλʹ͍ͭͯɼ୳ࡧ࣌ؒ΍࠶‫ݱ‬ੑʹ༩͑ΔӨ‫ڹ‬ͷௐࠪ

‫·ؚ‬ΕΔ۠ըͷϥϕϧΛϋογϡ஋ͱͯ͠औಘ

Λߦ͏ɽ5 ষͰ͸ɼຊख๏ͷධՁ࣮‫͍ͯͭʹݧ‬ड़΂ɼ6 ষͰߟ

STEP A ͸ϝϞϦ࡟‫ߴͱݮ‬଎ԽͷͨΊʹߦ͏ɽSTEP B, C࡯Λߦ͏ɽ࠷‫ʹޙ‬ɼ7 ষͰ·ͱΊͱࠓ‫ޙ‬ͷ՝୊ʹ͍ͭͯड़΂Δɽ͸ Cross-Polytope LSH ʹ‫͋Ͱ࡞ૢ͍ͨͮج‬ΔɽFALCONNͷϋογϡؔ਺ʹ͓͍ͯɼ‫ ཭ڑ‬r > 0 ʹର͠ p − q < r Λຬ

2. ؔ ࿈ ‫ڀ ݚ‬ͨ͢ p, q ͕িಥ͢Δ֬཰͸ࣜ 1 Λຬͨ͢ɽ

2. 1 ۙࣅ࠷ۙ๣୳ࡧ໰୊༻ϥΠϒϥϦ FALCONNAndoni Β͸ɼେ‫ن‬໛ߴ࣍‫ͳݩ‬ϕΫτϧू߹ͷۙࣅ࠷ۙ๣୳ࡧ໰୊Λղͨ͘Ίͷ LSH Ͱ͋Δ FALCONN ΛఏҊͨ͠ [6]ɽFALCONN ͸ɼ‫ࢉܭ‬ίετ‫ۭؒͼٴ‬ίετʹؔͯ͠༏Εͨ
Cross-Polytope LSH ʹ‫͍ͯͮج‬ɼ‫ػ‬ցֶशΛ༻͍ͨ࣍‫ݩ‬ѹॖ΍ɼ୳ࡧਫ਼౓Λ޲্ͤ͞ΔͨΊͷ multi-probe LSH [7] Λ༻͍

ln1r2· ln d + Or (ln ln d)=P r(p, q)
4 − r2(1)2. 2 ϒϩοΫΫϩʔϯ‫ݕ‬ग़๏
2. 2. 1 ϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ͷΞϧΰϦζϜԣҪΒ͸ɼ৘ใ‫ٕࡧݕ‬ज़Λར༻͢Δ͜ͱʹΑͬͯɼҙຯతʹॲཧ͕ྨࣅͨ͠ϒϩοΫΫϩʔϯΛ‫ݕ‬ग़͢Δख๏ΛఏҊͨ͠ [3]ɽͯɼେ‫ن‬໛ߴ࣍‫ࡧ୳ͳݩ‬໰୊ʹରԠՄೳʹ͍ͯ͠ΔɽϒϩοΫΫϩʔϯ‫ݕ‬ग़๏Ͱ͸ɼϒϩοΫ୯Ґͷ֤ίʔυยʹର

2. 1. 1 ‫ॴہ‬ੑӶහ‫ܕ‬ϋογϡ (LSH) ͷఆٛ
LSH (Locality-Sensitive Hashingʣͱ͸ɼϋογϡؔ਺Λ༻͍ͯۙ๣఺Λ୳ࡧ͢ΔΞϧΰϦζϜͰ͋Δ [5] Ͱ͸ɼσʔλؒͷ‫ʹ͍͕࣌ۙ཭ڑ‬ϋογϡ஋͕Ұக͢Δɽਖ਼֬ͳఆٛΛҎԼͷ͠ϕΫτϧԽΛߦ͏ͨΊɼίʔυยಉ͕࢜‫׬‬શʹҰக͢ΔλΠ
ϓ 1 ͔Βҙຯతʹྨࣅ͢ΔλΠϓ 4 ·ͰͷίʔυΫϩʔϯ [10]Λ‫ݕ‬ग़Ͱ͖ΔɽϒϩοΫΫϩʔϯ‫ݕ‬ग़๏͸ҎԼͷεςοϓͰ࣮ߦ͞ΕΔɽ௨ΓͰ͋ΔɽϊϧϜ  ·  ͕ఆٛ͞Εͨ d ࣍‫্ۭؒݩ‬ͷ೚ҙͷ 2 ఺ p, q ΛͱΔɽ‫ ཭ڑ‬r ಺ͷ 2 ఺Λ‫ٻ‬ΊΔͨΊͷ LSH ͷϋογϡؔ਺͸ɼ
͋Δ c > 1 ͱ P1 > P2 Λຬͨ֬͢཰ P1 , P2 ʹରͯ͠ɼҎԼͷ2 ͭͷ৚݅Λຬͨ͢ɽ

STEP 1 ߏจղੳΛߦ͍ɼந৅ߏจ໦Λੜ੒
STEP 2 ந৅ߏจ໦͔ΒίʔυϒϩοΫͱ୯‫ޠ‬Λநग़
STEP 3 TF-IDF ๏ʹΑΓɼϒϩοΫ୯Ґͷಛ௃ϕΫτϧΛ‫ࢉܭ‬STEP 4 FALCONN Λར༻͠ɼྨࣅϖΞͷ୳ࡧ (Ҏ߱ɼྨࣅʦఆٛ 1ʧ p − q < r ⇒ P r(p, q) > P1୳ࡧͱ͢Δ) Λߦ͍ɼΫϩʔϯϖΞΛ‫ݕ‬ग़ʦఆٛ 2ʧ p − q > cr ⇒ P r(p, q) < P2P r(p, q) ͱ͸ p ͱ q ͕ಉ͡ϋογϡ஋ΛऔΔ֬཰Λද͠ɼ
LSH Ͱ͸িಥ֬཰ͱ‫ݺ‬͹ΕΔɽ

STEP4 ͷྨࣅ୳ࡧ͸ҎԼͷεςοϓͰ࣮ߦ͞ΕΔɽ
STEP4-1 ϒϩοΫશͯͷಛ௃ϕΫτϧ͔Β FALCONNͷϋογϡؔ਺Λ༻͍ͯϋογϡςʔϒϧΛ࡞੒

2. 1. 2 FALCONN ͷϋογϡؔ਺Andoni Β͕ఏҊ͢Δ FALCONN ͸ɼ୯Ґ‫ٿ‬໘্ͷϢʔΫϦου‫ʹ཭ڑ‬ରͯۙ͠ࣅ࠷ۙ๣୳ࡧΛߦ͏ͨΊɼ༨‫ʹ౓ࣅྨݭ‬΋ରԠ͍ͯ͠Δɽ༨‫౓ࣅྨݭ‬Λ༻͍Δ TF-IDF ๏΍ը૾ͷྨࣅ୳ࡧΛߦ͏৔߹ʹద͍ͯ͠Δɽ୯Ґ‫ٿ‬໘্ͷ఺ͷ FALCONNͷϋογϡ஋͸ҎԼͷεςοϓͰ‫ٻ‬ΊΒΕΔɽ

STEP A Feature Hashing [8] Λ༻͍ͯ೚ҙͷ࣍‫ʹݩ‬ѹॖ
STEP B ߴ଎ΞμϚʔϧม‫׵‬ΛԠ༻ٖͨ͠ࣅϥϯμϜճస [9]STEP4-2 ಛ௃ϕΫτϧຖʹɼSTEP4-3ɼ4-4ɼ4-5 Λ࣮ߦ
STEP4-3 ಛ௃ϕΫτϧͷϋογϡ஋Λ‫ٻ‬Ίɼϋογϡςʔϒϧʹ͓͍ͯিಥ͢ΔϕΫτϧΛ୳ࡧɽ·ͨɼmulti-probeLSH ʹ‫͖ͮج‬ɼ͍ۙϋογϡ஋ͷϕΫτϧ΋୳ࡧSTEP4-4 ‫͚ͨͭݟ‬શͯͷۙ๣ϕΫτϧͱͷ‫཭ڑ‬Λ‫͠ࢉܭ‬ɼᮢ஋Ҏ಺ͷϕΫτϧͷίʔυยΛΫϩʔϯϖΞͱͯ͠‫ݕ‬ग़

2. 2. 2 ϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ͷ࢖༻ͷ໰୊఺
2. 2. 1 અͰ͸ɼϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ͷΞϧΰϦζϜʹ͍ͭʢ஫ 1ʣɿhttps://falconn-lib.org/― 58 ―㼤㻌㻩㻌㼧㼍㻝㻘䈈㻘㼍㼚㼩㼥㻌㻩㻌㼧㼎㻝㻘䈈㻘㼎㼚㼩≉ᚩ䝧䜽䝖䝹㼝㻌㻩㻌㼧㼝㻝㻘䈈㻘㼝㼚㼩㻝 㼤㻞㻟 㼥㻠䈈 䈈䈈≉ᚩ䝧䜽䝖䝹㞟ྜ䝝䝑䝅䝳䝔䞊䝤䝹㻿㼀㻱㻼㻠㻙㻝㻝㻞 㼥㻟 㼤㻠䈈䈈㻝 㼥㻞㻟䈈㻠 㼤䈈䈈Ϯ≉ᚩ䝧䜽䝖䝹㼝䛾㏆ഐⅬ䜽䝻䞊䞁䝨䜰䛾≉ᚩ䝧䜽䝖䝹㼤㼥㼥ਤ1䈈㻿㼀㻱㻼㻠㻙㻞㻿㼀㻱㻼㻠㻙㻟ྨࣅ୳ࡧͷ࣮ߦϑϩʔͯઆ໌ͨ͠ɽ֤εςοϓʹ͔͔Δ࣌ؒΛ PostgreSQL 10.1ʢ஫ 2ʣ
ʢ஫ 3ʣ

ද 2 FALCONN ʹ༩͑Δύϥϝʔλύϥϝʔλ໊಺༰ͨ݁ՌΛද 1 ʹࣔ͢ɽ͜ͷ݁Ռͱ LSH ͕֬཰తͳΞϧΰϦζ

lsh_familyϋογϡؔ਺ͷछྨϜͰ͋Δࣄ͔ΒɼϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ʹରͯ͠ҎԼͷ໰୊kςʔϒϧຖͷϋογϡؔ਺ͷ਺ͱ Linux Kernel 4.14

ͷ 2 ͭͷϓϩδΣΫτʹରͯ͠‫ܭ‬ଌ͠

stroge_hash_table ϋογϡςʔϒϧͷσʔλߏ଄఺͕‫͛ڍ‬ΒΕΔɽ

1 ͭ໨͸ɼϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ͷ STEP4 ʹ͔͔Δ࣌ؒ

ThreadsεϨουͷ਺

distance_function‫਺ؔ཭ڑ‬ͷछྨ͕‫ݕ‬ग़શମͷ໿ 90%Λ઎Ί͍ͯΔ఺Ͱ͋Δɽ࣮ࡍɼද 1 ͷ݁Ռ

num_rotationsٖࣅϥϯμϜճసͷճ਺͔ΒɼͦΕͧΕ STEP4 ʹ໿ 90%ͷ͕͔͔͍࣌ؒͬͯΔɽFHD࣍‫ݩ‬ѹॖ‫ޙ‬ͷ࣍‫਺ݩ‬

2 ͭ໨͸ɼSTEP4 ʹ͓͍ͯ LSH ͕༻͍ΔͨΊɼΫϩʔϯϖprobesۙ઀όέοτͷ୳ࡧ਺Ξͷ‫ݕ‬ग़࿙ΕΛ‫͢͜ى‬Մೳੑ͕͋Δ఺Ͱ͋Δɽ࣮ࡍɼSTEP4LCD

cross-polytope LSH Ͱ༻͍Δ‫ٿ‬໘ͷ෼ׂ਺ʹ͓͍ͯ LSH Λ༻͍ͣʹ‫ٻ‬ΊͨΫϩʔϯϖΞͷ਺ͱɼLSH Λlϋογϡςʔϒϧͷ਺༻͍ͯ‫ٻ‬ΊͨΫϩʔϯϖΞͷ਺Λൺֱͨ݁͠Ռɼ5%ఔ౓ͷ‫ݕ‬ग़࿙ΕΛ‫͍ͨͯ͜͠ى‬ɽ

3. 1 ύϥϝʔλܾఆͷํ਑͋ΔϕΫτϧʹର͠‫͕཭ڑ‬ᮢ஋Ҏ಺ͷϕΫτϧΛ‫ٻ‬ΊΔ࣌ɼ

3. ύϥϝʔλܾఆख๏શͯͷ‫཭ڑ‬Λ‫͢ࢉܭ‬ΔલʹɼFALCONN ʹΑΓᮢ஋Ҏ಺ͷϕຊ‫Ͱڀݚ‬͸ɼ2. 2. 2 અͰड़΂ͨ 2 ͭͷ໰୊఺Λ౿·͑ͯɼϒΫτϧͷީิͱͯۙ͠๣ϕΫτϧΛ‫ٻ‬Ίɼ‫཭ڑ‬Λ‫͢ࢉܭ‬ΔίεϩοΫΫϩʔϯ‫ݕ‬ग़๏ʹ͓͚Δ STEP4 (ྨࣅ୳ࡧ) ͷվળΛߦτΛ࡟‫͢ݮ‬Δɽۙ๣ϕΫτϧʹ‫·ؚ‬Εͳ͍ϕΫτϧ͸ɼᮢ஋Ҏ͏ͨΊʹɼྨࣅ୳ࡧʹ༻͍Δ FALCONN ʹରͯ͠ɼ‫ݕ‬ग़ର৅಺ͷϕΫτϧͱͯ͠‫ݕ‬ग़͞ΕΔ͜ͱ͸ͳ͍ɽ͕ͩɼFALCONN͝ͱʹ࠶‫཰ݱ‬ΛҰఆҎ্อূ্ͨ͠Ͱ࠷খͷ‫ͳͱؒ࣌ࢉܭ‬Δɼʹ༩͑ΔύϥϝʔλΛมߋ͠ɼᮢ஋Ҏ಺ͷϕΫτϧͱিಥ͢Δద੾ͳύϥϝʔλΛܾఆ͢Δख๏ΛఏҊ͢ΔɽຊষͰ͸ɼύϥ֬཰Λ্͛Δ͜ͱ͕Ͱ͖Δɽͨͩ͠ɼিಥ֬཰Λ্͛Δͱɼۙϝʔλܾఆͷํ਑ͱɼͦͷࠜ‫ڌ‬Λड़΂Δɽ๣ϕΫτϧ͕૿Ճ͠ɼ‫཭ڑ‬ͷ‫ࢉܭ‬ίετ͕૿Ճ͢Δɽ

TF-IDF ๏ʹΑΓੜ੒͞ΕͨϒϩοΫΫϩʔϯͷಛ௃ϕΫτϧؒͷྨࣅ୳ࡧ͸ɼd ࣍‫͍͓ͯʹۭؒ਺࣮ݩ‬༨‫ʹ཭ڑݭ‬ରͯ͠ߦΘΕΔɽಛ௃ϕΫτϧͷ਺͸ɼιʔείʔυதͷίʔυϒϩοΫͷ਺Ͱ͋Δɼಛ௃ϕΫτϧͷ࣍‫ݩ‬͸ɼιʔείʔυதʹग़‫͢ݱ‬Δϫʔυͷछྨͷ਺Ͱ͋Δɽू߹͸ɼେ‫ن‬໛ଟ࣍‫ͳʹݩ‬Γ΍͍͢ɽ࣮ࡍɼιʔείʔυதͷίʔυϒϩοΫͷ਺͸ߦ਺ʹൺྫͯ͠૿͑ɼ1MLOC ͷ JavaϓϩδΣΫτʹ͸໿ 4 ສϒϩοΫ‫·ؚ‬Ε͍ͯͨɽTF-IDF ๏Ͱ͸ɼม਺໊Λ‫ؚ‬Ίͨϫʔυͷछྨͷ਺͕ͦͷ··ಛ௃ϕΫτϧͷ࣍‫ͳͱݩ‬ΔͨΊɼϓϩδΣΫτͷ‫ن‬໛͕େ͖͘ͳΔͱϫʔυͷछྨ͕૿Ճ͠ɼ࣮ࡍ 1MLOC ͷ Java ϓϩδΣΫτʹ͸໿ 1࠶‫ ཰ݱ‬p Ҏ্Ͱ͖Δ͚ͩখ͍͞୳ࡧ࣌ؒͷྨࣅ୳ࡧϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ʹ͓͍ͯੜ੒͞ΕΔಛ௃ϕΫτϧͷສछྨͷϫʔυ͕ଘࡏͨ͠ɽύϥϝʔλ͸ҎԼͷཁ݅Λຬͨ͢΋ͷΛࢦఆ͢Δɽp ྨࣅ୳ࡧ࠶‫཰ݱ‬p ྨࣅ୳ࡧͷ࠶‫ͱ཰ݱ‬͸ɼLSH Λ࢖Θͣʹ͢΂ͯͷ૊Έ߹Θͤͷྨࣅ౓Λ‫ݕͯ͠ࢉܭ‬ग़ͨ͠ΫϩʔϯϖΞͷ‫ݕ‬ग़਺ͷ಺ɼ

FALCONN ͕‫ݕ‬ग़ͨ͠ΫϩʔϯϖΞͷ‫ݕ‬ग़਺ͷׂ߹Λද͢ɽ୳ࡧ࣌ؒp ྨࣅ୳ࡧͷ୳ࡧ࣌ؒͱ͸ɼϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ͷΞϧΰϦζϜͷ STEP4-1 ͔Β STEP4-5 ·Ͱʹ͔͔Δ࣌ؒͱ͢Δɽ࠶‫཰ݱ‬Λ p Ҏ্ʹͰ͖ΔύϥϝʔλͷதͰɼͰ͖Δ͚ͩগͳ͍
୳ࡧ࣌ؒͱͳΔύϥϝʔλΛܾఆ͢Δɽ

ʢ஫ 2ʣɿhttps://github.com/postgres/postgresʢ஫ 3ʣɿhttps://github.com/torvalds/linux― 59 ―

p − q2 = 2 − 2 · cos θ

3. 2 FALCONN ʹ༩͑ΔύϥϝʔλຊઅͰ͸ɼද 2 ʹࣔ͞Εͨ FALCONN ʹࢦఆ͢Δ 10 छྨͷύϥϝʔλʹ͍ͭͯઆ໌͠ɼύϥϝʔλͷܾఆखॱͱͦΕʹΑΓܾఆͨ͠ύϥϝʔλΛઆ໌͢ΔɽFALCONN ʹ༩͑Δύϥϝʔλ͸ɼҎԼͷεςοϓͰܾఆ͢Δɽ

STEP I FALCONN ੡࡞ऀ͕ਪ঑͢Δύϥϝʔλʹ‫ݻ‬ఆSTEP II ϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ʹదͨ͠ύϥϝʔλʹ‫ݻ‬ఆ(2)͜ͷͨΊ‫ͯ͠ͱ਺ؔ཭ڑ‬બͿ΋ͷ͸ͲͪΒͰ΋Α͍ɽ͔͠͠ɼ༨‫཭ڑݭ‬Λࢦఆͨ͠৔߹ɼ࠶‫ ͕཰ݱ‬5%ఔ౓‫ݮ‬গ͢Δ͜ͱ͕࣮‫ʹݧ‬ΑΓ෼͔ͬͨͨΊɼߴ͍࠶‫཰ݱ‬Λ࣮‫͢ݱ‬ΔͨΊϢʔΫϦου‫཭ڑ‬Λࢦఆ͢Δɽ

num_rotations Ͱ͸ɼٖࣅϥϯμϜճసͷճస਺ΛࢦఆͰ͖Δɽcross-polytope LSH Ͱ͸ɼϕΫτϧΛϥϯμϜʹճసͤ͞ɼཧ࿦্ͷিಥ֬཰ΛҰఆʹอͭɽߴ଎ΞμϚʔϧม‫׵‬ΛԠ

STEP III ‫ن‬໛ʹԠͯ͡มߋ͢Δύϥϝʔλͷܾఆ
3. 2. 1 અ͔Β 3. 2. 3 અ·Ͱɼύϥϝʔλͷܾఆखॱʹ‫͖ͮج‬ύϥϝʔλΛܾఆ͢ΔखॱΛઆ໌͢Δɽ

3. 2. 1 FALCONN ੡࡞ऀ͕ਪ঑͢Δύϥϝʔλʹ‫ݻ‬ఆFALCONN ʹ༩͑Δύϥϝʔλͷ಺ɼFALCONN ੡࡞ऀ͕ਪ঑͢Δ஋ʹ‫ݻ‬ఆ͢ΔύϥϝʔλΛද 3 ʹࣔ͢ɽҎԼͰɼύϥϝʔλʹؔ͢Δઆ໌ͱɼAndoni Β͕ਪ঑͢Δ‫ݻ‬ఆ஋ʹ͍ͭͯड़΂Δɽ

lsh_family Ͱ͸ɼϋογϡؔ਺ͱͯ͠ cross-polytope LSH͔ɼhyperplane LSH ͷ 2 छྨΛબ୒Ͱ͖ΔɽAndoni Βͷख๏͸ cross-polytope LSH ʹ‫͍ͯͮج‬ઃ‫͍ͯ͠ܭ‬ΔͨΊɼcross-polytope LSH ʹ‫ݻ‬ఆ͢Δɽk Ͱ͸ɼςʔϒϧຖͷϋογϡؔ਺ͷ਺Λܾఆ͢Δɽϋογϡؔ਺͕ଟ͍΄Ͳɼ͍ۙϕΫτϧͷީิͷ਺Λ‫ݮ‬Β͢͜ͱ͕Ͱ͖
ΔͨΊɼେ‫ن‬໛ͳσʔληοτ͔Β࠷ۙ఺Λ‫ٻ‬ΊΔ৔߹ʹ͸ kΛେ͖͘͠ɼۙ๣఺ΛͰ͖Δ͚ͩ‫ݮ‬Β͢ඞཁ͕͋Δɽ͔͠͠ɼຊ‫Ͱڀݚ‬͸ᮢ஋Ҏ಺ͷϖΞΛશͯ‫͚ͭݟ‬Δ͜ͱΛ໨తͱ͍ͯ͠
ΔͨΊɼk ͸ Andoni Β͕ਪ঑͢Δ 2 ʹ‫ݻ‬ఆ͢Δɽ

storage_hash_table Ͱ͸ɼϕΫτϧͷू߹ͷ‫ن‬໛΍࣍‫ݩ‬ͷେ͖͞ʹ߹͏ςʔϒϧͷσʔλߏ଄͕༻ҙ͞Ε͓ͯΓɼলϝϞϦͳ LSH Λ࣮‫͢ݱ‬ΔͨΊʹඞཁͰ͋ΔɽϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ʹ͓͍ͯಛ௃ϕΫτϧͷू߹͸େ‫ن‬໛Ͱ͋ΔͨΊɼAndoni Β͕ਪ঑͍ͯ͠ΔͰ͖Δ͚ͩগͳ͍Ϗοτ਺ͰϋογϡςʔϒϧͷόέοτΛߏங͢ΔΑ͏ʹࢦఆ͢Δ BitPackedFlatHashTableʹ͢ΔɽThreads Ͱ͸ɼFALCONN ͕࢖༻Մೳͳϋʔυ΢ΣΞͷεϨουͷ਺ΛࢦఆͰ͖Δɽͨͩ͠ɼ0 Λ༩͑Δͱɼ࠷େ਺ͷεϨουΛࣗಈͰࢦఆͤ͞Δ͜ͱ͕Ͱ͖ΔͨΊɼThreads ͸ 0(࠷େ਺) Λࢦఆ͢Δɽ

3. 2. 2 ϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ʹదͨ͠஋ʹ༻ٖͨ͠ࣅϥϯμϜճసΛ༻͍ͯɼཧ࿦্ͷϥϯμϜճసͱಉ͡ৼΔ෣͍ʹ͢ΔͨΊʹɼ3 ճసͤ͞Δɽ͜ͷͱ͖ɼߴ଎ΞμϚʔϧม‫׵‬Λ༻͍ΔͨΊɼ࣍‫ݩ‬ѹॖ‫ޙ‬ͷ࣍‫਺ݩ‬͸ɼ2 ͷྦྷ৐Λࢦఆ͠ͳ͚Ε͹ͳΒͳ͍ɽ

FHD(feature_hashing_dimension) Ͱ͸ɼ࣍‫ݩ‬ѹॖ‫ޙ‬ͷ࣍‫ݩ‬਺ΛࢦఆͰ͖Δɽ‫ػ‬ցֶशΛ༻͍ͨ࣍‫ݩ‬ѹॖΛ༻͍͓ͯΓɼ2఺ؒͷ‫཭ڑ‬Λ΄ͱΜͲมԽͤͣ͞ʹ࣍‫ݩ‬ѹॖͰ͖Δɽͨͩɼѹॖ‫ޙ‬ͷ࣍‫ݩ‬Λখ͗͘͢͞͠Δͱ 2 ఺ؒͷ‫཭ڑ‬ͷ‫͕ࠩޡ‬େ͖͘ੜ͡ΔՄೳੑ͕͋ΔͨΊɼѹॖ‫ޙ‬ͷ࣍‫ݩ‬͸ Andoni Β͕ਪ঑ͯ͠
͍Δ 1024 ʹ‫ݻ‬ఆ͢ΔɽFHD ͕‫ؒ࣌ࢉܭ‬΍࠶‫ʹ཰ݱ‬༩͑ΔӨ‫ڹ‬͸ 4. ষͰड़΂ΔɽٖࣅϥϯμϜճసʹ༻͍ΒΕΔߴ଎ΞμϚʔϧม‫׵‬ͷͨΊʹɼѹॖ‫ޙ‬ͷ࣍‫ݩ‬͸ 2 ͷྦྷ৐Λࢦఆ͠ͳ͚Ε͹ͳΒͳ͍ɽ

probes Ͱ͸ɼmulti-probe ʹ‫઀͍ۙͯͮج‬όέοτͷ୳ࡧ਺ΛࢦఆͰ͖Δɽ֤ςʔϒϧʹ͖ͭ 4 ͭͣͭۙ઀όέοτΛ୳ࡧͤ͞Δ͜ͱʹΑΓ‫ݕ‬ग़࿙ΕΛ‫ݮ‬Β͢ɽ4. ষͰৄࡉʹ͍ͭͯड़΂Δɽ

3. 2. 3 ‫ن‬໛ʹԠͯ͡มߋ͢Δύϥϝʔλຊख๏͕ϓϩδΣΫτͷ‫ن‬໛ຖʹܾఆ͢Δ FALCONN ʹ༩͑Δ 2 छྨͷύϥϝʔλΛද 5 ʹࣔ͢ɽ2 छྨͷύϥϝʔλʹ͍ͭͯड़΂ΔɽLCD (last_cp_dimension) Ͱ͸ɼcross-polytope LSH Ͱ༻͍Δ‫ٿ‬໘ͷ෼ׂ਺ΛࢦఆͰ͖Δɽ෼ׂ਺Λଟ͘͢Δ΄Ͳিಥ֬཰͸Լ͕Δɽ‫ٿ‬໘Λ T ‫ݸ‬ͷ۠ըʹ෼ׂͨ࣌͠ɼcross-polytopeLSH ͷੑ্࣭ɼ‫ ཭ڑ‬r Ҏ಺ͷ 2 ఺ p, q ͷিಥ֬཰͸ࣜ 3 Ͱ‫ܭ‬ࢉ͞ΕΔɽ͜ͷিಥ֬཰͕ 0.8 Ҏ্ʹͳΔΑ͏ͳ࠷େͷ T Λᮢ஋ʹରͯ͠‫ܾͯ͠ࢉܭ‬ఆ͢Δɽ4. ষͰ LCD ͱ‫ؒ࣌ࢉܭ‬΍࠶‫ݱ‬཰ͷؔ܎Λड़΂Δɽln‫ݻ‬ఆ͢Δύϥϝʔλ1r2· ln T + Or (ln ln T )=P r(p, q)
4 − r2(3)FALCONN ʹ༩͑Δύϥϝʔλͷ಺ɼϒϩοΫΫϩʔϯ‫ݕ‬l Ͱ͸ϋογϡςʔϒϧͷ਺ΛࢦఆͰ͖Δɽϋογϡؔ਺͕ग़๏ʹదͨ͠஋ʹ‫ݻ‬ఆ͢ΔύϥϝʔλΛද 4 ʹࣔ͢ɽҎԼͰɼશͯҟͳΔϋογϡςʔϒϧΛෳ਺༻ҙ͠ɼগͳ͘ͱ΋̍ͭͷύϥϝʔλʹؔ͢Δઆ໌ͱɼϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ʹదͨ͠ϋογϡςʔϒϧͰিಥͨ͠ϕΫτϧΛۙ๣఺ͱ͠ɼিಥ֬཰‫ݻ‬ఆ஋ʹ͍ͭͯड़΂ΔɽΛ্͛Δɽͨͩ͠ɼ4. ষͰৄ͘͠ड़΂Δ͕ɼϋογϡςʔϒϧ

distance_function Ͱ͸ɼ‫ͯ͠ͱ਺ؔ཭ڑ‬༨‫͔཭ڑݭ‬ϢʔΫͷ਺Λ૿΍͢ͱɼઢ‫ۙʹܗ‬๣఺͕૿Ճ͢ΔͨΊɼ‫ࢉܭ‬ίετ͕Ϧου‫཭ڑ‬ͷ 2 छྨΛબ୒Ͱ͖ΔɽTF-IDF ๏Ͱ͸༨‫౓ࣅྨݭ‬ઢ‫૿ʹܗ‬Ճ͢Δɽϋογϡςʔϒϧ͕ L ‫ݸ‬ͷ࣌ɼ2 ఺ p, q ͷিΛ༻͍ΔͨΊɼྨࣅ୳ࡧͷલʹ͢΂ͯͷಛ௃ϕΫτϧʹର͠ਖ਼

ಥ֬཰ P rL (p, q) ͸ࣜ 4 Ͱ‫ٻ‬ΊΒΕΔɽ‫ن‬ԽΛߦ͏ɽਖ਼‫ن‬Խ͞Εͨ 2 ͭͷϕΫτϧ p, q ʹରͯ͠ɼͳ֯͢Λ θ ͱ͢Δͱɼࣜ 3 Ͱࣔ͞ΕΔΑ͏ʹɼϢʔΫϦου‫཭ڑ‬͸༨‫ʹ཭ڑݭ‬ର͠୯ௐ‫ݮ‬গ͢Δɽ

P rL (p, q) = 1 − (1 − P r(p, q))L(4)͜͜ͰɼN ‫ݸ‬ͷಛ௃ϕΫτϧશ͕ͯᮢ஋಺ͷ఺ͱিಥ͢Δ֬
཰ͱͯ͠ɼP rR (p, q) ΛҎԼͷΑ͏ʹఆٛ͢ΔɽP rR ͸ɽ࠶‫ݱ‬― 60 ―

lsh_family

cross-polytope LSHk2᥈⣴᫬㛫㼇㼟㼉஋

storage_hash_table BitPackedFlatHashTable㻝㻝㻢㻜㻚㻥㻝㻞㻜㻚㻤㻤㻜㻚㻣㻠㻜㻚㻢㻜㻜㻚㻡㻝0(࠷େ਺)Threads㻝㻢㻢㻠㻞㻡㻢᥈⣴᫬㛫㼇㼟㼉ϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ʹదͨ͠஋ʹ‫ݻ‬ఆ͢Δύϥϝʔλ㻝㻜㻞㻠෌⌧⋡

ਤ 2 FHD ͕୳ࡧ࣌ؒ΍࠶‫ݱ‬ੑʹ༩͑ΔӨ‫ڹ‬

3 ճసFHD1,024probesςʔϒϧຖʹ 4 ͭͷόέοτΛ୳ࡧ᥈⣴᫬㛫㼇㼟㼉

num_rotations㻞㻚㻠㻜㻚㻢㻞㻚㻟㻜㻚㻡㻢㻞㻚㻞㻜㻚㻡㻞㻞㻚㻝㻜㻚㻠㻤㻞㻜㻚㻠㻠㻝㻚㻥㻝‫ن‬໛ʹԠͯ͡มߋ͢Δύϥϝʔλύϥϝʔλ໊஋LCD

P r(p, q) > 0.8 & ࠷খl

P rR > p & ࠷େ㻢㻠㻞㻡㻢㻜㻚㻠㻝㻜㻞㻠෌⌧⋡ਤ 3 LCD ͕୳ࡧ࣌ؒ΍࠶‫ݱ‬ੑʹ༩͑ΔӨ‫ڹ‬཰ͷཧ࿦্ͷ‫ظ‬଴஋Ͱ͋Δɽ࠶‫཰ݱ‬Λ p ಘΔͨΊʹɼ‫ظ‬଴஋Ͱ
͋Δ P rR ͕ p Ҏ্ʹͳΔΑ͏ͳ࠷খͷςʔϒϧ਺ L Λಛ௃ϕ㻝㻜㻜㻝㻤㻜㻜㻚㻥㻢㻜㻜㻚㻤㻠㻜㻜㻚㻣㻞㻜㻜㻚㻢Ϋτϧͷ਺ʹରͯ͠‫ܾͯ͠ࢉܭ‬ఆ͢ΔɽP rR ͸ࣜ 5 Ͱ‫ٻ‬ΊΒ㻜㻜㻚㻡㻜ΕΔɽ

P rR = P rL (p, q)N㻝㻢᥈⣴᫬㛫㼇㼟㼉᥈⣴᫬㛫㼇㼟㼉ද5㻠෌⌧⋡஋

distance_function Euclidean distance㻝㻜㻞㻜᥈⣴᫬㛫㼇㼟㼉(5)᥈⣴᫬㛫㼇㼟㼉

FALCONN ʹ༩͑Δύϥϝʔλͷ಺ɼFHDɼLCDɼlɼprobe㻝㻜㻝㻥㻜㻚㻥㻤㻜㻚㻤㻣㻜㻚㻣㻢㻜㻚㻢㻜㻚㻡㻜Βਤ 5 ʹࣔ͢ɽௐࠪ݁Ռ͸ɼௐࠪର৅Ҏ֎ͷύϥϝʔλΛશͯ㻢㻜㻤㻜㻝㻜㻜෌⌧⋡Βɼ࠶‫཰ݱ‬΋૿Ճ͢Δɽ֬ೝ͢Δۙ઀όέοτΛ૿΍͢ຖʹɼۙ๣ϕΫτϧͱΈͳ͢ϕΫτϧ͕૿͑ɼ‫཭ڑ‬ͷ‫૿͕ؒ࣌ࢉܭ‬Ճ͢ΔͨΊͰ͋Δɽ

5. ఏҊख๏ͷධՁ࣮‫ݧ‬ͷ‫ʹࢉܭ‬ଟେͳ͕͔͔࣌ؒΔɽͦͷ൓໘ɼFHD ͷ஋ΛΛେ͖͘͢Δͱɼۙ๣఺͕‫ݮ‬গ͢Δ͕ɼ࣍‫͕ݩ‬େ͖͘ͳΔ͜ͱʹΑΓɼٖࣅϥϯμϜճసʹ͔͔Δίετ͕େ͖͘ͳΔɽ㻠㻜

ਤ 5 probes ͕୳ࡧ࣌ؒ΍࠶‫ݱ‬ੑʹ༩͑ΔӨ‫ڹ‬‫ݻ‬ఆͨ͠ঢ়ଶͰௐࠪର৅ͷύϥϝʔλΛมԽͤ͞Δɽ୳ࡧ࣌ؒ͘͢Δͱɼ࣍‫ݩ‬ѹॖͷӨ‫ʹڹ‬ΑΓۙ๣఺͕ଟ͘‫͔ͭݟ‬Γɼ‫཭ڑ‬㻞㻜᥈⣴᫬㛫㼇㼟㼉ͷௐࠪΛ PostgreSQL 10.1 Λର৅ʹߦ͏ɽௐࠪ݁ՌΛਤ 2 ͔FHD ͸ओʹ୳ࡧ࣌ؒʹେ͖ͳӨ‫ڹ‬Λ༩͑ΔɽFHD ͷ஋Λখ͞෌⌧⋡㻡

ͷ 4 ͭͷύϥϝʔλʹ͍ͭͯɼ୳ࡧ࣌ؒ΍࠶‫ݱ‬ੑʹ༩͑ΔӨ‫ڹ‬

FHD ͱ୳ࡧ࣌ؒͱ࠶‫ݱ‬ੑͷؔ܎Λද͢άϥϑΛਤ 2 ʹࣔ͢ɽ㻟㻜

ਤ 4 l ͕୳ࡧ࣌ؒ΍࠶‫ݱ‬ੑʹ༩͑ΔӨ‫ڹ‬

4. ύϥϝʔλ͕୳ࡧ࣌ؒ΍࠶‫ݱ‬ੑʹ༩͑ΔӨ‫ڹ‬ͷௐࠪ͸ɼ3 ճͷ࣮ߦ࣌ؒͷฏ‫ۉ‬ΛऔΔɽ෌⌧⋡ύϥϝʔλ໊㻠

෌⌧⋡

ද4㻞㻜

෌⌧⋡

ද 3 FALCONN ੡࡞ऀ͕ਪ঑͢Δύϥϝʔλύϥϝʔλ໊ຊষͰ͸ɼຊख๏ͰఏҊͨ͠ύϥϝʔλܾఆख๏ͷධՁ࣮
ʢ஫ 4ʣ

ᮢ஋ 0.9 ʹ͓͍ͯɼLCD ͱ୳ࡧ࣌ؒͱ࠶‫ݱ‬ੑͷؔ܎Λද͢άϥϑΛਤ 3 ʹࣔ͢ɽLCD Λ૿Ճͤ͞Δͱɼ࠶‫཰ݱ‬͸‫ݮ‬গ͠ɼ
LCD >= 64 ʹ͓͍ͯ୳ࡧ࣌ؒ͸΄΅ҰఆͰ͋ΔɽLCD = 32ʹ͓͍ͯ P r(p, q) = 0.803 ͱͳΔɽl ͱ୳ࡧ࣌ؒͱ࠶‫ݱ‬ੑͷؔ܎Λද͢άϥϑΛਤ 4 ʹࣔ͢ɽl ͷ஋Λ૿Ճͤ͞Δͱɼ֤ϋογϡςʔϒϧͰ΄ͱΜͲಉ͡਺ͷۙ๣఺Λऔಘ͠ɼ‫཭ڑ‬ͷ‫͕ؒ࣌ࢉܭ‬ઢ‫૿ʹܗ‬Ճ͢ΔͨΊɼ୳ࡧ࣌ؒ͸ઢ‫૿ʹܗ‬Ճ͢ΔɽϋογϡςʔϒϧຖʹϥϯμϜͳϋογϡؔ਺͕ੜ੒͞ΕΔͨΊɼ࠶‫཰ݱ‬͸ l ͷ૿Ճͱͱ΋ʹ૿Ճ͢Δɽ

probe ͱ୳ࡧ࣌ؒͱ࠶‫ݱ‬ੑͷؔ܎Λද͢άϥϑΛਤ 5 ʹࣔ͢ɽprobe ͷ஋Λ૿Ճͤ͞Δͱɼ୳ࡧ࣌ؒ͸΄΅ઢ‫૿ʹܗ‬Ճ͠ͳ͕‫ݧ‬ʹ͍ͭͯड़΂Δɽຊख๏Ͱܾఆͨ͠ύϥϝʔλͱ͜Ε·ͰϒϩοΫΫϩʔϯ‫ݕ‬ग़๏Ͱ࢖༻͍ͯͨ͠ύϥϝʔλͱͷൺֱΛɼྨࣅ୳ࡧʹ͔͔Δ࣌ؒͱ࠶‫཰ݱ‬ͷ‫Ͱ఺؍‬ɼҟͳΔ‫ن‬໛ͷ 2ͭͷ C ϓϩδΣΫτͷ PostgreSQL 10.1 ͱ Linux Kernel 4.14ʹରͯ͠ߦ͏ɽର৅ͷϓϩδΣΫτͷ৘ใΛද 6 ʹࣔ͢ɽ࣮‫ݧ‬͸ҎԼͷखॱͰߦ͏ɽ·ͣɼLSH Λ࢖Θͣʹ͢΂ͯͷ૊Έ߹Θͤͷྨࣅ౓Λ‫ͯ͠ࢉܭ‬ϒϩοΫΫϩʔϯ‫ݕ‬ग़Λߦ͏ɽ‫ط‬ʹ࢖༻தͷύϥϝʔλͱຊख๏Ͱܾఆͨ͠ύϥϝʔλΛɼͦΕͧΕϒϩοΫΫϩʔϯ‫ݕ‬ग़๏ʹద༻͢Δɽ֤ϓϩδΣΫτʹର
ʢ஫ 4ʣɿCPU Intel Xeon 2.80GHz 4coreɼϝϞϦ 32.0GBɼOS Windows10 64bit. Java Ծ૝ϚγϯͷελοΫྖҬ 1GBɼώʔϓྖҬ 15GB― 61 ―ද6ϓϩδΣΫτͷ৘ใϓϩδΣΫτ໊ϝʔλܾఆΛߦ͏͜ͱͰɼp ྨࣅ୳ࡧͷཁ݅Ͱ͋Δɼ࠶‫ ཰ݱ‬pϝτϦΫε

஋ߦ

1,136,684

ධՁ࣮‫Ͱݧ‬͸ɼҟͳΔ‫ن‬໛ͷ 2 ͭͷ C ϓϩδΣΫτͷ Post-ίʔυϒϩοΫ

30,537

greSQL 10.1 ͱ Linux Kernel 4.14 ʹର͠ɼ࠶‫ʹؒ࣌ࡧ୳ͱ཰ݱ‬ϫʔυ

11,366

ᮢ஋ 0.9 ͷΫϩʔϯϖΞ

12,629PostgreSQL 10.1Ҏ্Λຬ଍͠ɼྨࣅ୳ࡧͷ࣌ؒͷ࡟‫ݮ‬Λ࣮‫ͨ͠ݱ‬ɽؔͯ͠ɼ‫ʹط‬ϒϩοΫΫϩʔϯ‫ݕ‬ग़๏Ͱ࢖༻தͷύϥϝʔλͱຊख๏Ͱܾఆͨ͠ύϥϝʔλͱͷൺֱΛߦͬͨɽͦͷ݁Ռɼຊߦ 17,407,666

Linux Kernel 4.14ίʔυϒϩοΫ

508,982ख๏Ͱܾఆͨ͠ύϥϝʔλ͸ɼલύϥϝʔλΑΓ΋୳ࡧ࣌ؒΛϫʔυ77,319

୹͘͢Δ͜ͱʹ੒ޭͨ͠ɽ·ͨɼp = 0.99 ͱͯ͠ p ྨࣅ୳ࡧΛᮢ஋ 0.9 ͷΫϩʔϯϖΞ

163,535

͍ͯ͠Δ͕ɼཁ݅Ͱ͋Δ࠶‫ ཰ݱ‬99% Λຬ଍͍ͯ͠Δɽࠓ‫ޙ‬ͷ՝୊ͱͯ͠ɼҎԼ͕‫͛ڍ‬ΒΕΔɽ

ද7

PostgreSQL 10.1࣮‫݁ݧ‬Ռ•ؔ਺Ϋϩʔϯ‫ݕ‬ग़๏ [11] ͳͲɼϒϩοΫΫϩʔϯ‫ݕ‬ग़๏લύϥϝʔλຊख๏ͱಉ༷ͷྨࣅ୳ࡧΛߦ͏ख๏ʹରͯ͠ద༻͠ɼ༗ޮੑΛධՁ͢୳ࡧ࣌ؒ [s]

65.64

14.78

Δඞཁ͕͋Δɽ࠶‫[ ཰ݱ‬%]

93.10

99.21

Linux Kernel 4.14 ୳ࡧ࣌ؒ [s]࠶‫[ ཰ݱ‬%]•1098.1 334.73
89.62

ຊ‫Ͱڀݚ‬͸ TF-IDF ๏ʹରͯ͠ධՁ࣮‫ݧ‬Λߦ͕ͬͨɼଞͷϕΫτϧԽख๏ʹରͯ͠΋࣮‫ݧ‬Λߦ͍ɼ༗ޮੑΛධՁ͢Δඞ

99.86

ཁ͕͋Δɽ•ຊ‫Ͱڀݚ‬͸ FALCONN ʹରͯ͠ύϥϝʔλܾఆΛߦͬͯͦ͠ΕͧΕͷύϥϝʔλͰͷϒϩοΫΫϩʔϯ‫ݕ‬ग़Λ 3 ճ͕ͣͨɼଞͷ LSH ʹ͸ͳ͍ύϥϝʔλ͕ଘࡏ͢ΔͨΊɼຊख๏ͭߦ͍ɼྨࣅ୳ࡧͷฏ‫ͱؒ࣌ࡧ୳ۉ‬ɼ࠶‫཰ݱ‬Λൺֱ͢ΔɽΛଞͷ LSH ʹద༻͢ΔͨΊͷ֦ுੑʹ͍ͭͯ࠶ߟ͢Δඞཁ͕࣮‫݁ݧ‬ՌΛද 7 ʹࣔ͢ɽ‫ن‬໛͕ҟͳΔ 2 ͭͷϓϩδΣΫτʹରͯ͠ɼલύϥϝʔλͷ৔߹͔ΒɼͦΕͧΕ 60%Ҏ্ͷ୳ࡧ࣌ؒͷ࡟‫ݮ‬Λߦ͏͜ͱ͕Ͱ͖ɼຊख๏Ͱܾఆͨ͠ύϥϝʔλͰ͸ɼ͋Δɽँࣙ

p = 0.99 ͷ p ྨࣅ୳ࡧͷཁ݅Ͱ͋Δ 99%ͷ࠶‫཰ݱ‬Λຬ଍ͯ͠
͍Δɽ

6. ߟ࡯

ຊষͰ͸ɼධՁ࣮‫ݧ‬ͷ݁Ռʹର͢Δٞ࿦Λߦ͍ɼଞͷ‫ݕ‬ग़ख๏΍ଞͷϕΫτϧԽख๏ʹର͢Δຊख๏ͷ༗༻ੑʹ͍ͭͯߟ࡯Λߦ͏ɽ࠶‫ؒ࣌ࡧ୳ͱ཰ݱ‬ධՁ࣮‫Ͱݧ‬͸ 2 ͭͷҟͳΔ‫ن‬໛ͷϓϩδΣΫτʹର࣮͠‫ݧ‬Λߦͬͨɽ͍ͣΕͷ‫ن‬໛Ͱ΋࠶‫ ཰ݱ‬0.99 Λຬ଍͢Δ݁Ռ͕ಘΒΕɽ‫ظ‬଴͢Δ࠶‫཰ݱ‬ΛಘΒΕΔ͜ͱ͕֬ೝͰ͖ͨɽ·ͨɼ͍ͣΕͷ‫ن‬໛Ͱ΋ 60%ఔ౓ͷ୳ࡧ࣌ؒͷ୹ॖ͕֬ೝͰ͖ͨɽຊख๏ͷ༗ޮੑຊख๏͸༨‫཭ڑݭ‬ͷԼͰͷ p ྨࣅ୳ࡧʹରͯ͠ఏҊ͍ͯ͠ΔɽͦͷͨΊɼ‫ݕ‬ग़ख๏ʹґଘ͓ͯ͠ΒͣɼϒϩοΫΫϩʔϯ‫ݕ‬ग़๏Ҏ֎ͷख๏ʹ͓͍ͯ΋ɼ༨‫཭ڑݭ‬ͷԼͰͷ p ྨࣅ୳ࡧΛߦ͏ख๏ʹ͸ɼຊख๏Ͱܾఆ͢ΔύϥϝʔλΛ༻͍Δ FALCONNΛద༻ՄೳͰ͋Δɽຊ‫Ͱڀݚ‬͸ FALCONN Λର৅ʹύϥϝʔλܾఆΛߦͬͨɽຊ‫ڀݚ‬͸ɼᮢ஋Ҏ಺ͷিಥ֬཰ΛҰఆҎ্ʹ͢ΔύϥϝʔλΛܾఆ͠ɼ͞Βʹ࠶‫ ཰ݱ‬p Λຬͨ͢ύϥϝʔλΛܾఆ͢Δɽຊख๏Λଞͷ LSH ʹద༻͢ΔͨΊʹ͸ɼিಥ֬཰΍࠶‫཰ݱ‬Λௐ੔͢ΔͨΊͷύϥϝʔλ͕͋Δࣄɼ·ͨ͸Ϣʔβʔ͕ͦΕΒΛ֎෦͔Βௐ੔͢Δํ๏͕͋Δࣄ͕ඞཁͰ͋Δɽ

7. ·ͱΊͱࠓ‫ޙ‬ͷ՝୊ຊ‫Ͱڀݚ‬͸ɼp ྨࣅ୳ࡧͷͨΊͷύϥϝʔλܾఆख๏ΛఏҊͨ͠ɽύϥϝʔλΛɼ࠶‫͕཰ݱ‬ཧ࿦্ p Ҏ্ͱͳΔΑ͏ͳύϥຊ ‫ ڀ ݚ‬͸ JSPS Պ ‫ ݚ‬අ 25220003ɼ16K16034ɼ

15H06344 ͷॿ੒Λड͚ͨɽจ‫ݙ‬[1] ං‫ޙ‬๕थɼೇຊਅೋɼҪ্ࠀ࿠ɼ“ίʔυΫϩʔϯ‫ݕ‬ग़ͱͦͷؔ࿈ٕज़ɼ” ిࢠ৘ใ௨৴ֶձ࿦จࢽɼvol.J91-Dɼno.6ɼpp.604–613ɼ
1998ɽ
[2] Ratta D., Bhatia R., and Singh M., “Software clone detection: A systematic review,” Information and Software
Technology, vol.55, no.7, pp.1165–1199, 2013.
[3] ԣҪҰًɼ٢ాଇ༟ɼቐ ԸಬɼҪ্ࠀ࿠ɼ“৘ใ‫ٕࡧݕ‬ज़ʹ‫ج‬ͮ͘ϒϩοΫΫϩʔϯ‫ݕ‬ग़ɼ” ৘ใॲཧֶձ‫ڀݚ‬ใࠂɼvol.2017SE-196ɼno.19ɼpp.1–8ɼ2017ɽ
[4] R. Baeza-Yates and B. Ribeiro-Neto, Modern Information
Retrieval: The Concepts and Technology behind Search,
Addison-Wesley, 2011.
[5] A. Alexandr and I. Piotr, “Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions,” Foundations of Computer Science, vol.51, no.1,pp.117–122, 2006.
[6] A. Alexandr, I. Piotr, L. Thijs, R. Ilya, and S. Ludwig,“Practical and optimal LSH for angular distance,” Proc. ofNIPS 2015, pp.1225–1233, 2015.
[7] Q. Lv, W. Josephson, Z. Wang, M. Charikar, and K. Li,“Multi-probe LSH: eﬃcient indexing for high-dimensional
similarity search,” Proc. of VLDB, pp.950–961, 2007.
[8] K.Q. Weinberger, A. Dasgupta, J. Langford, A.J. Smola,and Josh Attenberg., “Feature hashing for large scale multitask learning,” Proc. of ICML 2009, pp.1113–1120, 2009.
[9] N. Ailon and B. Chazelle, “The fast johnson-lindenstrausstransform and approximate nearest neighbors,” Society forIndustrial and Applied Mathematics, vol.39, no.1, pp.302–322, 2009.
[10] C.K. Roy, J.R. Cordy, and R. Koschke, “Comparison andevaluation of code clone detection techniques and tools,”
Science of Computer Programming, vol.74, no.7, pp.470–495, 2009.
[11] ࢁத༟थɼ٢ాଇ༟ɼቐ ԸಬɼҪ্ࠀ࿠ɼ“৘ใ‫ٕࡧݕ‬ज़ʹ‫ج‬ͮ͘ߴ଎ͳؔ਺Ϋϩʔϯ‫ݕ‬ग़ɼ” ৘ใॲཧֶձ࿦จࢽɼvol.55ɼ
no.10ɼpp.2245–2255ɼ2014ɽ― 62 ―