プライバシー保護した分散データマイニングの通信コスト削減手法

全文

(1)Vol.2016-DPS-168 No.4 Vol.2016-SPT-21 No.4 Vol.2016-EIP-74 No.4 2016/11/17. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ϓϥΠόγʔอ‫ͨ͠ޢ‬෼ࢄσʔλϚΠχϯάͷ ௨৴ίετ࡟‫ݮ‬ख๏ খྛ ༝ਅ1,a). Ԧ Ո޺1. ࣇ‫ ۄ‬ӳҰ࿠1. ߴా ๛༤1. ֓ཁɿ෼ࢄσʔλϚΠχϯάʹ͓͍ͯɼऔΓѻ͏σʔλͷอ‫ޢ‬͸ॏཁͳ՝୊Ͱ͋Δɽൿີ෼ࢄ๏Λ༻͍Δ ͜ͱʹΑΓɼσʔλͷ҉߸Խͱൺ΂ͯɼ௿͍௨৴ίετͰσʔλΛอ‫͕ͳ͠ޢ‬Βසग़ύλʔϯͷநग़͕Ͱ ͖Δɽ͔͠͠ɼଟ਺ͷ௨৴͕ඞཁͱͳΓɼΠϯλʔωοτͷΑ͏ͳଳҬʹ੍‫ݶ‬ͷ͋Δ‫Ͱڥ؀‬͸ɼॲཧ࣌ؒ ͕૿Ճ͢Δ‫ڪ‬Ε͕͋Δɽຊ‫ڀݚ‬͸ɼ௨৴ίετΛ࡟‫ͨ͠ݮ‬෼ࢄσʔλϚΠχϯάख๏ͷఏҊͱͦͷੑೳධ ՁΛߦ͏ɽ. An Approach to Reducing Communication Cost of Secure Data Mining Yuma Kobayashi1,a). Jiahong Wang1. 1. എ‫ܠ‬ ۙ೥ɼ‫Ͱۀا‬͸औΓѻ͏σʔλΛσʔλϕʔεʹ஝ੵ͠ɼ. Eiichiro Kodama1. Toyoo Takata1. ͦͷ‫ݸऀױ‬ਓ͕ಛఆ͞ΕΔՄೳੑ͕ଘࡏ͢Δɽ ͦͷͨΊɼ෼ࢄσʔλϚΠχϯάͷϓϥΠόγʔอ‫ޢ‬Λ ՝୊ͱͨ͠‫͕ڀݚ‬ଘࡏ͢Δɽ‫ͯ͠ͱྫڀݚ‬ɼCRDM[1] ͕. σʔλϚΠχϯάٕज़ʹΑͬͯ༗ӹͳ৘ใΛநग़͢Δ͜ͱ. ‫͛ڍ‬ΒΕΔɽ͜ͷ‫Ͱڀݚ‬͸ɼൿີ෼ࢄ๏Λ༻͍ͨϓϥΠό. ͕Ұൠతͱͳ͍ͬͯΔɽҩྍ‫ؔػ‬Λྫͱͨ͠৔߹ɼ ʰͦͷҩ. γʔอ‫ޢ‬Λߦ͍ͬͯΔɽ۩ମతʹ͸ɼ֤ҩӃͷൿີσʔλ. ྍ‫Ͱؔػ‬͸ɼ಄௧ͱ‫͜ݞ‬Γͷ঱ঢ়Λ࣋ͬͨଟ͘ͷ‫ऀױ‬͸ɼ. Λ͍͔ͭ͘ͷ஋ʹ෼ׂ͠ɼଞͷҩӃΛ‫ܦ‬༝͔ͤͯ͞Βू‫ܭ‬. ෩अΛͻ͍͍ͯΔʱͱ͍ͬͨؔ܎ੑͷ͋ΔσʔλΛநग़͢. Λߦ͏ɽ͜ͷϓϥΠόγʔอ‫ޢ‬ख๏Λ༻͍Δ͜ͱͰɼ֤ҩ. Δɽ͜ͷσʔλ͸૬ؔϧʔϧͱ‫ݺ‬͹ΕΔɽ·ͨɼ૬ؔϧʔ. Ӄ͕ൿີσʔλͷஅย͔͠‫ݟ‬Δ͜ͱ͕Ͱ͖ͳ͍ঢ়ଶͰσʔ. ϧΛग़ྗ͢Δٕज़Λ૬ؔϧʔϧϚΠχϯάͱ‫Ϳݺ‬ɽຊ‫ڀݚ‬. λϚΠχϯάΛߦ͏͜ͱ͕Ͱ͖Δɽൿີ෼ࢄ๏Λ༻͍ͯ. Ͱ͸ɼ૬ؔϧʔϧϚΠχϯάΛର৅ͱ͢Δɽ. σʔλϚΠχϯάΛߦ͏͜ͱͰɼ҉߸ԽͳͲͷෛՙͷॏ͍. ҩྍ‫ؔػ‬͸ɺ͠͹͠͹ෳ਺ͷ஍Ҭʹ·͕ͨͬͯ఺ࡏͯ͠. ॲཧΛߦΘͣʹϓϥΠόγʔอ‫ޢ‬Λߦ͏͜ͱ͕Ͱ͖Δ [1]ɽ. ͍Δɽྫ͑͹ɼ੝ԬපӃ΍ୌ୔ҩӃͷΑ͏ʹɼ֤஍Ҭʹ਺. ͔͠͠ɼൿີ෼ࢄ๏ʹ͸ଟ਺ͷ௨৴͕ඞཁͱͳΔɽ͜ͷ. ଟ͘ͷҩྍ‫͕ؔػ‬ଘࡏ͢Δɽ͜ͷΑ͏ͳ‫Ͱڥ؀‬͸ɼෳ਺ͷ. ͨΊɼଳҬͷ‫ Ͱڥ؀͍ڱ‬CRDM Λ༻͍ͨσʔλϚΠχϯ. σʔλϕʔεΛର৅ͱͨ͠૬ؔϧʔϧϚΠχϯάٕज़Ͱ. άΛߦͬͨ৔߹ɼॲཧ͕࣌ؒ૿Ճ͢Δ‫ڪ‬Ε͕͋Δɽ. ͋Δ෼ࢄσʔλϚΠχϯάΛ༻͍ͯɼ‫ڞ‬௨ͯ͠සग़͢Δύ. ຊ‫Ͱڀݚ‬͸ɼൿີ෼ࢄ๏Λ༻͍ͨ෼ࢄσʔλϚΠχϯά. λʔϯͷநग़Λߦ͏ɽ͜ͷͨΊʹ͸ɼ֤ҩӃͷൿີσʔλ. ͷ௨৴ίετͷ࡟‫ݮ‬Λ໨తͱ͢ΔɽఏҊख๏ͱͯ͠ɼσʔ. ΛଞͷҩӃ΁ૹ৴ͯ͠ɼू‫͢ܭ‬Δඞཁ͕͋Δɽ. λϚΠχϯάΛߦ͏‫߹ʹڥ؀‬Θͤͯɼద੾ͳ௨৴਺ʹͳΔ. ͔͠͠ɼൿີσʔλΛͦͷ··ૹ৴ͯ͠͠·͏ͱɼϓϥ. Α͏ʹࣄલʹ௨৴૬खΛௐ੔͢Δ͜ͱͰɼ௨৴ίετͷ࡟. Πόγʔ࿙Ӯͷ‫ݥة‬ੑ͕ଘࡏ͢Δɽྫͱͯ͠ɼҩྍ‫ऀױ‬ͷ. ‫ݮ‬Λߦ͏ɽੑೳධՁͷ݁Ռɼ௨৴ίετͷ࡟‫͕֬ݮ‬ೝͰ͖. Α͘ซൃ͢Δ঱ঢ়Λൃ‫͢ݟ‬ΔͨΊʹ‫ऀױ‬ͷσʔλΛ༻͍Δ. ͨɽಛʹσʔλϚΠχϯάʹࢀՃ͢Δϊʔυ͕ଟ਺ଘࡏ͢. ৔߹Λߟ͑Δɽ‫ऀױ‬ͷσʔλΛͦͷ··౉ͯ͠͠·͏ͱɼ. Δ৔߹ɼ௨৴ίετΛେ͖͘࡟‫͖Ͱݮ‬Δɽ ຊ‫ʹڀݚ‬ΑΓɼωοτϫʔΫଳҬͷ‫͋ʹڥ؀͍ڱ‬Δσʔ. 1 a). ‫ؠ‬ख‫ཱݝ‬େֶιϑτ΢ΣΞ৘ใֶ‫ڀݚ‬Պ [email protected]. ⓒ 2016 Information Processing Society of Japan. λϕʔεΛର৅ͱͨ͠σʔλϚΠχϯάͰ΋ɼॲཧ࣌ؒͷ. 1.

