2013年02月14日04:30 カテゴリアルゴリズム百選Math algorithm - PATRICIA に一番似合う姓は Crit-Bit かも 高速文字列解析の世界 岡野原大輔 「高速文字列解析の世界」を読んだら、熱がぶりかえしてきたので。 ハッシュテーブルや平衡二分木に代わる連想配列を実装するにはどうしたらよいのかという、知恵熱が。 すべてのハッシュ衝突を、生まれる前に消し去りたい。すべての宇宙、過去と未来の全てのハッシュ衝突を、この手でなくてもいいから。 ハッシュテーブル - Wikipedia ハッシュテーブル (hash table) は、キーと値の組(エントリと呼ぶ)を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。ハッシュ表ともいう。ハッシュテーブルは連想配列や集合の最も効率的な実装のうち1つである ハッシュテーブルはあまりに愛用されてきたため、連想配
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
高速に類似度計算をしたい場合、典型的に使われるのは Locality sensitive hashing (LSH)という技術であり、元々距離が近いインスタンス同士はハッシュ値が近くなるようにハッシュ関数を作ることで高速に類似度を計算したりできるというお話なのだが、最近 Semantic hashing や Spectral hashing、また Kernelized LSH という手法が登場して盛り上がりつつあるところ、同じグループの人がもっといいのを出しました、ということらしい。ちなみに情報推薦とか画像検索とか大規模クラスタリングとか、いろいろな分野で高速な類似度計算の応用例がある。 そういうわけで、今日は manab-ki くんが Brian Kulis and Trevor Darrell. "Learning to Hash with Binary Reconstructive
【論文】M. Datar, N. Immorlica, P. Indyk, and V.S. Mirrokni, Locality-Sensitive Hashing Scheme Based on p-Stable Distributions, Proceedings of the twentieth annual symposium on Computational geometry, 2004. Overview Locality Sensitive Hashing(以下LSH,局所性鋭敏型ハッシュ)は高次元データを次元圧縮するための手法で,圧縮したデータによるハッシュテーブルを作成して,効率的に近似的最近傍探索を行うための手法です.基本的なアイディアとしては高次元空間内での距離が近い2つのベクトルが,ハッシュテーブルにおいて高確率で同じバケットに入るように確率的な処理を行うと
WEB+DB press vol.49にレコメンド特集の記事をtkngさんと書きました。 内容は最初は、協調フィルタリングやコンテンツマッチの簡単な話から、特徴量をどのように表すか、大規模データをどのように処理するかにいき、特異値分解などの低ランク行列分解によるレコメンドやRestricted Boltzmann Machineといった最近のnetflix prizeの上位の手法など、かなり突っ込んだ議論もしてます。 個人的には三章でLocality Sensitive Hash(LSH)について扱っているあたりがお勧めです。 レコメンドの内部の問題を極言すると、データというのは疎な高次元の数値ベクトル(数百万次元とか)で表され、クエリでベクトルが与えられた時、これと似たようなベクトルを探してこいという問題になります。”似たような”を数学的にいえば、クエリのベクトルとの内積(各ベクトルは長
by Erich Owens Optimizing the memory footprint of a classifier used here at Newsle set us down a rabbit hole of rewriting a basic Scipy function with Cython, something that only became a problem when our high-dimensional text spaces grew to a cartoonish size, thanks to the hashing trick. Here I motivate the use of the hashing trick, how we use sparse matrix-vector multiplication for text classific
去年の終わりから、バイナリハッシングを使った近似近傍検索をいろいろ調べていたのですが、ぼちぼち一段落したので、ひと通りまとめておきます。 バイナリハッシングとは。 個の 次元の点からなるデータセット で、元空間での近傍点を、類似したバイナリコードに関連づける技術。 要するに、実数ベクトルの検索をマトモにやるには、最近のデータは膨大すぎるのでお手上げ。なので、元空間での距離をなるべく保ったまま、バイナリコードに落としましょう。 そうすると、バイナリ一致か、1ビット違うか、2ビット違うか...と、捜索していくにしても、元空間のデータでやるより高速で、しかもストレージ容量を削減できるというわけです。 その ビットのバイナリコード を作るために、 個のハッシュ関数が使われる。 ハッシュ関数は と定義される。ここで、 はデータセット。 は射影ベクトル。 は閾値。 線形写像ベースのハッシングはシンプル
In game development, we use associative maps for many things. Dynamic loading, object reflection, rendering, shader management. A lot of them fit the following usage pattern: The keys and values have simple integer or pointer types. The keys are effectively random. The basic operation is lookup-or-insert: Look for an existing item first, and add one if not found. Usually, the item is found. Delete
データ構造とアルゴリズム再入門 はじめに ・並{行|列} & {Lock|Wait}Free ・ABA & ABA' ・volatile & メモリバリア ・プリミティブ ・CAS ・MCAS ・STM ・メモリ管理:free & GC ・Toots List & Skiplist [単方向List] ・リスト ・細粒度リスト ・Lazyリスト ・Lock-Freeリスト ・Lock-Freeリスト2 [SkipList] ・スキップリスト ・Lazyスキップリスト ・Lock-freeスキップリスト [双方向List] Queue & PriorityQueue [UnBounded Queue] ・Queue ・CAS based Lock-Free Queue ・LL/SC based Lock-Free Queue [Unbounded Priority Queue] ・Heap
12月21日、ハッシュアルゴリズム「BLAKE2」とそのCおよびC#実装が公開された。BLAKE2はMD5やSHAといったハッシュアルゴリズムの代替として利用できるもので、セキュリティに優れ高速に動作するのが特徴という。 BLAKE2は、与えられた入力に対し指定されたビット長のハッシュ値を生成するためのアルゴリズム。既存のハッシュアルゴリズムであるMD5よりもセキュリティに優れ、かつSHAよりも高速に処理を実行できるのが特徴という。 同様のハッシュアルゴリズムとしてSHA-2やその後継となるSHA-3(Keccak)などがあるが、BLAKE2はSHA-3アルゴリズムの候補の1つであったBLAKEを改良したものとなっている。BLAKE2はSHA-3やBLAKEと同等のセキュリティを備えつつ、64ビット環境においてMD5と同等の速度で動作し、SHA-2やSHA-3と比べて33%少ないメモリで動
It's a few monthes since the initial release of xxHash. The algorithm has almost fullfilled its initial objective, which is to provide a Hash function for error detection fast enough to use within LZ4 streaming interface. Although the "fundamentals" were fine, a few details were still rough on the edges. The most important "missing feature" was the ability to provide input data in several consecut
Highly Scalable BlogArticles on Big Data, NoSQL, and Highly Scalable Software Engineering Some time ago our team had been requested to develop several Java components for structured information retrieval. After the initial research, we concluded that standard approaches like inverted indexes are not well applicable to our problem because of specific business requirements. As a result we faced a ne
Which hashing algorithm is best for uniqueness and speed? Example (good) uses include hash dictionaries. I know there are things like SHA-256 and such, but these algorithms are designed to be secure, which usually means they are slower than algorithms that are less unique. I want a hash algorithm designed to be fast, yet remain fairly unique to avoid collisions.
Posted by usa on 9 Nov 2012 ruby 1.9 系列で使用しているハッシュ関数について、ハッシュ飽和攻撃によってサービスを停止させることができる脆弱性が報告されました。 この脆弱性は 1.8.7 に対して公表された CVE-2011-4815 とは異なるものです。 全ての ruby 1.9 ユーザーは、この問題に対するセキュリティフィックスが含まれた ruby-1.9.3 patchlevel 327 に更新することが推奨されます。 影響 綿密に構築された文字列の並びをサーバーに対して送信することにより、そのサーバーがこの文字列の並びを文字列をキーとした Hash オブジェクトの生成に利用する場合、サービス停止攻撃が成立します。 例えば、信頼できない送信元から送られた JSON データを解釈する Web アプリケーションなどがこの脆弱性の影響を受けます。 詳細 こ
Cryptographer, co-founder & chief security officer @ Taurus. Books Serious Cryptography (No Starch Press, 2017) Translations' covers 🚧 Second edition: to appear in 2024 (No Starch Press) 🚧 French translation: to appear in 2024 (Dunod) Petit Pingouin (self-published, 2021) Crypto Dictionary (No Starch Press, 2020) The Hash Function BLAKE (Springer, 2014) Crypto projects Hash functions BLAKE, BLAK
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く