乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩− - iwiwiの日記
本日，PFI セミナーにて「乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩−」というタイトルで話をさせてもらいました．スライドは以下になります． Ustream の録画もあります． http://www.ustream.tv/recorded/48151077 内容としては，以下の操作を効率的に行うための集合に関するデータ構造 (Sketch) の最近の進歩を紹介しました． 集合の類似度の推定 (Jaccard 係数) 集合異なり数の推定 (distinct counting) どちらも重要かつ基礎的な操作で，b-bit MinHash や HyperLogLog など，既に実用的な手法が提案されており，実際にも使われています．しかし，2014 年になって，Odd Sketch や HIP Estimator という，これらをさらに改善する手法が立て続
Efficient Parallel Set-Similarity Joins Using MapReduce
Department of Computer Science University of California, Irvine Abstract In this paper we study how to efficiently perform set-similarity joins in parallel using the popular MapReduce framework. We propose a 3-stage approach for end-to-end set-similarity joins. We take as input a set of records and output a set of joined records based on a set-similarity condition. We efficiently partition the dat
VFML: VFML
Welcome to the VFML (Very Fast Machine Learning) toolkit for mining high-speed data streams and very large data sets. VFML is made up of three main components. The first is a collection of tools and APIs that help a user develop new learning algorithms. The second component is a collection of implementations of important learning algorithms. The third component is a collection of scalable learning
大規模フィンガープリント類似検索のための簡潔マルチビット木の実装を公開しました - Yasuo Tabeiの日記
以前のブログで紹介した簡潔マルチビット木のc++による実装 (Succinct Multibit Tree (SMBT)) を公開致しました。ソフトウェアーはgoogle codeからダウンロードすることができます。 http://code.google.com/p/smbt/ SMBTは去年のWABIで発表した内容にもとづいています。 簡潔マルチビット木に関するブログ記事 : http://d.hatena.ne.jp/tb_yasu/20120808/1344415559 論文 : Yasuo Tabei: Succinct Multibit Tree: Compact Representation of Multibit Trees by Using Succinct Data Structures in Chemical Fingerprint Searches, Workshop
Googleはスピード狂である。 : Owlet - アコースティックデュオ オゥレット
server: asm_old = disassemble(original) asm_new = disassemble(update) asm_new_adjusted = adjust(asm_new, asm_old) asm_diff = bsdiff(asm_old, asm_new_adjusted) transmit asm_diff client: receive asm_diff asm_old = disassemble(original) asm_new_adjusted = bspatch(asm_old, asm_diff) update = assemble(asm_new_adjusted) ※ここでoriginalとは旧バージョンのことと思われる。 まず、サーバ側では旧版、新版ともに逆アセンブルを行い、実行ファイルにコンパイルされる直前のデータに起こし
Family of Graph and Hypergraph Partitioning Software | Karypis Lab
METIS stable version: 5.1.0, 3/30/2013; MT-METIS version: 0.7.3, 6/4/2020 METIS is a set of serial programs for partitioning graphs, partitioning finite element meshes, and producing fill reducing orderings for sparse matrices. The algorithms implemented in METIS are based on the multilevel recursive-bisection, multilevel k-way, and multi-constraint partitioning schemes developed in our lab. METIS
Biff (Bloom Filter) Codes : Fast Error Correction for Large Data Sets
Large data sets are increasingly common in cloud and virtualized environments. For example, transfers of multiple gigabytes are commonplace, as are replicated blocks of such sizes. There is a need for fast error-correction or data reconciliation in such settings even when the expected number of errors is small. Motivated by such cloud reconciliation problems, we consider error-correction schemes d
情報知識ネットワーク特論 -講義資料- | 北海道大学オープンコースウェア (Hokkaido University OpenCourseWare, HU-OCW, 北大OCW)
情報検索とパターン照合（７回）（喜田が担当） ガイダンス、および、準備 講義スライド Prefix型アルゴリズム（naïve、KMP、AC、Shift-And/Or） 講義スライド Suffix型アルゴリズム（BM、Galil、Horspool、Sundayほか） 講義スライド 近似文字列照合 講義スライド 正規表現の照合 講義スライド 圧縮テキスト上のパターン照合 講義スライド 文字列照合技術の今後 講義スライド
Paolo Ferragina --- Home Page
Full Professor Department of Computer Science University of Pisa Largo Bruno Pontecorvo 3, I-56127 Pisa, Italy. email: paolo.ferragina(AT)unipi.it skype: paolo.ferragina linkedin: my profile I'm leading the Advanced Algorithms and Application Lab (Acube), located at the Department of Computer Science, University of Pisa. We design and implement algorithms for compressing, indexing, searching and m
BlinkDB: Queries with Bounded Errors and Bounded Response Times on Very Large Data
Queries with Bounded Errors and Bounded Response Times on Very Large Data BlinkDB is a massively parallel, approximate query engine for running interactive SQL queries on large volumes of data. It allows users to trade-off query accuracy for response time, enabling interactive queries over massive data by running queries on data samples and presenting results annotated with meaningful error bars.
Tumblr
「JPEG Tilt」というページを公開しました。MotionJPEG Builder を作った時に、JPEG のヘッダを読み込む処理を作ったので（結局これは使わなかったんですが）圧縮データの読み込み部分も作ってみようか、という気になって作ったのがこれです。JPEG ファイルで画像が圧縮される様子を視覚的に表現する…… という目標だったのですが、どうでしょうか。まあ内容が内容なので説明無しではさすがに意味が分からないと思います。 ということで、JPEG Tilt の見方を以下で簡単に説明します。 図1は、JPEG Tilt の画面です。画像が iTunes の CoverFlow のように並んでいますが、これの左側は画像の低周波成分のみを抜き出した物で、右に行くとより高周波の成分も含めるように並んでいます（低周波、高周波という言葉の意味はこの先で出てきます） 画像の上にマウスカーソルを乗せ
Introduction to Lock-Free Algorithms | AppNexus Tech Blog
APPNEXUS MAIN APPNEXUS CAREERS AppNexus is the leader in real-time advertising technology, serving the most sophisticated clients in the ecosystem. Founded in 2007, we are consistently ranked as a top technology company in New York. Slides are at http://concurrencykit.org/presentations/lockfree_introduction/. Recently I’ve been interested in formalizing a course structure for the practical applica
Divide-and-conquer algorithm - Wikipedia
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. The divide-and-conquer technique is the basis of ef
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Count-Min Sketch
Reddit - Dive into anything
403 Forbidden
Data Compression Techniques | Department of Computer Science [pre 2018 site]
Algolib: The Algorithms Project's Library and Other Packages of the Algorithms Project
Google Code Archive - Long-term storage for Google Code Project Hosting.
ESMAJ