(2) Vol.2016-DPS-168 No.4 Vol.2016-SPT-21 No.4 Vol.2016-EIP-74 No.4 2016/11/17. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ૿ՃΛ཈͑Δ͜ͱ͕Ͱ͖Δɽ͜ΕʹΑΓɼ෼ࢄσʔλϚΠ. ߹ΘͤΛ૬ؔϧʔϧͱͯ͠நग़͢Δ͜ͱΛߟ͑Δɽ঱ঢ়΍. χϯά͕Ͱ͖Δର৅ͷ֦େͱ෼ࢄσʔλϚΠχϯάͷੑೳ. ͦͷ ID ͳͲͷσʔλϚΠχϯάʹ༻͍ΔσʔλͷཁૉΛ. ͷ޲্ʹߩ‫ظ͕ݙ‬଴Ͱ͖Δɽ. ΞΠςϜͱ‫ͼݺ‬ɼ1 ͭҎ্ͷΞΠςϜͷू߹ΛΞΠςϜηο. ୈ̎અͰ͸ɼ෼ࢄσʔλϚΠχϯάʹؔ͢Δؔ࿈‫ڀݚ‬ͷ. τͱ‫Ϳݺ‬ɽ‫͕ऀױ‬ૌ͑ͨ঱ঢ়ͷཤྺ (ΞΠςϜηοτ) Λτ. આ໌ͱ໰୊఺ʹ͍ͭͯड़΂Δɽୈ̏અͰ͸ɼఏҊख๏ͷઆ. ϥϯβΫγϣϯͱ‫Ϳݺ‬ɽ֤ҩӃ͸τϥϯβΫγϣϯσʔλ. ໌ͱఏҊΞϧΰϦζϜʹ͍ͭͯड़΂Δɽୈ̐અͰ͸ɼఏҊ. ϕʔεΛอ͓࣋ͯ͠Γɼ‫ऀױ‬ͷ঱ঢ়ͷཤྺ (ΞΠςϜηο. ΞϧΰϦζϜͷੑೳධՁͷ݁ՌΛड़΂ɼ࠷‫ͱ·ʹޙ‬Ίͱ͠. τ) ΛτϥϯβΫγϣϯͱͯ͠େྔʹอଘ͍ͯ͠Δɽ֤ҩ. ͯ݁࿦Λड़΂Δɽ. Ӄ͸ಉ͡छྨͷ঱ঢ়Λѻ͏΋ͷͱ͠ɼ঱ঢ়ͷ ID ͸‫ڞ‬௨͠. 2. ؔ࿈‫ڀݚ‬ ‫ج‬ຊతͳ෼ࢄσʔλϚΠχϯάΞϧΰϦζϜͱͯ͠ɼ. ͍ͯΔ΋ͷͱ͢Δɽ ͜ͷσʔλϚΠχϯάͰ͸ɼϓϥΠόγʔอ‫ޢ‬ͷͨΊɼ ͋ΔҩӃ಺Ͱ঱ঢ়Λૌ͑ͨ‫ऀױ‬ͷ਺ΛଞͷҩӃʹ஌ΒΕͳ. FDM[2] ͕‫͛ڍ‬ΒΕΔɽ͜ͷ‫ڀݚ‬͸ෳ਺ͷσʔλϕʔεΛ. ͍Α͏ʹ૬ؔϧʔϧΛநग़͢ΔɽϓϥΠόγʔͷఆٛ͸અ. ର৅ͱͨ͠‫ Ͱڥ؀‬Apriori ΞϧΰϦζϜ [3] Λ༻͍ͯ‫ڞ‬௨. 3.2 ʹ‫ޙ‬ड़͢Δɽ. ͢Δ૬ؔϧʔϧΛநग़͢Δɽ͔͠͠ɼFDM ͸σʔλϚΠ. γεςϜϞσϧΛਤ 1 ʹࣔ͢ɽγεςϜʹࢀՃ͢Δҩྍ. χϯάʹ༻͍ΔࣗϊʔυͷϓϥΠϕʔτσʔλͰ͋ΔΞΠ. ‫ؔػ‬Λϊʔυͱͯ͠ѻ͏ɽϊʔυͷ૯਺Λ M ͱ͢Δɽ֤. ςϜηοτͱαϙʔτ஋ͦͷ΋ͷΛଞϊʔυ΁ૹ৴ͯ͠͠. ϊʔυʹ͸ 0 ͔Β M − 1 ·Ͱͷ ID ׂ͕ΓৼΒΕ͓ͯΓɼ. ·͏ͨΊɼ৘ใྲྀग़ͷ‫ݥة‬ੑ͕ଘࡏ͢Δɽ. ϊʔυͷ ID Λ iɼϊʔυΛ Ni (0 ≤ i < M ) ͱ‫͢ه‬ɽ·. FDM ͷ ϓ ϥ Π ό γ ʔ อ ‫ ޢ‬Λ ՝ ୊ ͱ ͠ ͨ ‫ͯ ͠ ͱ ڀ ݚ‬. ͨɼN0 Λ؅ཧऀϊʔυͱͯ͠ѻ͍ɼଞΛࢀՃऀϊʔυͱ. SFDM[4] ͕‫͛ڍ‬ΒΕΔɽ͜ͷ‫Ͱڀݚ‬͸ɼσʔλϚΠχ. ͢Δɽϊʔυ Ni ͕࣋ͭσʔλϕʔεΛ DBi ͱද͢ɽ·. ϯάʹ༻͍ΔΞΠςϜηοτͱαϙʔτ஋Λ҉߸Խ͢Δ͜. ͨɼDBi ʹ֨ೲ͞ΕΔ֤τϥϯβΫγϣϯΛ Ti,j ͱ͠ɼ. ͱͰϓϥΠόγʔอ‫ޢ‬Λߦ͍ͬͯΔɽ͔͠͠ɼ҉߸ԽΛߦ. −1 DBi = {Ti,1 ɼTi,2 ɼʜ}ɼDB = ∪M i=0 DBi ͱ͢Δɽϊʔυ. ͏ͨΊʹߴ͍‫ࢉܭ‬ίετ͕ඞཁͱͳΔͨΊɼॲཧ͕࣌ؒ૿. Ni ͕࣋ͭɼཁૉͷ਺͕ k ͷ೚ҙͷΞΠςϜηοτΛ Xi,k ɼ. Ճͯ͠͠·͏ɽ. Xi,k ʹର͢Δαϙʔτ஋Λ Vi,k ͱද͢ɽXi,k ʹ‫·ؚ‬ΕΔ. ෼ࢄσʔλϚΠχϯάʹ͓͚ΔϓϥΠόγʔอ‫ࢉܭͱޢ‬. ΞΠςϜͷ਺Λ Xi,k ͷ௕͞ͱ‫ͼݺ‬ɼ‫ٻࡏݱ‬Ί͍ͯΔසग़. ίετΛ՝୊ͱͨ͠‫ͯ͠ͱڀݚ‬ɼCRDM[1] ͕͋Δɽ͜ͷ. ΞΠςϜηοτͷ௕͞Λ len ͱද͢ɽΞΠςϜηοτ͕ස. ‫Ͱڀݚ‬͸ɺΞΠςϜηοτͷαϙʔτ஋ΛϥϯμϜͳ஋Ͱ. ग़ͱ͞ΕΔ‫ج‬४Λද͢࠷௿αϙʔτ஋Λ min sup ͱද͢ɽ. ෼ׂ͠ɼଞϊʔυΛ‫ܦ‬༝͔ͤͯ͞Βू‫ܭ‬Λߦ͏ൿີ෼ࢄ๏. min sup Ҏ্ͷαϙʔτ஋Λ࣋ͭΞΠςϜηοτΛසग़ͱ. Λ༻͍Δɽ͜ΕʹΑΓɼ҉߸ԽͳͲͷෛՙͷॏ͍ॲཧΛߦ. ͢Δɽ. ΘͣʹϓϥΠόγʔอ‫ޢ‬Λߦ͏͜ͱ͕Ͱ͖Δɽ·ͨɼϊʔ. ҩྍ‫ؔػ‬ͷσʔλϚΠχϯάΛྫͱ͢Δɽ֤ҩӃ͸ɼ੝. υؒͷ݁ୗʹΑΔ৘ใ࿙Ӯʹର͢Δ଱ੑ (݁ୗ଱ੑ) ͕ߴ. ԬපӃΛ N0 ɼୌ୔ҩӃΛ N1 ͷΑ͏ʹද‫͞ه‬ΕΔɽ·ͨɼ. ͘ɼ৘ใ࿙ӮͷͨΊʹ͸߈ܸର৅ͷϊʔυҎ֎ͷϊʔυ͢. N0 ͸σʔλϕʔε DB0 ɼN1 ͸σʔλϕʔε DB1 Λ࣋. ΂ͯͱ݁ୗ͢Δඞཁ͕͋Δɽ͔͠͠ɼϓϥΠόγʔอ‫ޢ‬ͷ. ͪɼσʔλϕʔεʹ͸‫͕ऀױ‬ૌ͑ͨ঱ঢ়ͷཤྺ͕֨ೲ͞Ε. ͨΊʹଟ਺ͷ௨৴͕ඞཁͱͳΔɽ͜ͷͨΊɼଳҬͷ‫؀͍ڱ‬. ͍ͯΔɽΞΠςϜ͸ “಄௧”΍ “‫͜ݞ‬Γ”ͷΑ͏ʹද͠ɼΞ. ‫Ͱڥ‬σʔλϚΠχϯάΛߦͬͨ৔߹ɼॲཧ͕࣌ؒ૿େ͢Δ. ΠςϜηοτ͸ X1,2 ={ ಄௧ɼ‫͜ݞ‬Γ } ͷΑ͏ʹද‫͢ه‬. Մೳੑ͕ଘࡏ͢Δɽ. Δɽ͜ͷͱ͖ɼΞΠςϜηοτ X1,2 ͷ௕͞͸ 2 ͱͳΔɽ. 3. ϓϥΠόγʔอ‫ͨ͠ޢ‬෼ࢄσʔλϚΠχϯ άʹ͓͚Δ௨৴ίετͷ࡟‫ݮ‬ख๏. min sup = 0.05 ͱͨ͠ͱ͖ɼσʔλϕʔε಺Ͱ 5%Ҏ্ͷ ׂ߹Ͱग़‫͢ݱ‬ΔΞΠςϜηοτΛɼසग़ΞΠςϜηοτͱ ͯ͢͠΂ͯநग़͢Δ͜ͱ͕໨తͱͳΔɽ. CRDM Λ༻͍ͨ෼ࢄσʔλϚΠχϯάʹ͸ɼଟ਺ͷ௨৴ ͕ඞཁͱͳΔɽຊ‫Ͱڀݚ‬͸ɼCRDM ͸σʔλϚΠχϯά ʹࢀՃ͢Δϊʔυ਺ͷ૿ՃʹΑͬͯɼա৒ͳϓϥΠόγʔ อ‫ޢ‬ੑೳΛఏ‫ʹͱ͜͏·ͯ͠͠ڙ‬஫໨͠ɼར༻ऀͷཁ‫ʹٻ‬ ߹Θͤͯ݁ୗ଱ੑ਺ΛઃఆͰ͖ΔΑ͏ʹΞϧΰϦζϜΛม ߋ͢Δ͜ͱʹΑͬͯɼ௨৴ίετͷ࡟‫ݮ‬ΛਤΔɽ. 3.1 γεςϜϞσϧ શࠃʹ఺ࡏ͢Δҩྍ‫ͯ͜͠ྗڠ͕ؔػ‬ͷγεςϜΛ༻͍ ͯɼ‫ऀױ‬ͷૌ͑ͨ঱ঢ়ͷཤྺ͔Βซൃ͠΍͍͢঱ঢ়ͷ૊Έ. ⓒ 2016 Information Processing Society of Japan. ਤ 1 ෼ࢄσʔλϚΠχϯάͷγεςϜϞσϧ. 2.

