LSH (Locality Sensitive Hashing) を用いた類似インスタンスペアの抽出 - mixi engineer blog
GW 中の長距離移動のために体調が優れない takahi-i です. 今回は巨大なデータをマイニングする一つの技術として LSH (Localtiy Sensitive Hashing) を紹介させていただきます. LSH とは LSH は大量なデータから類似度が高いインスタンスのペアを高速に抽出してくれるアルゴリズムです. ここでインスタンスはデータ集合の一つの要素を表します. たとえば扱うデータが E-コマースサイトの購買ログであれば, インスタンスは各ユーザですし, 画像データ集合であれば, インスタンスは個々の画像データです. LSH の詳しい解説については以下のサイトがあります. Wikipedia のエントリ LSH に関する論文がまとめられているページ 本稿ではE-コマースサイトの購買履歴データを基に LSH の機能について述べてゆきます. 以下のような E-コマースサイトの
ランダウの記号 - Wikipedia
スターリングの公式はランダウの記号を用いてと書くこともできる。 ランダウの記号（ランダウのきごう、英: Landau symbol）は、主に関数の極限における漸近的な挙動を比較するときに用いられる記法である。英語圏では一般的にビッグ・オー（Big O）と呼ばれる。 ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O （数字の0ではない）を用いることから（バッハマン-ランダウの）O-記法 (Bachmann-Landau O-notation[1])などともいう。 記号 O はドイツ語のOrdnungの頭字にちなむ[2]。 なおここでいうランダウはエトムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。 ランダウの記号は数学や計算機科学をはじめとした様々な分野で用い
プログラミングコンテストでのデータ構造 2 - iwiwiの日記
情報オリンピックの春合宿で「プログラミングコンテストでのデータ構造 2」というタイトルで講義をさせてもらいました．スライドは以下になります． プログラミングコンテストでのデータ構造 2 〜平衡二分探索木編〜 View more presentations from Takuya Akiba プログラミングコンテストでのデータ構造 2 〜動的木編〜 View more presentations from Takuya Akiba 平衡二分探索木の話と動的木の話をしました．アルゴリズム的な説明だけでなく，実際にコードにする際に楽に実装するためのポイントにも重きをおいています．実装に関する話は，アルゴリズム系の講義資料等にはあまり書かれることが無いため，珍しい資料になっているかと思います．（そもそもとして動的木の話は珍しいですが…） 「プログラミングコンテストでの」というタイトルになっています
An Implementation of Double-Array Trie
Contents What is Trie? What Does It Take to Implement a Trie? Tripple-Array Trie Double-Array Trie Suffix Compression Key Insertion Key Deletion Double-Array Pool Allocation An Implementation Download Other Implementations References What is Trie? Trie is a kind of digital search tree. (See [Knuth1972] for the detail of digital search tree.) [Fredkin1960] introduced the trie terminology, which is
情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、この本を教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから
Algorithm - 連想配列の実装としてのハッシュはオワコン? : 404 Blog Not Found
2012年01月17日11:45 カテゴリアルゴリズム百選Tips Algorithm - 連想配列の実装としてのハッシュはオワコン? 珠玉のプログラミング Jon Bentley / 小林健一郎訳 つまり「終わったコンテナ」。 以前からうすぼんやりと考えて来た危惧が、すこしはっきりと見えてきた。 徳丸浩の日記: Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 もうそろそろハッシュ(テーブル)以外の手段の連想配列の実装手段を本格的に模索するべきではないか、と。 そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列(Associative array)がコレクション(Collection)、すなわち数多のデータ構造をまとめるデータ構造としての覇者となったのはもはや疑いようがない事実でしょう「配列で実装されるデータ構造ではなくて、配列を実装するデータ構
第二版が出ます！プログラミングコンテストチャレンジブック - iwiwiの日記
一昨年 9 月に初版が出て以来「蟻本」の愛称で皆様にご好評頂いていた僕と岩田 (id:wata_orz) と北川の「プログラミングコンテストチャレンジブック」ですが，お陰様で，このたび第二版が出版されます！第二版の発売日は 1/27 の予定です．よろしくお願いします． （初版の紹介記事はこちら） 改訂による追加部分は，以下になります． 4 つの新しいトピック：計算幾何，枝刈り探索，分割統治法，文字列アルゴリズム 練習問題コーナー 発展内容コーナー ページは 50 ページ増となっています． 練習問題コーナー 練習問題コーナーでは，本書で取り上げた各トピックに関連したオンラインジャッジ上の問題を紹介しています．例題を理解するだけでなく，実際に練習問題を自分で解くことで，一層の定着や応用力の増強を図ることができます． 発展内容コーナー 発展内容コーナーでは，難易度や本の性質の都合等で本書で紹介し
Don Knuth's Home Page
Donald E. Knuth (), Professor Emeritus of The Art of Computer Programming at Stanford University, welcomes you to his home page. Frequently Asked Questions Infrequently Asked Questions Recent News Computer Musings Known Errors in My Books Help Wanted Diamond Signs Preprints of Recent Papers Curriculum Vitæ Pipe Organ Fantasia Apocalyptica Downloadable Graphics Downloadable Programs and Data Expect
Sort-merge join - Wikipedia
The sort-merge join (also known as merge join) is a join algorithm and is used in the implementation of a relational database management system. The basic problem of a join algorithm is to find, for each distinct value of the join attribute, the set of tuples in each relation which display that value. The key idea of the sort-merge algorithm is to first sort the relations by the join attribute, so
Least Recently Used - Wikipedia
Least Recently Used (LRU) とは、データが最後に使われたのはいつであるかを記録し、最近最も使われなかったデータをキャッシュから削除するキャッシュアルゴリズムのこと。CPUのキャッシュメモリや仮想メモリが扱うデータのリソースへの割り当てなどにも使われる。対義語はMost Recently Used (MRU)。 和訳すると「最近最も使われなかったもの」つまり「使われてから最も長い時間が経ったもの」「参照される頻度が最も低いもの」である。 小容量で高速な記憶装置（例えば、CPUのキャッシュメモリ）がいっぱいになったとき、その中にあるデータのうち、未使用の時間が最も長いデータを大容量で低速な記憶装置（例えば、主記憶装置）に保存する、というのが基本のアルゴリズムである。 なお、上の括弧内の例はCPUのキャッシュメモリの場合である。仮想メモリの場合は、小容量で高速な記憶装置を
.:: General Purpose Hash Function Algorithms - By Arash Partow ::.
Introduction Hash functions are by definition and implementation generally regarded as Pseudo Random Number Generators (PRNG). From this generalization it can be assumed that the performance of hash functions and comparisons between other hash functions can be determined by modelling the functions as PRNGs. Analysis techniques such a Poisson distribution can be used to analyse the collision rates
Dictionary of Algorithms and Data Structures
absolute performance guarantee abstract data type (a,b)-tree accepting state Ackermann's function active data structure acyclic directed graph: see directed acyclic graph acyclic graph adaptive heap sort adaptive Huffman coding adaptive k-d tree adaptive sort address-calculation sort adjacency-list representation adjacency-matrix representation adjacent admissible vertex ADT: see abstract data typ
Rosetta Code
Rosetta Code is a programming chrestomathy site. The idea is to present solutions to the same task in as many different languages as possible, to demonstrate how languages are similar and different, and to aid a person with a grounding in one approach to a problem in learning another. Rosetta Code currently has 1,329 tasks, 393 draft tasks, and is aware of 973 languages, though we do not (and cann
Fractal tree - Rosetta Code
Fractal tree You are encouraged to solve this task according to the task description, using any language you may know. Generate and draw a fractal tree. Draw the trunk At the end of the trunk, split by some angle and draw two branches Repeat at the end of each branch until a sufficient level of branching is reached Related tasks Pythagoras Tree 11l -V Width = 1000 Height = 1000 TrunkLength = 400 S
データマイニングで使われるトップ10アルゴリズム - データサイエンティスト上がりのDX参謀・起業家
2006年のデータマイニング学会、IEEE ICDMで選ばれた「データマイニングで使われるトップ10アルゴリズム」に沿って機械学習の手法を紹介します（この論文は@doryokujin君のポストで知りました、ありがとうございます！）。 必ずしも論文の内容には沿っておらず個人的な私見も入っていますので、詳細は原論文をご確認下さい。また、データマイニングの全体観をサーベイしたスライド資料がありますので、こちらも併せてご覧下さい。 データマイニングの基礎 View more presentations from Issei Kurahashi 1. C4.5 C4.5はCLSやID3といったアルゴリズムを改良してできたもので、決定木を使って分類器を作ります。決定木といえばCARTが良く使われますが、CARTとの違いは以下のとおりです。 CARTは2分岐しかできないがC4.5は3分岐以上もできる C
遺伝的アルゴリズムでブランコの漕ぎ方を学習させた。Long版/物理エンジン【むにむに】
前回は私が作成したアルゴリズムで漕いだ。 今回はコンピュータにアルゴリズムを学習させる。 遺伝的アルゴリズムを用いた。 コンピュータは私のアルゴリズムを超えられるか？ 評価：踏み台の初期位置からの最大移動距離で決めている。 選択：評価の高いほうから4人を選ぶ。 交叉：4人(A,B,C,D)からランダムに2人選ぶ(AとAなど同じ人を選ぶ場合もある)。一方から遺伝子の前半、他方から遺伝子の後半をもらう。 突然変異：ランダムな場所を選び、0と1を逆転させる。何箇所行うかはランダムに決める(0個から3個の間)。 ニコニコ動画版 https://www.nicovideo.jp/watch/sm16212939 #むにむに #munimuni #物理エンジン #遺伝的アルゴリズム
蟻コロニー最適化 - Wikipedia
蟻コロニー最適化の概念図 蟻コロニー最適化（ありコロニーさいてきか、Ant Colony Optimization、ACO）とは、Marco Dorigo が 1992年の博士論文で提案したアルゴリズムであり、グラフを使ってよい経路を探すことで単純化できるような計算問題の確率的解法である。これはアリがコロニー（＝群れ）から食物までの経路を見つける際の挙動からヒントを得たものである。 実世界では、アリは始めランダムにうろつき、食物を見つけるとフェロモンの跡を付けながらコロニーへ戻る。他のアリがその経路を見つけると、アリはランダムな彷徨を止めてその跡を辿り始め、食物を見つけると経路を補強しながら戻る。 しかし、時間とともにフェロモンの痕跡は蒸発しはじめ、その吸引力がなくなっていく。その経路が長いほどフェロモンは蒸発しやすい。それに対して、経路が短ければ行進にも時間がかからず、フェロモンが蒸発す
単体マシン（x86/x64）における最速sort algorithmは何か？ - maropuのメモ墓場
今日はsortの日なのでしょうか・・・ twitterのタイムラインを眺めていると，tim-sortというalgorithmが話題のようです． quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort http://d.hatena.ne.jp/gfx/20111019/1318981818 単体マシン（x86/x64）における高速なsort algorithmの研究はIntelが近年行っていて，有名な実装だとbufferingを利用したradix-sort実装と，SIMDを利用したmerge-sort(bitonic-sort）実装があります． 1. radix-sort: Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort, SIGMOD'10, ht
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Fractals in 10 minutes No. 6: Turtle Snowflake
ConsistentHashing - コンシステント・ハッシュ法