GitHub - NicolasLM/bplustree: An on-disk B+tree for Python 3You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.
Atom Flight Manual
CompanyEngineeringProductSunsetting AtomWe are archiving Atom and all projects under the Atom organization for an official sunset on December 15, 2022. January 30, 2023 Update: Update to the previous version of Atom before February 2 On December 7, 2022, GitHub detected unauthorized access to a set of repositories used in the planning and development of Atom. After a thorough investigation, we hav
高次元ベクトルデータ検索技術「NGT」の性能と使い方の紹介
この結果を見て単語ベクトルが変わるとNGTの性能が変わってしまうように感じた方がいるかもしれません。しかし、実はこれらの単語ベクトルはデータの次元数や件数が違っているため、それぞれの条件をあわせてみる必要があります。興味がある方は論文を読んで見比べて欲しいと思いますが、ここで重要なことは、NGTが高い精度にも関わらず、せいぜい100ミリ秒程度で検索できるという規模感であるということです。その規模感を感じてもらうために、これらの実験結果をご紹介しました。この実験以外にも論文の中では単語ベクトルの応用としてアナロジーと呼ばれる合成ベクトルでの実験やその他の比較手法の比較、実験結果の考察などもありますが今回は割愛します。 これまで紹介した内容と同じような実験はLinux系のサーバーであれば公開しているExperimental softwareという実験プログラムを使うと簡単に試すことができます。
接尾辞木 - Wikipedia
文字列 BANANA に $ を補った接尾辞木。根から葉（四角で表示）への6つの経路が6つの接尾辞 A$, NA$, ANA$, NANA$, ANANA$, BANANA$ に対応。四角の中の数字は対応する接尾辞の開始位置を示す。接尾辞リンクは破線の矢印で示されている。 接尾辞木（せつびじき）またはサフィックス木（英: Suffix tree）は、与えられた文字列の接尾部を木構造(基数木)で表すデータ構造であり、多くの文字列操作の高速な実装に利用されている。 文字列 の接尾辞木は木構造であり、その枝には文字列が対応し、木構造の根から葉までの経路ごとにそれぞれ の接尾部の1つが対応している。従って、これは の接尾部に関する基数木である。 文字列 からそのような木構造を構築するには、 の長さに対して線形な時間と空間を要する。構築できれば、いくつかの操作が高速化される（ の部分文字列を探す、誤
LCP(Longest Common Prefix)を用いたSuffix Arrayの検索 - EchizenBlog-Zwei
Suffix Arrayは「インデックスの構築」と「キーワードの検索」からなる。それぞれ構築には文字列のsortが、検索には文字列の二分探索が必要になる。 以前にCompressed Suffix Arrayのライブラリtsubomiを実装したときにはsortについてはマルチキー・クイックソート(multikey-quicksort)というアルゴリズムを用いた。一方で二分探索については特に工夫をしていなかった。 さすがにこのまま放っておくのは気が引けたのでSuffix Array論文を読みなおしてみたらLCP(Longest Common Prefix)を用いた二分探索の方法が書いてあった。シンプルだが賢い方法だったのでメモしておく。これはすごい(というか今まで読み飛ばしてたことのほうが問題ですね。はい)。 さて。まずLCP(Longest Common Prefix)とは何かと言うとその
Roaring Bitmaps
A better compressed bitset Roaring bitmaps are compressed bitmaps. They can be hundreds of times faster. Grab one of our research papers Roaring Bitmaps on GitHub Widely used Roaring is found in Google Procella: YouTube’s SQL Engine, Apache Lucene and derivative systems such as Solr and Elasticsearch, Apache Druid, Apache Spark, Apache Hive, Apache Tez, Apache Zeppelin, Apache Doris, Apache Carbon
Fun with ZDDs: Notes from Knuth’s 14th Annual Christmas Tree Lecture
In this entry, I’ll record the important ideas Knuth presented in his 14th Annual Christmas Tree Lecture, part of his regular Computer Musings. Like all other “musings”, this one included some fascinating anecdotal bits (no pun intended) and Knuth’s good sense of humor was sprinkled throughout; but most noticeable was his infectious enthusiasm for the topics he spoke about. The preface to Volume 4
BDD, ZDD, フロンティア法, Graphillion - iwiwi 備忘録
詳しい資料へのポインタを示しつつ，自分が読んで理解した範囲の簡潔なまとめを書きます． BDD 入門 湊先生の授業が詳しく分かりやすい． http://www-alg.ist.hokudai.ac.jp/~minato/alg2013.html 概念自体 図を一個見れば一発で理解できる DAG で，各中間ノードは変数で，その変数の値に応じて次に進む子を選ぶ．終着点が答え． 構築法 順序付き既約 BDD (ROBDD) を普通作るらしい．重要な性質を持つらしい． 順序付き ＝ 変数が出現してくる順番が全順序 以下の 2 つのルールを適用し続けていれば既約になる（適用順関係なし） 冗長な接点を全て削除 等価な接点を全て共有 実際には，BDD の間の二項論理演算を繰り返して構築する BDD 同士の演算 (Family Algebra) and, or, xor, not, ... みたいな色々な
BDDs - Binary Decision Diagrams
Take a map of mainland USA, and consider the following problems: Suppose you want to visit every state capitol exactly once, traveling on highways. Which route is shortest? Which route is longest? What is the mean and standard deviation of all the routes? Weight the states by any means, for example, by reading their two-letter code as a number in base 36. Then find a set of states such that no two
四分木 - Wikipedia
領域四分木 四分木（しぶんぎ、英: Quadtree）は、各内部ノードが4個までの子ノードを持つ木構造のデータ構造である。四分木は主に、2次元空間を再帰的に4つの象限または領域に分割するのに使われる。領域は四角形または矩形の場合もあるし、任意の形状の場合もある。このデータ構造は1974年、Raphael Finkel と J.L. Bentley が四分木と名づけた。同様の分割手法はQ木 (Q-tree) とも呼ばれている。四分木に共通する特徴は以下の通りである。 空間を適応可能セルに分割する。 各セル（またはバケット）は容量の上限がある。容量が最大に達すると、バケットは分割される。 木構造ディレクトリは四分木の空間分割に従う。 種類[編集] 四分木は表現するデータの型によって分類され、領域 (area)、点 (point)、線 (line)、曲線 (curve) などがある。また、木構造
UB-tree - Wikipedia
The UB-tree as proposed by Rudolf Bayer and Volker Markl is a balanced tree for storing and efficiently retrieving multidimensional data. It is basically a B+ tree (information only in the leaves) with records stored according to Z-order, also called Morton order. Z-order is simply calculated by bitwise interlacing the keys. Insertion, deletion, and point query are done as with ordinary B+ trees.
RCFile，Parquet，ORCFile
この2ヶ月で，Cloudera/Twitter，Hortonworks からそれぞれ別の列指向ファイルフォーマットが公開されました．Parquet と ORCFile です． この記事では，まず RCFile の復習をして，その後 Parquet と ORCFile それぞれの共通点と違いをおおまかに見ていこうと思います．コードレベルの詳細な違いについては，次回以降で見ていきます． RCFile の復習 RCFile は Record Columnar File の略で，Hive から利用できるストレージフォーマットです．特に，HDFS や S3 といった分散ストレージ上でパフォーマンスがでるように設計されています． HDFS/S3 といったストレージでは，基本的にデータを計算機間で同じ負荷になるようにデータを分散配置します．このため，従来の列指向ストレージフォーマットのように適当に列毎に
クヌース氏も認めたアルゴリズム「ZDD」でスマートグリッドを実現、北大・湊教授らが開発
科学技術振興機構（JST）、北海道大学、早稲田大学は2012年2月23日、北海道大学大学院情報科学研究科の湊真一教授らのグループが、電力の配電網における送電ロスを最小化する技術を開発したと発表した。湊教授が考案した「ゼロサプレス型二分決定グラフ（ZDD）」というアルゴリズムを、配電網の最適化計算に適用した。モデル上の検証では、配電網における電力ロスを3％削減できたとしている。 湊教授が1993年に考案したZDDは、米スタンフォード大学のドナルド・クヌース名誉教授の著書「The Art of Computer Programming」において、日本人が考案したアルゴリズムとしては初めて、独立項目として解説されたことで知られている。これまでZDDは、LSI設計において、回路の構成を最適化する計算などに使われていた。そのZDDを配電網の経路最適化に用いたのが、今回の発表のポイントである。 電力の
XOR連結リスト - Wikipedia
XOR連結リスト（英: XOR linked list）は、プログラミングにおけるデータ構造の一種。ビット毎の排他的論理和 (XOR) の特徴を生かして、双方向連結リストに必要なメモリ量を削減する。なお、以下ではXOR演算を ⊕ と記述する。 通常の双方向連結リストは、リスト上の前後のノードのアドレスを各ノードに格納する。従って、アドレス格納フィールドを2つ必要とする。 ... A B C D E ... –> next –> next –> next –> <– prev <– prev <– prev <– XOR連結リストでは、同じ情報を1つのアドレスフィールドに圧縮する。このとき、"prev" と "next" のアドレスについてビット毎のXOR演算を行った値をそのフィールドに格納する。 ... A B C D E ... <–> A⊕C <-> B⊕D <-> C⊕E <-> こ
テキストエディタ実装技術
バグつぶしばかりやっていると飽きてくるので、目先を変えるために技術的な文書を作成し、ここで公開することにする（01/06/04）。 意見・質問・間違いのご指摘は 津田 までメールまたはツイートしてください。 新着順 「関数電卓」アプリにおける陽関数グラフ描画 (2016/10/09) mate法を用いた Numberlink 問題自動生成 (Jly-2016) Unity C# Script プログラミング 入門(Nov-2015) C/C++ プログラミング 入門(Nov-2014) JavaScript 入門(Nov-2014) C/C++ static 修飾子 入門(Oct-2014) マップクラス std::map 入門(Oct-2014) 双方向リストクラス std::list 入門(Oct-2014) cocos2d-x 3.1 KeyboardTest(Jun-2014) c
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Exponential Stochastic Cellular Automata for Massively Parallel Inference
https://dl.acm.org/doi/10.1145/2851141.2851147
PowerPoint Presentation
乱択データ構造の最新事情 －MinHash と HyperLogLog の最近の進歩－
Count-Min Sketch - faq on count-min sketch