(3) Vol.2016-DPS-168 No.4 Vol.2016-SPT-21 No.4 Vol.2016-EIP-74 No.4 2016/11/17. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. 3.2 ϓϥΠόγʔͷఆٛ ্ड़ͨ͠γεςϜϞσϧͷ΋ͱͰɼ֤ϊʔυͰ‫ͨ͠ࢉܭ‬ ΞΠςϜηοτͷαϙʔτ஋Λൿີσʔλͱͯ͠ɼϓϥΠ όγʔอ‫ޢ‬ͷର৅͢Δɽ ϓϥΠόγʔอ‫ޢ‬ख๏ͱͯ͠ൿີ෼ࢄ๏Λ༻͍Δɽൿີ ෼ࢄ๏ʹର͢Δ߈ܸख๏ͷ̍ͭͱͯ͠ɼ֤ϊʔυ͕݁ୗ͠ ͯ߈ܸର৅ϊʔυͷ෼ׂͨ͠ൿີσʔλΛ͢΂ͯೖख͢Δ ͜ͱ͕ߟ͑ΒΕΔɽ͜ͷ݁ୗʹΑΔ߈ܸʹର͢Δ଱ੑΛධ Ձ͢ΔͨΊʹɼ݁ୗ଱ੑ਺ΛϓϥΠόγʔอ‫ޢ‬ੑೳͷࢦඪ ͱͯ͠༻͍Δɽ݁ୗ଱ੑ਺ͱ͸ɼ߈ܸऀ͕߈ܸϊʔυͷൿ. ਤ 2. ෼ࢄσʔλϚΠχϯάͷॲཧͷྲྀΕ (ൿີ෼ࢄॲཧ). ີσʔλΛೖख͢ΔͨΊʹɼ݁ୗ͕ඞཁͳϊʔυͷ਺ͷ͜ ͱͰ͋Δɽ ྫͱͯ͠ɼ߈ܸϊʔυ A ͕ϊʔυ B ͷαϙʔτ஋Λख ʹೖΕΔͨΊʹϊʔυ C ͱϊʔυ D ͱͷ݁ୗ͕ඞཁͰ͋ Δ৔߹ɼϊʔυ B ͷ݁ୗ଱ੑ਺͸ 2 ͱͳΔɽ ຊఏҊ͸ɼSemi-Honest ηΩϡϦςΟϞσϧ [5] Λ࠾༻ ͢Δɽ͜Ε͸ɼϢʔβ͕γεςϜΛվ͟Μ͢Δ͜ͱͳ͘ɼ γεςϜϓϩτίϧʹଇͬͯར༻͢Δ͜ͱΛࣔ͢ϞσϧͰ ͋Δɽͨͩ͠ɼϢʔβ͸γεςϜ͔Βೖྗͱग़ྗσʔλΛ ෼ੳ͢Δ͜ͱʹΑͬͯɼଞϊʔυͷϓϥΠϕʔτσʔλͷ औಘΛࢼΈΔ͜ͱ͕Ͱ͖Δɽ. 3.3 CRDM ๏ͷ෼ࢄσʔλϚΠχϯά. ਤ 3 ෼ࢄσʔλϚΠχϯάͷॲཧͷྲྀΕ (ू‫ॲܭ‬ཧ). ͷ௕͞Λ k ͱ͢Δͱɼසग़ΞΠςϜηοτީิͷαϙʔτ. CRDM ͷൿີ෼ࢄ๏Λ༻͍ͨ෼ࢄσʔλϚΠχϯάͷ. ஋ͷ‫ࢉܭ‬ɼൿີ෼ࢄ๏Λ༻͍ͨू‫ܭ‬ɼ௕͞ k ͷසग़ΞΠς. ॲཧͷྲྀΕΛਤ 2 ͱਤ 3 ʹࣔ͢ɽਤ 2 Ͱ͸ɼ͸͡Ίʹ֤. Ϝηοτͷੜ੒ɼ௕͞ k + 1 ͷසग़ΞΠςϜηοτީิͷ. ࢀՃऀϊʔυ Ni ͸ɼαϙʔτ஋Λஅยσʔλͱͯ͠ M − i. ੜ੒Λ‫܁‬Γฦ͢͜ͱͰ͢΂ͯͷසग़ΞΠςϜηοτΛੜ੒. ‫ݸ‬ͷϥϯμϜͳ஋Ͱ෼ׂ͢Δɽͦͷ‫ޙ‬ɼ෼ׂͨ͠அยσʔ. ͢Δɽ. λΛͦΕͧΕࣗ਎ΑΓ΋ ID ͷߴ͍ϊʔυ΁ૹ৴͢Δɽ. ্‫ه‬ͷΞϧΰϦζϜʹΑͬͯɼϓϥΠόγʔอ‫ͨ͠ޢ‬෼. ਤ 3 Ͱ͸ɼૹ৴͞Ε͖ͯͨஅยσʔλͱࣗ਎ͷͨΊͷஅ. ࢄσʔλϚΠχϯάΛߦ͏͜ͱ͕Ͱ͖Δɽ͔͠͠ɼൿີ෼. ยσʔλ (Vi,k,1 ) Λ͢΂ͯՃࢉ͠ɼ؅ཧऀϊʔυ΁ૹ৴͢. ࢄॲཧʹ͸ଟ਺ͷ௨৴͕ඞཁͱͳΔɽಛʹɼϊʔυ਺͕૿. Δɽ؅ཧऀϊʔυ͸ɼࢀՃऀϊʔυ͔ΒૹΒΕ͖ͯͨஅย. Ճͨ͠ͱ͖ɼ௨৴਺΋େ͖͘૿Ճ͢Δɽ͜Ε͸ൿີ෼ࢄॲ. σʔλͷ߹‫ܭ‬஋ͱࣗ਎ͷൿີσʔλΛ͢΂ͯՃࢉ͢Δ͜ͱ. ཧͰ֤ϊʔυ͕ࣗ਎ΑΓ ID ͷߴ͍͢΂ͯͷϊʔυʹஅย. Ͱɼ͢΂ͯͷϊʔυͷαϙʔτ஋ͷ߹‫ܭ‬Λ‫͠ࢉܭ‬ɼසग़Ξ. σʔλΛૹ৴͍ͯ͠Δ͜ͱ͕‫ݪ‬ҼͰ͋Δɽ. ΠςϜηοτͷ‫ࢉܭ‬Λߦ͏ɽͦͷ‫ޙ‬ɼසग़ΞΠςϜηοτ. ຊఏҊख๏͸ɼൿີ෼ࢄ๏Λ༻͍ͨ෼ࢄσʔλϚΠχϯ. ͔Βɼ࣍ͷසग़ΞΠςϜηοτͷީิΛੜ੒͢Δɽ্‫ه‬ͷ. άʹࢀՃ͢Δϊʔυͷ਺ͷ૿ՃʹΑͬͯɼա৒ͳ݁ୗ଱ੑ. ॲཧΛ௕͞ 1 ͷΞΠςϜηοτީิ͔Β‫܁‬Γฦ࣮͠ߦ͢Δɽ. Λఏ‫ʹͱ͜͏·ͯ͠͠ڙ‬஫໨͢ΔɽϢʔβʹඞཁͳ݁ୗ଱. ྫͱͯ͠ɼҩྍ‫ؔػ‬ͷσʔλϚΠχϯάʹ౰ͯ͸Ίͨॲ. ੑ਺Λࣄલʹࢦఆͯ͠΋Β͍ɼͦͷཁ‫߹ʹٻ‬க͢Δ݁ୗ଱. ཧͷྲྀΕΛड़΂Δɽ͸͡Ίʹɼ௕͞ 1 ͷΞΠςϜηοτͰ. ੑΛఏ‫͢ڙ‬ΔΑ͏ʹ CRDM Λมߋ͢Δ͜ͱͰɼϓϥΠό. ͋Δ { ಄௧ }ɼ{ ‫͜ݞ‬Γ }ɼ{ ෩अ } ͷαϙʔτ஋Λ֤ϊʔ. γʔอ‫ͨ͠ޢ‬෼ࢄσʔλϚΠχϯάͷ௨৴ίετΛ࡟‫͢ݮ‬. υͰ‫͢ࢉܭ‬Δɽͦͷ‫ޙ‬ɼൿີ෼ࢄ๏Λ༻͍֤ͯϊʔυͷ֤. Δɽख๏ͱͯ͠ɼ͸͡Ίʹઅ 3.4 ʹड़΂Δ௨৴૬खܾఆΞ. ΞΠςϜηοτͷαϙʔτ஋Λ؅ཧऀϊʔυͰू‫͢ܭ‬Δɽ. ϧΰϦζϜΛ༻͍ͯɼࣄલʹϢʔβͷཁ‫͢ٻ‬Δ݁ୗ଱ੑ਺. ू‫ܭ‬ͷ݁Ռͱͯ͠ɼmin sup Λӽ͑Δαϙʔτ஋Λ࣋ͭΞ. Λຬͨ͢Α͏ʹɼൿີ෼ࢄ๏Ͱ௨৴͢Δ૬खΛܾఆ͢Δɽ. ΠςϜηοτΛසग़ͷΞΠςϜηοτͱͯ͠நग़͢Δɽ࣍. ͦͷ‫ޙ‬ɼमਖ਼‫ޙ‬ͷ CRDM Λ༻͍ͯ෼ࢄσʔλϚΠχϯά. ʹ௕͞ 1 ͷසग़ΞΠςϜηοτ͔Β௕͞ 2 ͷසग़ΞΠςϜ. Λߦ͏ɽ͜ͷΑ͏ʹ͢Δ͜ͱͰɼ௨৴ίετͷ࡟‫ݮ‬ΛਤΔɽ. ηοτͷީิΛੜ੒͢Δɽྫͱͯ͠ɼ௕͞ 1 ͷසग़ΞΠς Ϝηοτͷ { ಄௧ }ɼ{ ‫͜ݞ‬Γ }ɼ{ ෩अ } ͔Β͸ɼ{ ಄௧ɼ. 3.4 ௨৴૬खܾఆΞϧΰϦζϜ. ‫͜ݞ‬Γ } ΍ { ಄௧ɼ෩अ }ɼ{ ‫͜ݞ‬Γɼ෩अ } ͕ੜ੒͞Ε. ఏҊख๏Ͱ͸ɼϢʔβʹࣄલʹ݁ୗ଱ੑ਺ R (1 ≤ R ≤. Δɽͦͷ‫ޙ‬͸ɼ‫͍ͯ͠ࢉܭࡏݱ‬Δසग़ΞΠςϜηοτީิ. M − 2) Λࢦఆͯ͠΋Β͍ɼൿີ෼ࢄ๏ʹൃੜ͢Δ֤ϊʔ. ⓒ 2016 Information Processing Society of Japan. 3.

