テックレポート - TechReport

一覧はこちら

  • now_btn.png
  • ameblo_btn.png

wavelet行列で高速な「もしかして友だち？」検索

執筆者

執筆者：
井上ゆり
所属部署：
アドテク本部 アドテクスタジオ
業務経歴：
Sierでのソフトウェア開発・大手メディアでのサービス運用を経て2012年サイバーエージェント入社。
アメーバ事業本部コミュニティサービスの開発責任者を経て、現在はアドテクスタジオで広告配信技術に注力。
好きな分野はグラフ探索とチューリングマシン。

概要

ソーシャルサービスでは、ユーザ間のつながりやユーザ同士の類似性がとても重要です。

つながりの近いユーザや自分と似ているユーザを「もしかして友だち？」とサジェストすることでユーザ間のつながりを伸展させることができます。

そこで、ユーザの「つながり」具合が似ているユーザを「友だちかもしれないユーザ」としてサジェストを行うことを考えました。

しかし「つながり」のデータというのはユーザ数のベキ乗であるため、容量が大きくなりやすい性質があります。

即ち、「つながり」類似度の算出には時間がかかる、ということです。

この「つながり」類似度算出を高速に行うため、ウェーブレット行列をインデックスとして使ったシステムを提案致します。

補足

本レポートで使用するプログラムコードはすべてscalaで記述しました。
requirement >= scala2.10

目次

 

1. ウェーブレット行列とは

ウェーブレット行列は計算量が定数時間のrank, selectなどをサポートする簡潔データ構造です。

「ウェーブレット行列とは」を説明することはこのレポートの趣旨ではないので、詳細は下記のスライドをご参照ください。

ウェーブレット木の世界

2. システム概要

本レポートで提案するシステムは、

  1. ユーザ間のリレーションデータからwavelet行列インデックスを作成
  2. wavelet行列インデックスから類似度検索

を主軸とします。

2-1. システム概要図

下記に検索システムの概要図を掲載します。

201404221553_1-708x0.png

  • リレーションデータストア：ノード間のリレーション（フォロー／フォロワーなど）を保持しているデータストアです。
    • これらのデータはRDBに保持されていることもあればKVSに保持されていることもあるでしょう。APIから取得するケースも考えられます。
  • wavelet行列データストア：wavelet行列を格納するためのデータストアです。

2-2. データモデル

下記にリレーションデータのデータモデル例とwavelet行列のデータモデルを表示します。

201404221548_1-708x0.png

リレーションデータモデルは一例です。上記と同じ形である必要はありません。

2-3. JSON例

上記のwavelet行列データモデルをJSON形式であらわした例を記します。


wavelet
{"wavelet" : [
   {
      "bit_level" : 0
     ,"vector" : [ 0, 1, 0, 0, .. 1 ]
     ,"size" : 31
     ,"zero" : 19
   }, {
      "bit_level" : 1
     ,"vector" : [ 1, 1, 0, 1, .. 0 ]
     ,"size" : 31
     ,"zero" : 12
   }, {
    :
   }, {
      "bit_level" : n
     ,"vector" : [ 1, 0, 1, 1, .. 0 ]
     ,"size" : 31
     ,"zero" : 10
   }
]}
node_attributes
{"node_attributes" : {
   "size"       : 16
  ,"latest_id" : 60,096
}}
index_attributes
{"index_attributes" : {
   "status"        : "latest"
  ,"current_level" : 12
}}

3. インデクシング

先に記述したとおり、ウェーブレット行列を検索に用いるためにはウェーブレット行列のインデックスを作成する必要があります。

3-1. ウェーブレット行列インデックスの作成

ユーザをノード、つながりをリレーションとしたグラフからウェーブレット行列を作成します。

201404221548_2-708x0.png

3-1-1. インデックス作成フロー

1. エッジの終点ノードをすべてbit表現に変換します。

201404221548_3-708x0.png

 

2. 1で作成した全ノードの最上位ビットを1つの配列に格納し、ウェーブレット行列の行0とします。

201404221548_4-708x0.png

上図の赤枠で囲まれたビット配列をウェーブレット行列の行0に格納します。

JSON例
{"wavelet" : [The Wavelet Matrix|http://www.dcc.uchile.cl/~gnavarr/ps/spire12.4.pdf]
   ,"size"        : 31
   ,"zero"        : 19
}]}

