今更ながら,GoogleのMaglev論文で提案されているMaglev Hashingを手元で実装してみた. Maglev: A Fast and Reliable Software Network Load Balancer Maglev Hashingとは 所謂Consitent Hashの一種.Maglevロードバランサにおけるリアルサーバ選択に使用されている. 上記論文のSection 3.4で詳細が説明されている.NSDI'16での発表スライドも併せて眺めると分かりやすい. Maglev: A Fast and Reliable Software Network Load Balancer | USENIX Slide: https://www.usenix.org/sites/default/files/conference/protected-files/nsdi16_sli
前回に引き続き転置インデックスの圧縮を実装してみる。今回紹介するのは[2]で提案されているSimple-9というアルゴリズムである。 Simple-9は32bitのwordにできるだけ数字を詰めていくという圧縮アルゴリズムである。例えば2bitの数が16個ならんでいれば32bitで表現できる。しかし、実際は大きい数字も出現するため数字の長さの情報も格納する必要がある。Simple-9では4bitを用いて残りの28bitがどう詰められているかを表す。 28bitの表し方としては 上位bit 符号の個数 符号のビット長 0000 28 1 0001 14 2 0010 9 3 0011 7 4 0100 5 5 0101 4 7 0110 3 9 0111 2 14 1000 1 28 の9通りがあり、これがSimple-9の名前の由来となっている。 例えば ( 3 , 5 , 0 , 0 ,
Random and FIFO are both strictly worse than either LRU or 2-random. LRU and 2-random are pretty close, with LRU edging out 2-random for the smaller caches and 2-random edging out LRU for the larger caches. To see if anything odd is going on in any individual benchmark, we can look at the raw results on each sub-benchmark. The L1, L2, and L3 miss rates are all plotted in the same column for each b
Designing algorithms for balanced allocation of clients to servers in dynamic settings is a challenging problem for a variety of reasons. Both servers and clients may be added and/or removed from the system periodically, and the main objectives of allocation algorithms are: the uniformity of the allocation, and the number of moves after adding or removing a server or a client. The most popular sol
あなたは円周率を何桁言えますか。3.14159…という、あの数字です。 円周率の小数部分は無限に続き、循環することもありません。 古来より、数学者は円周率の値を様々な幾何学的な近似や公式を用いて計算してきました。 その桁数は計算機の発明により飛躍的に伸び、収束の速い公式の発見や効率の良いアルゴリズムの発明などによって加速してきました *1。 5年前、私がまだ学生だった頃、円周率1億桁の計算に挑んだことがありました。 私にとって高精度計算の初めての挑戦で、様々な試行錯誤で苦労したのをよく覚えています。 itchyny.hatenablog.com 2017年現在、円周率計算の世界記録は22兆桁です。 円周率計算の歴史をご覧いただくとよく分かると思いますが、近年の円周率計算の世界記録からは次のような特徴が読み取れます。 2002年に1兆を超え、最新の記録 (2016年) は22兆桁 (10進数
This article was ported from my old Wordpress blog here, If you see any issues with the rendering or layout, please send me an email. papadHard to believeSanjeev Arora and his coauthors consider it “a basic tool [that should be] taught to all algorithms students together with divide-and-conquer, dynamic programming, and random sampling.” Christos Papadimitriou calls it “so hard to believe that it
Random sample consensus (RANSAC) is an iterative method to estimate parameters of a mathematical model from a set of observed data that contains outliers, when outliers are to be accorded no influence on the values of the estimates. Therefore, it also can be interpreted as an outlier detection method.[1] It is a non-deterministic algorithm in the sense that it produces a reasonable result only wit
So in this case there were nine elements in total. The number 1 showed up twice, the number 2 showed up once, the number 4 showed up five times and the number 5 showed up once. So maybe the input sequence was { 4, 4, 2, 4, 1, 1, 4, 5, 4 }. The final loop now goes over the initial array again and uses the key to look up into the prefix sum array. And lo and behold, that array tells us the final pos
The information presented in this paper defines LogLog-Beta. LogLog-Beta is a new algorithm for estimating cardinalities based on LogLog counting. The new algorithm uses only one formula and needs no additional bias corrections for the entire range of cardinalities, therefore, it is more efficient and simpler to implement. Our simulations show that the accuracy provided by the new algorithm is as
FALCONN (FAst Lookups of Cosine and Other Nearest Neighbors) is a C++ library with a Python wrapper for similarity search over high-dimensional data. It supports cosine similarity and the Euclidean distance. The main ingredient of FALCONN is a Locality-Sensitive Hashing family for cosine similarity that is: Optimal in theory,Fast in practice. See the github repo for the source code and documentati
Illustration by Champa LoA few weeks ago, Uber posted an article detailing how they built their “highest query per second service using Go”. The article is fairly short and is required reading to understand the motivation for this post. I have been doing some geospatial work in Golang lately and I was hoping that Uber would present some insightful approaches to working with geo data in Go. What I
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く