Skip to content

Instantly share code, notes, and snippets.

View yaojingguo's full-sized avatar
🎯
Focusing

Jingguo Yao yaojingguo

🎯
Focusing
View GitHub Profile
@yaojingguo
yaojingguo / math.md
Last active June 30, 2018 07:37
math

Cache-Oblivious Streaming B-trees

SHUTTLE TREE

Shuttle-tree structure

Shuttle tree algorithm complexity:

  • Search(optimal): $O(\log_{B+1}N)$
  • Range query of $L$ successive elements (Optimal): $\log_{B+1}N + L/B$
  • Insertion: $\frac{\log_{B+1}N}{B^{\Theta(\frac{1}{(\log\log B)^2})}+\frac{(\log^2 N)}{B}}$

A shuttle tree is a strongly weight-balanced search tree (SWBST). Each non-leaf node points to a a linked list of buffers. These buffers are recursively defined to be shuttle trees.

\documentclass{article}
\usepackage{amsmath, amssymb, amsthm}
\begin{document}
The invariant is that $min\_sum$ is the min-abs-sum of pairs whose one element
is among $a[0]...a[l-1]$ or $a[r+1]...a[n-1]$.
\textbf{Initialization}: Before the first iteration, $l = 0$ and $r = n- 1$.
$('form#searchForm').submit(function() {
$(':input', this).each(function() {
var val = $(this).val();
if (typeof val === 'string') {
$(this).val(val.trim());
}
this.disabled = !val;
});
});