3. 最上位ビットが0だったノードの次ビットを順番に別の配列に格納します。（順番は保持したまま）

201404221548_5-708x0.png

上図の下表の赤枠で囲まれたビット配列をウェーブレット行列の行1に先頭から格納します。

4. つづけて最上位ビットが1だったノードの次ビットを3の配列に追加します。（順番は保持したまま）

201404221548_6-708x0.png

上図の下表の赤枠で囲まれたビット配列をウェーブレット行列の行1の末尾に追加します。

5. これを終わりまで繰り返します。

201404221548_7-708x0.png

要は基数ソートです。

 

6. 最後に、それぞれのビットレベルのゼロの個数を保持しておきます。

これでウェーブレット行列インデックスの完成です。

3-2. ウェーブレット行列インデックスのデータ容量

ウェーブレット行列インデックスが必要とするデータ容量は下記の通りであることがわかっています。

n log σ
n: リレーション数
σ: ビット長

The Wavelet Matrix

ビット長が十分に大きければ（≒即ちノード数が多いということ）、リレーション数と同程度になります。

3-3. ウェーブレット行列インデックス作成の実装例

rank(scala)
package ly.inoueyu.wavelet

import scala.collection.immutable._
import scala.collection.mutable
import org.slf4j.LoggerFactory
import scala.collection.mutable.ListBuffer

/**
* waveletインデックスを作成します。
*
* Created with IntelliJ IDEA.
* User: inoue_yuri
* Date: 2013/09/26
* Time: 16:33
*/
class Indexer( length: Int ) extends Compute {

   val log = LoggerFactory.getLogger( this.getClass )

   def generate( rels: Relations ) : WaveletMatrix = {

      // 各ノードをBitSetに変換します。
      val bits = flatten( rels.getAll.length-1, rels, Array.empty )

      // ビットの並び順を保持します。
      var preZero = new ListBuffer[Int]()
      var preOne = new ListBuffer[Int]()

      for ( n <- 0 to bits.length-1 )
      { preZero += n }

      val matrix = new WaveletMatrix( length )

      for ( n <- length-1 to 0 by -1) {

         // この操作で0の左寄寄せ、1の右寄せを行っています。
         val order : List[Int] = preZero.toList ++ preOne.toList
         preOne.clear()
         preZero.clear()

         val cols = new mutable.BitSet()

         for ( m <- 0 to bits.length-1 ) {
            val o = order( m )
            if ( bits( o )( n ) ) {
               cols += m
               preOne += o
            } else {
               preZero += o
            }
         }

         val rowIndex = ( length - 1 - n )
         matrix.update(
            rowIndex
            ,matrix.WaveletRow( rowIndex, cols, bits.length, preZero.length ) )
         }

         val order = ( preZero.toList ++ preOne.toList ).toArray
         var current = -1

         for ( n <- 0 to order.length-1 ) {
            val value = intValue( bits( order( n ) ) )
            if ( value != current ) {
               current = value
               matrix.updateIndex( current, n )
            }
         }

         for ( n <- matrix.length-1 to 1 ) {
            val row = matrix.get( n )
            matrix.update(
               n
               ,matrix.WaveletRow( n, row.vector, row.bitLevel, matrix.get( n-1 ).zero ) )
            }
            matrix
         }

         private def flatten( index: Int, rels: Relations, previous : Array[BitSet] ) : Array[BitSet] = {
            val converted = index match {
               case i if ( i < 0 ) => Array.empty
               case i if ( i == 0 ) => long2BitSet( rels.get( index ).end )
               case _ => flatten( index-1, rels, long2BitSet( rels.get( index ).end ) )
            }
            converted ++ previous
         }

         private def long2BitSet( nodes: Array[Long] ) : Array[BitSet] = {
            nodes match {
               case a:Array[Long] =>
               a.map {
                  n => BitSet.fromBitMaskNoCopy( Array( n ) )
               }
            case _ =>
               Array.empty
         }
      }
   }

4. 検索基本操作のオーダー

4-1. 出現数を返すrank

出現数が多い終端ノード≒人気のあるノードということになります。

通常の場合、データサイズが大きくなるとサイズに比例した時間がかかりますが、ウェーブレット行列を使うと、

rankn = Rl[[i/l]]+Rs[[i/l]]+popcount(u/[i/u], i mod u)

として計算することができ