(4) Vol.2016-DPS-168 No.4 Vol.2016-SPT-21 No.4 Vol.2016-EIP-74 No.4 2016/11/17. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. υͷૹ৴਺ͱड৴਺ͷ߹‫ܭ‬Λ R ʹ੍‫͢ݶ‬Δ͜ͱʹΑͬͯɼ ϢʔβͷϓϥΠόγʔอ‫ʹޢ‬ର͢Δཁ‫ٻ‬Λຬͨͭͭ͠σʔ λϚΠχϯάΛߦ͏ɽ ۩ମతʹ͸ɼൿີ෼ࢄॲཧΛߦ͏લʹɼ֤ϊʔυ͕அย σʔλΛ΍ΓͱΓ͢ΔϊʔυΛܾఆ͢Δ͜ͱͰɼ݁ୗ଱ੑ ͷௐ੔Λߦ͏ɽ͜͜Ͱ͸ɼࣗ਎ͷஅยσʔλΛ౉͢ଞϊʔ υͷϦετΛૹ৴ઌϦετɼଞϊʔυ͔ΒஅยσʔλΛड ͚औΔඞཁ͕͋ΔଞϊʔυͷϦετΛड৴ઌϦετͱ‫ݺ‬ ͿɽຊఏҊख๏Ͱ͸ɼࣄલʹਤ 4 ʹࣔ͢ΞϧΰϦζϜΛ༻ ͍ͯɼૹ৴ઌϦετͱड৴ઌϦετΛੜ੒͢Δɽͳ͓ɼຊ. ਤ 5 N5 ͷૹ৴ઌϦετͱड৴ઌϦετͷੜ੒ͷྲྀΕ. ΞϧΰϦζϜ͸֤ࢀՃऀϊʔυ಺Ͱ࣮ߦ͠ɼ͢΂ͯͷࢀՃ ऀϊʔυͷૹ৴ઌϦετͱड৴ઌϦετΛੜ੒͢Δɽͦͷ ‫ޙ‬ɼੜ੒͞Εͨࣗ਎ͷϊʔυͷૹ৴ઌϦετͱड৴ઌϦε τΛൿີ෼ࢄ๏ʹ༻͍Δɽ Input. Ϣʔβͷཁ‫͢ٻ‬Δ݁ୗ଱ੑ਺ R Output. ૹ৴ઌϦετͱड৴ઌϦετ Step.1 ֤ࢀՃऀϊʔυ Ni (1 ≤ i < M ) ͷͨΊͷૹ৴ઌϦετ ͱड৴ઌϦετΛॳ‫ظ‬Խ͢ΔͨΊʹɼi ΑΓ΋ ID ͕ߴ͍͢΂ͯ ͷࢀՃऀϊʔυΛ Ni ͷૹ৴ઌϦετʹ௥Ճ͢Δɽ·ͨɼi ΑΓ ΋ ID ͕௿͍͢΂ͯͷࢀՃऀϊʔυΛ Ni ͷड৴ઌϦετʹ௥ Ճ͢Δɽ Step.2 ID ͷߴ͍ࢀՃऀϊʔυ Ni ͷϦετ͔ΒॱʹɼNi ͷૹ৴ઌ ϊʔυͷ਺ͱड৴ઌϊʔυͷ਺ͷ߹‫ ͕ܭ‬R ʹͳΔ·Ͱ Step.2.1 ͱ Step.2.2 Λߦ͏ɽ Step.2.1 Ni ΑΓ΋ ID ͷ௿͍ࢀՃऀϊʔυͷதͰɼૹ৴ઌϊʔυ ͷ਺ͱड৴ઌϊʔυͷ਺ͷ߹‫࠷͕ܭ‬େͰ͋ΔࢀՃऀϊʔυͷ ID Λ͢΂ͯ‫ٻ‬ΊΔɽ Step.2.2 Step.2.1 Ͱ‫ٻ‬ΊͨϊʔυͷதͰɼID ͕௿͍ϊʔυ (Nj ) Λ༏ઌͯ͠બ୒͠ɼNi ͷड৴ઌϦετ͔Β Nj Λ࡟আ͢Δɽ· ͨɼNj ͷૹ৴ઌϦετ͔Β Ni Λ࡟আ͢Δɽ͜ͷ 2 ͭͷॲཧ͸ɼ Nj ͷૹड৴ઌͷϊʔυͷ਺ͷ߹‫ ͕ܭ‬R Ͱ͋Ε͹࣮ߦ͠ͳ͍ɽ ਤ 4. ૹ৴ઌϦετͱड৴ઌϦετͷੜ੒ΞϧΰϦζϜ. ਤ 6 N4 ͷૹ৴ઌϦετͱड৴ઌϦετͷੜ੒ͷྲྀΕ. ʹࣔ͢ N4 ʹର͢ΔॲཧͰ͸ɼ͸͡Ίʹ௨৴਺͕ଟ͍ N3 ༏ઌͯ͠௨৴ઌ͔Βআ֎͢Δɽͦͷ‫ޙ‬ɼ͞Βʹ௨৴਺Λ࡟ ‫͢ݮ‬ΔͨΊʹɼID ͷ௿͍ N1 Λ௨৴ઌ͔Βআ֎͢Δɽ͜ͷ ํ਑ʹΑΓɼN1 ͷΈ௨৴͕ଟ͘ͳΔͱ͍ͬͨ௨৴ͷภΓ Λ๷͗ɼ༨෼ͳ௨৴Λ‫ݮ‬গͤ͞Δɽ ਤ 4 ʹࣔ͢ૹ৴ઌϦετͱड৴ઌϦετͷੜ੒ΞϧΰϦ ζϜΛ༻͍ͯੜ੒ͨ͠ૹ৴Ϧετͱड৴ϦετͷྫΛɼද. 1 ʹࣔ͢ɽ͜ͷྫͰ͸ɼϊʔυ਺Λ 6ɼϢʔβͷཁ‫͢ٻ‬Δ Step.1 Ͱ͸ɼ؅ཧऀϊʔυҎ֎ͷࢀՃऀϊʔυΛ௨৴૬. ݁ୗ଱ੑ਺ R Λ 2 ͱͨ͠৔߹ͷϦετΛͦΕͧΕ͍ࣔͯ͠. खͱͯ͠બ୒ͤ͞Δɽͨͩ͠ɼϊʔυಉ͕࢜ࣗ਎ͷஅย. ΔɽදΑΓɼ֤ϊʔυͷ௨৴਺͕ࢦఆ͞Εͨ݁ୗ଱ੑ਺ R. σʔλΛ౉͋͠͏ͱϓϥΠόγʔอ‫ޢ‬ੑೳ͕Լ͕ͬͯ͠·. ͷ஋Ͱ͋Δ 2 ʹͳ͍ͬͯΔ͜ͱ͕Θ͔Δɽ. ͏ɽ͜ΕΛ๷͙ͨΊʹɼID ͷ௿͍ϊʔυ͕ ID ͷߴ͍ϊʔ. ද 1 ੜ੒͞ΕΔૹ৴Ϧετͱड৴Ϧετͷྫ. υ΁அยσʔλΛ౉͢ϧʔϧΛઃ͚ΔɽͦͷͨΊɼ֤ࢀՃ ऀϊʔυ Ni ʹରͯ͠ɼi ΑΓ ID ͷߴ͍ϊʔυΛ Ni ͷૹ ৴ઌϦετʹ௥Ճ͠ɼi ΑΓ ID ͷ௿͍ϊʔυΛ Ni ͷड৴ ઌϦετʹ௥Ճ͢Δɽ. Step.2 Ͱ͸ɼΑΓଟ͘ͷ௨৴Λඞཁͱ͢ΔࢀՃऀϊʔυ Λ༏ઌతʹ௨৴૬ख͔Βআ֎͢Δ͜ͱͰɼ֤ࢀՃऀϊʔυ ͷ௨৴਺Λ R ΁ௐ੔͢ΔॲཧΛߦ͏ɽ֤ϊʔυͷ௨৴਺͕. ্‫ه‬ͷΞϧΰϦζϜΛ༻͍ͨ‫ޙ‬ɼੜ੒ͨ͠ૹ৴ઌϦετ. R ҎԼʹͳΔ͜ͱΛ๷͙ͨΊʹɼૹड৴ઌͷϊʔυͷ਺ͷ. ͱड৴ઌϦετΛ༻͍ͯɼ֤ϊʔυ͕‫ͨ͠ࢉܭ‬αϙʔτ஋. ߹‫ ͕ܭ‬R ͷϊʔυʹରͯ͠͸ॲཧΛߦΘͳ͍ϧʔϧΛઃ͚. ͷू‫ܭ‬Λߦ͏ɽू‫ॲܭ‬ཧΞϧΰϦζϜΛਤ 7 ʹࣔ͢ɽ. ΔɽStep.2 ͷॲཧͷྲྀΕΛਤ 5 ͱਤ 6 ʹࣔ͢ɽ͜͜Ͱ͸ɼ ֤ϊʔυͷ௨৴਺Λ 2 ʹ੍‫͢ݶ‬Δ͜ͱΛ໨ඪͱ͢Δɽ ਤ 5 ʹࣔ͢ N5 ʹର͢ΔॲཧͰ͸ɼଞͷ͢΂ͯͷϊʔυ. ू‫ॲܭ‬ཧΞϧΰϦζϜΛ༻͍ͨॲཧͷྲྀΕͷྫΛਤ 8 ͱ ਤ 9 ʹࣔ͢ɽ͜ͷྫͰ͸ɼϊʔυ਺͸̒ɼϢʔβͷཁ‫͢ٻ‬ Δ݁ୗ଱ੑ਺Λ̎ͱͨ͠ɽ. ͷ௨৴਺͕ 4 ͳͷͰɼID ͷ௿͍ N1 ͱ N2 ͷ 2 ͭΛ௨৴ઌ. ਤ 8 Ͱ͸ɼ෼ׂͨ͠அยσʔλ Vi,k,j Λଞͷϊʔυ΁. ͔Βআ֎͢Δ͜ͱͰɼࣗ਎ͷ௨৴਺Λ 2 ʹ੍‫͢ݶ‬Δɽਤ 6. ૹ৴͢Δൿີ෼ࢄॲཧͷྲྀΕΛ͍ࣔͯ͠Δɽ֤ϊʔυ͸ɼ. ⓒ 2016 Information Processing Society of Japan. 4.

