SSTable
SSTable is an abbreviation for Sorted String Table. It is the fundamental storage building block in few of the modern Log Structured Merge Tree(LSM) based distributed database systems and key-value stores. It is used in Cassandra, BigTable and other systems. SSTable stands for Sorted Strings Table which stores a set of immutable row fragments or partitions in sorted order based on row/partition ke
くまメモ
データベースを使って何かする際に、ダミーデータが超大量に欲しくなることがあるのでembulkのinput-pluginを作ってみた。 githubのリンク 何もない環境からなら $ wget https://bintray.com/artifact/download/embulk/maven/embulk-0.2.1.jar -O embulk.jar でembulk本体のが降ってくるのでそれを使って $ java -jar embulk.jar gem install embulk-plugin-input-random とすればプラグインが降ってくる。 exec: {} in: type: random rows: 100 schema: id: primary_key name: string score: integer out: type: stdout こんな感じのconfig
大規模データ処理のための簡潔データ構造 | CiNii Research
データ列に対して検索効率などを効率化するため，索引を付加することがある．演算を効率化するために，データに対して特定の情報を付加したものを，ここではデータ構造と呼ぶこととする．本稿ではこのようなデータ構造のうち，もとのデータの長さnに対してo(n)程度の付加情報のみを与える，簡潔データ構造と呼ばれる分野について解説する．特に，最も基本的かつ応用範囲の広いビットベクトルに関する簡潔データ構造に焦点を当てる．ビットベクトルBに対して，先頭からi番目までのビット中の1の数を与えるrank1(B i)と，i番目の1の位置を与える select1(B i)という演算は，基本的かつ重要な演算である．これらの演算が定数時間で可能な簡潔データ構造について，具体的なデータ構造とアルゴリズムを紹介し，次に付加するデータサイズの下界についての結果を示し，最後に今後の展望について述べる．
ブルームフィルタ - Wikipedia
この項目では、確率的データ構造について説明しています。画像にぼかし効果を付加する画像フィルタについては「川瀬のブルームフィルター」をご覧ください。 ブルームフィルタ（英語: Bloom filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性（false positive）の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性（false negative）はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない（ただし、拡張をした counting filter であれば削除もできる）。集合に要素を追加していくにつれて偽陽性の
Skip graphs
Skip Graphs James Aspnes, Gauri Shah Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2003, pp. 384-393. Submitted to Journal of Algorithms. Abstract Skip graphs are a novel distributed data structure, based on skip lists, that provide the full functionality of a balanced tree in a distributed system where elements are stored in separate nodes that may fail at any time.
Binary Indexed Tree (Fenwick Tree) - naoyaのはてなダイアリー
圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。 累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。 Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更
MIT OpenCourseWare OCW Home
Unlocking knowledge, Empowering Minds. Free lecture notes, exams, and videos from MIT. No registration required. Learn More about the OCW mission Free and open access to knowledge needs your support. When you donate to MIT OpenCourseWare, you open up possibilities for learners everywhere. Make your gift before our June 30 fundraising deadline. Chalk Radio: a podcast about inspired teaching at MIT
Grid File
A grid structure for queries on two search keys is a 2-dimensional grid, or array, indexed by values for the search keys. Figure 11.10 (textbook 11.31) shows part of a grid structure for the deposit file. Figure 11.10: Grid structure for deposit file. A particular entry in the array contains pointers to all records with the specified search key values. No special computations need to be done Onl
Xoilac tv - Xem Bóng Đá Trực Tiếp - Trực Tuyến Xôi Lạc TV
Xoilac tv - Xem Bóng Đá Trực Tiếp - Trực Tuyến Xôi Lạc TV Link xem bóng đá Xoilac cập nhật ngày 22-08-2024 Ngày nay, nhu cầu xem bóng đá trực tuyến trên mọi nền tảng ngày càng gia tăng bởi nó mang lại rất nhiều lợi ích. Nhận thức được tiềm năng đó, kênh truc tiep bong da xoilac tv đã được tạo dựng, cung cấp dịch vụ xem bong da online miễn phí, chất lượng cao dành cho người hâm mộ. Ngoài ra,
ダブル配列における動的更新の効率化アルゴリズム | CiNii Research
タイトル別名 ダブル ハイレツ ニ オケル ドウテキ コウシン ノ コウリツカ アルゴリズム Efficient Dynamic Update Algorithms for a Double-array Structure 自然言語処理 トライ構造はキーの表記文字単位に構成された木構造を用いて検索するキー検索技法の1つであり，自然言語辞書を中心として広く用いられている．このトライ構造を実現するデータ構造として高速性とコンパクト性を満足するダブル配列法があるが，この手法は，キーの更新が頻繁に生じない検索法として確立しているため，動的検索法に比べて追加時間は高速であるとはいえず，また削除で生じる不要なノードや未使用要素により記憶量に無駄が生じていた．本論文ではこれらの問題を解決し，ダブル配列を動的検索法として確立するため，未使用要素を連結することで追加処理を高速化する手法，削除時に生じる不要ノ
これからのDouble Arrayは動的更新に対応するべき - 射撃しつつ前転 改
Double Arrayのコードなんて1年以上いじってないくせになにを言ってるんだこの口はと言う感じですが、Double Arrayを作るのであれば、動的更新に対応させるべきであると、そう思うわけです。 Double Arrayのメリットは Trieである 速い (Ternary Search Treeとかと比べると)サイズも小さい という感じだった訳ですが、速度はともかく、サイズではTxが使っているようなLOUDSやLOUDS++などの圧縮しちゃう方式に勝てないので、静的な辞書としては、速度が超重要なところ以外ではLOUDSやLOUDS++を使った辞書を使うのがいいのかなと思う訳です。辞書引き以外の部分がボトルネックであることも多いだろうしね。 と言うわけで、簡潔データ構造に比較してDouble Arrayでなにか便利な事ができないかなというと、圧縮をかける方式ではやはり、動的な更新が難
Computer Laboratory – Systems Research Group – NetOS: Practical lock-free data structures
Introduction Through careful design and implementation it's possible to build data structures that are safe for concurrent use without needing to manage locks or block threads. These non-blocking data structures can increase performance by allowing extra concurrency and can improve robustness by avoiding some of the problems caused by priority inversion in local settings, or machine and link failu
DO++ : 透過的データ圧縮
可逆データ圧縮分野で、現在研究が盛んな分野の一つが、データを圧縮した状態のまま定数時間でランダムアクセスをサポートするデータ圧縮方式です（word RAMモデルでO(log n)サイズの復元が定数時間)。 これは、データをあたかも圧縮していないかのように扱えるため、透過的データ圧縮/構造と呼ばれています（英語だとまだ決まってない？)。 例えば1GBのデータを圧縮した状態で、途中300MB目から4Byteだけ復元しようというのが定数時間で実現できるわけです。これは理論的にもかなり強いことをいっていて，例えば今あるデータ構造やアルゴリズムが、O(T)時間である問題を解けるというのがあったら、それを全く同じO(T)時間のままデータ構造を圧縮し作業領域量を減らすことができます (一応データ構造に対し読み込み操作しか無い場合。書き込みもある場合はまたちょっと面倒になる） このデータを圧縮したまま扱う
http://www.t3.rim.or.jp/~matsuuch/COMP/btree.htm
という大小関係になっています。また、ページを指していないbranchは、NULL値になっています。 厳密に言うとページは、次のようなキビしい条件を満たします。ページ１つについてのキーの個数が最大2M個だとすると、 ページ当たりのキーの個数n は M ≦ n ≦ 2M を満たす。つまり、各ページは少なくとも半分埋まっていなければいけない。ただし、根（一つだけある）については 0 ≦ n ≦ 2 Mでよい。 各ページ上のキーは昇順にならべる（ key[0] ＜ key[1] ＜…＜ key[n-1] ） ポインタ branch[k] （ k ＞ 0 ）の指すページが含むすべてのキーは key[k-1] より大きい ポインタ branch[k] （ k ＜ n ）の指すページが含むすべてのキーは key[k] より小さい 木の高さはいたるところ一定。つまり、根から末端のページ（葉）に至るポインタ
物理的な格納方式
□ 計算機で使われるデータは必ず何がしかの記憶媒体上に置かれる． □ レジスタ (registers) CPU 内部に置かれた記憶装置 プログラムからのアクセスは高速 (CPU の動作クロックに合わせる必要があるため．) アーキテクチャの一部なのでサイズは固定されている ( が普通) 揮発性 (volatile): つまり電源が切れると内容が消えてなくなる □ 主記憶 (main memory, MM) CPU の外に置かれた記憶装置 プログラムからは直接読み書き可能 読み書きにかかる時間は今のところ 60ns 程度が主流 容量は可変で，現在は 数百 MB 〜 数 GB 程度が普通 揮発性 (volatile) □ 二次記憶装置 (secondary storage) CPU の外に置かれた記憶装置であるが， プログラムからは直接読み書きできないもの． 例: フロッピーディスク (FD)，
Matzにっき(2008-03-17) 「MacRuby」
<< 2008/03/ 1 1. [Ruby] Ruby 1.9.0-1 snapshot released 2. 高木浩光＠自宅の日記 - 公開鍵暗号方式の誤り解説の氾濫をそろそろどげんかせんと 3. [Ruby] Lisa Awards: Biggest Hack for a Language Runtime on Dion Almaer's Blog 2 1. [教会] 第一安息日 3 1. [言語] CS 11: Python track: python idioms 2. [Ruby] Binary search algorithm - Wikipedia, the free encyclopedia 3. [OSS] Theological Cultural Analysis of the Free Software Movement 4. 小寺信良：正直、テレビはもうダメかも
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
冬のLock-Free祭り
定兼 邦彦 (Kunihiko Sadakane) - 簡潔データ構造講義資料 - researchmap
DBH - Disk Based Hashtables
spiteful.com