Rl, Rs, popcountはnの準線形であることから、計算量は

O( n )

となります。

4-1-1. rankの実装例
rank(scala)
package ly.inoueyu.wavelet

import scala.collection.immutable._
import scala.collection.mutable
import org.slf4j.LoggerFactory

/**
 * Created with IntelliJ IDEA.
 * User: inoue_yuri
 * Date: 2013/09/28
 * Time: 13:59
 */
class Rank( matrix : WaveletMatrix ) extends Compute {

   val log = LoggerFactory.getLogger( this.getClass )

   def getRank( target: Long, index: Int ) : Int = {

      val bit = BitSet.fromBitMaskNoCopy( Array( target ) )
      val pos = pointer( 0, matrix.length-1, index, bit )

      pos - matrix.getStart( target.toInt ) + 1
   }

   def getRank( target: Long, start: Int, end: Int ) : Int = {

      val bit = BitSet.fromBitMaskNoCopy( Array( target ) )

      val startPos = pointer( 0, matrix.length-1, start, bit )
      val excessCount = startPos - matrix.getStart( target.toInt ) + 1

      val endPos = pointer( 0, matrix.length-1, end, bit )
      val count = endPos - matrix.getStart( target.toInt ) + 1

      log.debug( "all_count:{}, excess_count:{}.", count, excessCount )

      count - excessCount
   }

   private def count( index: Int, isSame: Boolean, bit : mutable.BitSet ) : Int = {
      index match {
         case x
            if x < 0 => 0
         case _ => count( index-1, isSame, bit ) + ( if ( bit( index ) ^ isSame ) 0 else 1 )
      }
   }

   private def pointer( current: Int, level: Int, end: Int, bit : BitSet ) : Int = {

      val index = current match {
         case `level` => end
         case _ => pointer( current+1, level, end, bit )
      }

      val reverse = level - current
      val num = count( index, bit( current ), matrix.get( reverse ).vector ) -1

      if ( bit( current ) )
         num + matrix.get( reverse ).zero
      else
         num
   }
}
object Rank {
   def apply( matrix : WaveletMatrix ) = new Rank( matrix )
}

4-2. 最初に出現するものを返すselect

rankを反対にたどるとselectが実現できます。

よってselectの計算量も

O( n ) -> O( 1 )

となります。

4-3. 共通して出現するものと頻度を返すintersect

あるユーザと別のユーザの共通リレーションがわかれば、どれだけつながり具合が似ているか算出することができます。

intersectの計算時間は、rankによる範囲の切り取り操作と二分木の枝刈り操作のため

  • K：ノードの最大ビット長
  • N：リレーション数

としたとき、

intersectn = O( K log N )

として計算できます。

201404221548_8-708x0.png

いずれも極めて高速です。

5. まとめ

ソーシャルグラフの重要性がこんなに提起されているのに、そのグラフデータ及び探索に関するデファクト・スタンダードが出ていないという現実があります。

それは、ソーシャルグラフの起源自体が比較的新しいこともありますが、データサイズが膨らみやすいことやRDBとの親和性観点から採用が難しいという側面があることが考えられます。

本レポートで提出した類似度検索システムはまだまだ途上ですが、

  • ウェーブレット行列のインデックスサイズが比較的コンパクトであること
    n log σ
  • インデックス構造が簡潔なため格納場所を選ばないこと
  • なんといっても高速な検索操作
  • 辞書さえ作ってしまえば各操作の実装はかんたん
    からユーザ類似度に基づく高速サジェストに効果を出せるのではないかと思います。

このレポートでは述べていないのですが、下記の論文で示されているように、ウェーブレット行列でグラフの類似度検索の拡張まで行えば、よりバリエーションにとんだサジェストを行うこともできます。

Weisfeiler-Lehman graph kernels

6. 謝辞 ～ごめんなさい<(_ _)>

本レポートの最大の欠陥は、「高速」を唱っていながら実証結果を提示していないことです。

残念ながら、時間的な都合で十分大量なデータを用いての実証サンプルを得ることができませんでした。

理論的な計算量を提示したのみにとどめています。

また、掲載したプログラムコードにおいては、再帰処理を多用しているため、

スタック・オーバーフローの危険性が潜在しています。

これらのプログラム改善及び時間の計測は本レポートと関係なく進める所存です。

7. 参考文献

  • now_btn.png
  • ameblo_btn.png