(5) Vol.2016-DPS-168 No.4 Vol.2016-SPT-21 No.4 Vol.2016-EIP-74 No.4 2016/11/17. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. Input. ֤ϊʔυͷૹ৴ઌϦετͱड৴ઌϦετ Output. ൿີ෼ࢄ๏ʹΑͬͯɼ͢΂ͯͷϊʔυͰ‫ڞ‬௨͢Δ௕͞ k ͷසग़ΞΠςϜηοτΛநग़͢Δɽ Step.1 ֤ϊʔυ͸ɼࣗ਎͕‫ͨ͠ࢉܭ‬αϙʔτ஋ΛϥϯμϜͳ஋Ͱ ૹ৴ઌϊʔυͷ਺ +1 ͷ਺ͷஅยσʔλʹ෼ׂ͢Δɽ Step.2 ֤ϊʔυ͸ɼ෼ׂͨ͠அยσʔλΛૹ৴ઌϦετͷϊʔυ ʹͦΕͧΕૹ৴͢Δɽ Step.3 ֤ϊʔυ͸ɼૹΒΕ͖ͯͨஅยσʔλͱࣗ਎ͷͨΊͷஅย σʔλΛ͢΂ͯՃࢉ͢Δɽ Step.4 ֤ϊʔυ͸ɼՃࢉͨ͠஋Λ؅ཧऀϊʔυ΁ૹ৴͢Δɽ Step.5 ؅ཧऀϊʔυ͸ɼStep.3 Ͱ‫͞ࢉܭ‬Εͨ஋Λ֤ϊʔυ͔Β ड͚औΓɼࣗ਎ͷαϙʔτ஋ͱड͚औͬͨ஋ͷ߹‫ܭ‬Λ‫͢ࢉܭ‬Δɽ ͦͷ‫ޙ‬ɼ‫ͨ͠ࢉܭ‬஋Λ min sup ͱൺֱͯ͠සग़ΞΠςϜηοτ Λੜ੒͢Δɽ ਤ 7 ϓϥΠόγʔอ‫ͨ͠ޢ‬෼ࢄσʔλϚΠχϯάΞϧΰϦζϜ. 4. ੑೳධՁ ຊઅͰ͸ɼఏҊख๏ͷ݁ୗ଱ੑͷධՁΛߦ͏ɽ·ͨɼ෼ ࢄσʔλϚΠχϯάʹඞཁͳ௨৴ίετʹ͍ͭͯ‫ط‬ଘ‫ڀݚ‬ Ͱ͋Δ CRDM ͱൺֱΛߦ͏ɽ. 4.1 ݁ୗ଱ੑʹ͍ͭͯ ؔ࿈‫͋Ͱڀݚ‬Δ CRDM ͷ݁ୗ଱ੑ਺͸ɼM − 2 ͱͳΔɽ ͜ͷ஋͸ɼ߈ܸϊʔυ͸߈ܸର৅ͷϊʔυҎ֎ͷ͢΂ͯͷ ϊʔυͱ݁ୗ͢Δඞཁ͕͋Δ͜ͱΛࣔ͢ɽ͔͠͠ɼϊʔυ ਺͕૿Ճ͢Δ͜ͱʹΑͬͯա৒ͳ݁ୗ଱ੑΛఏ‫·ͯ͠͠ڙ‬ ͏ɽྫͱͯ͠ɼ100 ΋ͷϊʔυ͕σʔλϚΠχϯάʹࢀՃ ͨ͠৔߹ɼ࣮ࡍʹ͸݁ୗ଱ੑ਺͸ 10 Ͱे෼Ͱ͋Δʹ΋ؔ ΘΒͣɼ݁ୗ଱ੑ਺͕ 98 ͷ‫ॲͰڥ؀‬ཧΛߦ͏ɽ ఏҊख๏ͷΞϧΰϦζϜΛ༻͍ͨ৔߹ɼ֤ϊʔυͷ݁ୗ ଱ੑ਺͸ਤ 4 ʹड़΂ͨΞϧΰϦζϜʹΑͬͯɼ෼ׂͨ͠α ϙʔτ஋ͷૹ৴ͱड৴ͷ਺Λ R ʹͳΔΑ͏ʹௐ੔͞ΕΔͨ Ίɼ݁ୗ଱ੑ਺͸Ϣʔβͷཁ‫͢ٻ‬Δ݁ୗ଱ੑ਺ R ͱͳΔɽ. 4.2 ௨৴ίετͷൺֱ ຊ‫Ͱڀݚ‬͸ɼ௨৴ίετΛʮൿີ෼ࢄॲཧͰൃੜ͢Δࢀ ਤ 8. ఏҊख๏Λ༻͍ͨ෼ࢄσʔλϚΠχϯάͷॲཧͷྲྀΕ (ൿີ෼. Ճऀϊʔυؒͷ௨৴ͷ਺ʯͱ͢Δɽ֤ϊʔυ͸ɼૹ৴ઌϦ. ࢄॲཧ). ετͱड৴ઌϦετʹ‫͞ه‬Εͨϊʔυͷ਺͚ͩ௨৴Λߦ͏ɽ ຊఏҊख๏ͷૹ৴ઌϦετͱड৴ઌϦετͷੜ੒ΞϧΰϦ ζϜʹΑͬͯɼ֤ϊʔυͰൃੜ͢Δ௨৴਺͸ R ʹ੍‫ͯ͠ݶ‬ ͍ΔɽͦͷͨΊɼϊʔυ਺Λ M ɼϢʔβͷཁ‫͢ٻ‬Δ݁ୗ଱ ੑ਺Λ R ͱ͢Δͱɼ֤ϊʔυ͕௨৴͢Δ਺Ͱ͋Δ R ͱࢀ Ճऀϊʔυͷ਺ M − 1 Λ͔͚ɼૹड৴ͷॏෳΛআ֎͢Δͨ Ίʹ 2 Ͱׂͬͨ஋͕௨৴ίετͱͳΔɽ ຊఏҊख๏ʹΑͬͯൃੜ͢Δ௨৴ίετͷཧ࿦஋͸ɼ ʢ(M − 1) ʷ. R 2 ʣͱͳΔɽ͜ͷࣜΛ֬ೝ͢ΔͨΊʹɼϊʔ. υ਺ͱϢʔβͷཁ‫͢ٻ‬Δ݁ୗ଱ੑ਺ΛͦΕͧΕมԽͤ͞ɼ ਤ 9. ఏҊख๏Λ༻͍ͨ෼ࢄσʔλϚΠχϯάͷॲཧͷྲྀΕ (ू‫ܭ‬ ॲཧ). ཧ࿦஋ͱ࣮ࡍͷ௨৴ίετͷൺֱΛߦͬͨɽൺֱͨ݁͠Ռ Λਤ 10 ʹࣔ͢ɽ͜ͷਤͰ͸ɼϢʔβ͕ཁ‫͢ٻ‬Δ݁ୗ଱ੑ ਺RΛ. M −1 2. ͱ 23 (M − 1) ͱ͍ͯ͠Δɽ. ࣗ਎͕‫ͨ͠ࢉܭ‬αϙʔτ஋ Vi,k ΛϥϯμϜͳ஋Ͱૹ৴ઌ ϊʔυͷ਺ +1 ͷ਺ͷஅยσʔλʹ෼ׂ͢Δɽ෼ׂͨ͠அ ยσʔλΛૹ৴ઌϦετʹࣔ͞Εͨϊʔυ΁ૹ৴͢Δɽ ਤ 9 Ͱ͸ɼࢀՃऀϊʔυ Ni ͸ड৴ઌϦετʹࣔ͞Εͨ ϊʔυ͔Βड৴ͨ͠அยσʔλͱࣗ਎ͷͨΊͷஅยσʔλ. Vi,k,1 Λ͢΂ͯՃࢉ͠ɼ؅ཧऀϊʔυ΁ૹ৴͢ΔྲྀΕΛࣔ ͍ͯ͠Δɽ؅ཧऀϊʔυ͸͢΂ͯͷϊʔυ͔Βஅยσʔλ ͷ߹‫ܭ‬஋Λड͚औΓɼࣗ਎ͷαϙʔτ஋ͱՃࢉ͢Δ͜ͱͰ ͢΂ͯͷϊʔυͷαϙʔτ஋Λू‫͢ܭ‬Δ͜ͱ͕ग़དྷΔɽ Ҏ্ͷॲཧʹΑΓɼ֤ϊʔυͷαϙʔτ஋Λൿಗ͠ͳ͕ Β෼ࢄσʔλϚΠχϯάͷू‫ॲܭ‬ཧΛߦ͏͜ͱ͕Ͱ͖Δɽ ·ɼ֤ϊʔυͷ௨৴਺Λ R ʹ੍‫͢ݶ‬Δ͜ͱͰɼগͳ͍௨৴ ਺Ͱू‫ॲܭ‬ཧΛߦ͏͜ͱ͕Ͱ͖Δɽ. ⓒ 2016 Information Processing Society of Japan. ਤ 10. ௨৴ίετͷཧ࿦஋ͱ࣮ࡍͷ஋ͷൺֱ. 5.

(6) Vol.2016-DPS-168 No.4 Vol.2016-SPT-21 No.4 Vol.2016-EIP-74 No.4 2016/11/17. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ਤ 10 ΑΓɼཧ࿦஋ͱ࣮ࡍͷ௨৴ίετ͸΄΅Ұகͯ͠ ͓ΓɼຊఏҊख๏Ͱൃੜ͢Δ௨৴ίετ͸ʢ(M − 1) ʷ. R 2ʣ. ্‫ه‬ͷཧ࿦஋Λ༻͍ͨ௨৴ίετʹ͓͚ΔఏҊख๏ͱ. CRDM ͷൺֱ݁ՌΛਤ 11 ʹࣔ͢ɽఏҊख๏Ͱ͸ɼϢʔβ ͕ཁ‫͢ٻ‬Δ݁ୗ଱ੑ਺ R Λ. ͱ. ຊఏҊख๏Λ༻͍Δ͜ͱʹΑͬͯɼ֤ϊʔυ͸ࢦఆͨ͠ ݁ୗ଱ੑ਺ R Λຬͨͨ͠‫Ͱڥ؀‬෼ࢄσʔλϚΠχϯάΛߦ. Ͱಋ͘͜ͱ͕Ͱ͖Δ͜ͱ͕Θ͔Δɽ. M −1 2. 4.4 ߟ࡯. 2 3 (M. − 1) ͱͨ͠৔߹. ͏͜ͱ͕Ͱ͖Δɽ ͞Βʹਤ 11 ΑΓɼຊఏҊख๏Λ༻͍Δ͜ͱʹΑͬͯɼR Ͱׂࣔͨ͠߹·Ͱ௨৴ίετΛ࡟‫͕ͱ͖ͨ͜Ͱݮ‬Θ͔Δɽ ·ͨɼϊʔυ਺͕૿Ճ͢ΔʹͭΕͯɼCRDM ΑΓ΋௨৴ί. ͷ݁ՌΛൺֱʹ༻͍ͨɽ. ετΛେ͖͘࡟‫͖Ͱݮ‬Δɽ͜ΕʹΑΓɼωοτϫʔΫଳҬ ͷѹഭʹΑΔ௨৴࣌ؒͷ૿ՃΛ཈͑Δ͜ͱ͕‫ظ‬଴Ͱ͖Δɽ ͔͠͠ɼ࣮‫͍͓ͯʹڥ؀ݧ‬͸ɼCRDM ͱఏҊख๏ͷॲཧ ࣌ؒͷେ͖ͳมԽ͸‫ݟ‬ΒΕͳ͔ͬͨɽ͜Ε͸ɼ୯Ұͷ PC Ͱར༻‫ڥ؀‬Λ࠶‫ͨͨ͠ݱ‬ΊʹɼωοτϫʔΫଳҬ͕े෼ʹ ޿͘ɼଳҬͷѹഭʹΑΔॲཧ࣌ؒͷ૿Ճ͕ൃੜ͠ͳ͔ͬͨ ͜ͱ͕ߟ͑ΒΕΔɽࠓ‫ޙ‬͸ɼଳҬͷ‫ॲͰڥ؀͍ڱ‬ཧ࣌ؒͷ มԽΛ‫ܭ‬ଌ͠ɼ࠶ධՁΛߦ͏͜ͱͰຊ‫ڀݚ‬ͷ༏ҐੑΛ֬ೝ ͢Δɽ. 5. ·ͱΊ ਤ 11. ௨৴ίετͷൺֱ. ຊ࿦จ͸ɼҩྍ‫ؔػ‬ͷΑ͏ͳෳ਺஍Ҭʹ·͕ͨͬͯ఺ࡏ ͍ͯ͠ΔҩӃͷσʔλϕʔεΛର৅ͱͨ͠෼ࢄ‫ܕ‬૬ؔϧʔ ϧϚΠχϯάͷϓϥΠόγʔอ‫ͱޢ‬௨৴ίετͷ࡟‫ݮ‬ख๏. 4.3 ॲཧ࣌ؒͷൺֱ. ΛఏҊͨ͠ɽར༻ऀͷཁ‫͢ٻ‬Δ݁ୗ଱ੑ਺ʹ߹Θͤͯϓϥ. ͜͜Ͱ͸ɼॲཧ࣌ؒʹ͓͚ΔఏҊख๏ͱ CRDM Λൺֱ. Πόγʔอ‫ॲޢ‬ཧʹඞཁͳ௨৴Λ੍‫͢ޚ‬Δ͜ͱͰɼ௨৴ί. ͨ݁͠ՌΛࣔ͢ɽσʔλϚΠχϯάʹ༻͍࣮ͨ‫ڥ؀ݧ‬Λද. ετͷ࡟‫ݮ‬ΛਤͬͨɽੑೳධՁͰ͸ɼཁ‫͢ٻ‬Δ݁ୗ଱ੑ਺. 2 ʹࣔ͢ɽ·ͨɼ෼ࢄσʔλϚΠχϯάʹ༻͍ͨύϥϝʔ. Λຬͨ͢‫Ͱڥ؀‬σʔλϚΠχϯά͕Ͱ͖Δ͜ͱΛࣔͨ͠ɽ. λΛද 3 ʹࣔ͢ɽද 2 ͱද 3 ʹࣔͨ͠‫ॲͰڥ؀‬ཧ࣌ؒΛ. ͞Βʹɼ௨৴ίετʹ͍ͭͯؔ࿈‫͋Ͱڀݚ‬Δ CRDM ͱൺ. ൺֱͨ݁͠ՌΛද 4 ʹࣔ͢ɽ. ֱΛߦ͍ɼগͳ͍௨৴਺ͰσʔλϚΠχϯά͕ߦ͑Δ͜ͱ. ද 2 ࣮‫ڥ؀ݧ‬. Λࣔͨ͠ɽ͜ΕʹΑΓɼωοτϫʔΫଳҬͷѹഭʹΑΔ௨ ৴࣌ؒͷ૿ՃΛ཈͑Δ͜ͱ͕‫ظ‬଴Ͱ͖Δɽࠓ‫ޙ‬͸ɼଳҬͷ ‫ॲͰڥ؀͍ڱ‬ཧ࣌ؒͷมԽΛ‫ܭ‬ଌ͠ɼ࠶ධՁΛߦ͏͜ͱͰ ॲཧ࣌ؒʹ͓͚Δຊ‫ڀݚ‬ͷ༏ҐੑΛ֬ೝ͢Δɽ ࢀߟจ‫ݙ‬ [1]. ද 3. ෼ࢄσʔλϚΠχϯάʹ༻͍ͨύϥϝʔλ. [2]. [3]. [4] ද 4. ॲཧ࣌ؒͷൺֱ. [5]. ⓒ 2016 Information Processing Society of Japan. S. Urabe, J. Wang, E. Kodama, T. Takata : A High Collusion-Resistant Approach to Distributed Privacy-preserving Data Mining, IPSJ Transactions on Databases, Vol. 48, No. SIG 11, pp.104–117, 2007. D.W. Chung, J. Han, V.T. Ng, A.W. Fu, and Y. Fu : Fast Distributed Algorithm for Mining Association Rules, Proc. International Conference on Parallel and Distributed Information Systems, pp.31–42, 1996. R. Agrawal, R. Srikant : Fast Algorithms for Mining Association Rules in Large Databases, Proc. 20th International Conference on Very Large Data Bases, pp.487– 499, 1994. M. Kantarcioglu and C. Clifton : Privacy-preserving Distributed Mining of Association Rules on Horizontally Partitioned Data, IEEE Transaction on Knowledge and Data Engineering, Vol.16, No.9, pp.1026–1037, 2004. Goldreich, O: Secure multi-party computation (working draft), Available from <http://www.wisdom.weizmann. ac.il/˜oded/pp.html>(Sept. 1998).. 6.

(7)