https://wiki.davidl.me/api.php?action=feedcontributions&user=David&feedformat=atomDavid's Wiki - User contributions [en]2024-03-29T12:49:09ZUser contributionsMediaWiki 1.41.0https://wiki.davidl.me/index.php?title=Logitech_Keyboard_Shortcuts&diff=6967Logitech Keyboard Shortcuts2024-03-25T15:32:40Z<p>David: </p>
<hr />
<div><br />
==Multi-device keyboards==<br />
https://defkey.com/logitech-pop-keys-shortcuts#105067<br />
<br />
* Windows/Android Mode: hold {{key press | FN}} + {{key press | P}} for 3 seconds<br />
* Mac Mode: hold {{key press | FN}} + {{key press | O}} for 3 seconds<br />
* iOS Mode: hold {{key press | FN}} + {{key press | I}} for 3 seconds</div>Davidhttps://wiki.davidl.me/index.php?title=Logitech_Keyboard_Shortcuts&diff=6966Logitech Keyboard Shortcuts2024-03-25T15:29:15Z<p>David: Created page with "https://defkey.com/logitech-pop-keys-shortcuts#105067"</p>
<hr />
<div>https://defkey.com/logitech-pop-keys-shortcuts#105067</div>Davidhttps://wiki.davidl.me/index.php?title=Stable_Diffusion&diff=6959Stable Diffusion2024-03-15T15:12:14Z<p>David: /* Architecture */</p>
<hr />
<div>Notes on the different versions of Stable Diffusion from what I can find online.<br />
<br />
==Stable Diffusion 1==<br />
Stable diffusion consists of three main components<br />
* CLIP text encoder<br />
* VAE<br />
* UNet latent diffusion model<br />
<br />
The main difference between stable diffusion and other diffusion models is that the diffusion operations happens in a low-resolution latent space. For a 512x512 image, the latent may only be 64x64, a factor of 8 times smaller. This significantly reduces the compute resources necessary.<br />
<br />
===Architecture===<br />
<br />
===U-Net===<br />
See [https://nn.labml.ai/diffusion/stable_diffusion/model/unet.html U-Net for Stable Diffusion] and [https://nn.labml.ai/diffusion/stable_diffusion/model/unet_attention.html Transformer for Stable Diffusion U-Net]<br />
<br />
At a high-level Stable diffusion uses a U-Net with 4 down blocks, one mid block, and 4 up blocks. Note that the last down block and first mid block do not change the resolution.<br />
<br />
===1.x===<br />
<br />
==Stable Diffusion 2==<br />
[https://stability.ai/news/stable-diffusion-v2-release Release Blog Post]<br />
<br />
Stable Diffusion 2 replaces the CLIP model with OpenCLIP, a retraining of CLIP using the publicly available LAION-5B dataset with NSFW images removed. By default they generate both 512x512 and 768x768 images.<br />
<br />
In additional, SD2 also includes the release of the following:<br />
* Super-resolution model<br />
* Depth to image model<br />
* Inpainting model<br />
<br />
===2.1===<br />
<br />
==Stable Diffusion XL==<br />
Stable Diffusion XL is a larger model trained on 1024x1024 images.<br />
<br />
==Stable Diffusion (XL) Turbo==<br />
[https://stability.ai/news/stability-ai-sdxl-turbo Blog post] [https://arxiv.org/abs/2311.17042 ADD Paper]<br />
<br />
Released Nov 2023, [https://huggingface.co/stabilityai/sd-turbo SD-Turbo] and [https://huggingface.co/stabilityai/sdxl-turbo SDXL-Turbo] are fine-tuned versions of SD2 and SDXL trained using adversarial diffusion distillation (ADD). <br />
<br />
ADD applies fine-tuning using an adversarial loss (from GANs) and a score distillation loss (from DreamFusion) such that each iteration the model produces a complete image. This allows SD-Turbo to produce realistic images in a single iteration while preserving the ability to contine refining the images with additional diffusion iterations.<br />
<br />
==Stable Cascade==<br />
[https://stability.ai/news/introducing-stable-cascade Release blog post]<br />
Stable Cascade introduces a latent generator<br />
<br />
==Stable Diffusion 3==<br />
Stable Diffusion 3 replaces the diffusion UNet with a [https://arxiv.org/abs/2212.09748 diffusion transformer (DiT)].<br />
<br />
==See Also==<br />
* [[Wikipedia: Stable_Diffusion]]</div>Davidhttps://wiki.davidl.me/index.php?title=Activation_Functions&diff=6958Activation Functions2024-03-15T15:06:57Z<p>David: /* GeLU */</p>
<hr />
<div>List of common activation functions<br />
<br />
<br />
==Sinusoidal==<br />
===Tanh===<br />
One of the older activation functions<br />
<br />
===Sigmoid===<br />
<br />
===Cosine/Sine===<br />
See [https://proceedings.neurips.cc/paper/2020/hash/53c04118df112c13a8c34b38343b9c10-Abstract.html SIREN]<br />
<br />
==ReLU==<br />
https://pytorch.org/docs/stable/generated/torch.nn.ReLU.html<br />
<br />
ReLU is one of the most popular activation functions. It simply performs <math>ReLU(x) = max(x, 0) = (x > 0) * x</math><br />
<br />
===LeakyReLU===<br />
https://pytorch.org/docs/stable/generated/torch.nn.LeakyReLU.html<br />
<br />
<math>LeakyReLU(x) = (x > 0) * x + (x < 0) * (-0.01x)</math><br />
<br />
===SiLU===<br />
===GELU===<br />
https://pytorch.org/docs/stable/generated/torch.nn.GELU.html<br />
<br />
===GeGLU===<br />
<br />
==Resources==<br />
* [https://armandolivares.tech/2022/09/04/elu-gelu-and-silu-activation-functions/]</div>Davidhttps://wiki.davidl.me/index.php?title=Activation_Functions&diff=6957Activation Functions2024-03-15T15:06:41Z<p>David: Created page with "List of common activation functions ==Sinusoidal== ===Tanh=== One of the older activation functions ===Sigmoid=== ===Cosine/Sine=== See [https://proceedings.neurips.cc/paper/2020/hash/53c04118df112c13a8c34b38343b9c10-Abstract.html SIREN] ==ReLU== https://pytorch.org/docs/stable/generated/torch.nn.ReLU.html ReLU is one of the most popular activation functions. It simply performs <math>ReLU(x) = max(x, 0) = (x > 0) * x</math> ===LeakyReLU=== https://pytorch.org/docs..."</p>
<hr />
<div>List of common activation functions<br />
<br />
<br />
==Sinusoidal==<br />
===Tanh===<br />
One of the older activation functions<br />
<br />
===Sigmoid===<br />
<br />
===Cosine/Sine===<br />
See [https://proceedings.neurips.cc/paper/2020/hash/53c04118df112c13a8c34b38343b9c10-Abstract.html SIREN]<br />
<br />
==ReLU==<br />
https://pytorch.org/docs/stable/generated/torch.nn.ReLU.html<br />
<br />
ReLU is one of the most popular activation functions. It simply performs <math>ReLU(x) = max(x, 0) = (x > 0) * x</math><br />
<br />
===LeakyReLU===<br />
https://pytorch.org/docs/stable/generated/torch.nn.LeakyReLU.html<br />
<br />
<math>LeakyReLU(x) = (x > 0) * x + (x < 0) * (-0.01x)</math><br />
<br />
===SiLU===<br />
===GeLU===<br />
===GeGLU===<br />
<br />
==Resources==<br />
* [https://armandolivares.tech/2022/09/04/elu-gelu-and-silu-activation-functions/]</div>Davidhttps://wiki.davidl.me/index.php?title=Stable_Diffusion&diff=6956Stable Diffusion2024-03-15T14:55:34Z<p>David: /* Stable Diffusion 1 */</p>
<hr />
<div>Notes on the different versions of Stable Diffusion from what I can find online.<br />
<br />
==Stable Diffusion 1==<br />
Stable diffusion consists of three main components<br />
* CLIP text encoder<br />
* VAE<br />
* UNet latent diffusion model<br />
<br />
The main difference between stable diffusion and other diffusion models is that the diffusion operations happens in a low-resolution latent space. For a 512x512 image, the latent may only be 64x64, a factor of 8 times smaller. This significantly reduces the compute resources necessary.<br />
<br />
===Architecture===<br />
See [https://nn.labml.ai/diffusion/stable_diffusion/model/unet.html U-Net for Stable Diffusion] and [https://nn.labml.ai/diffusion/stable_diffusion/model/unet_attention.html Transformer for Stable Diffusion U-Net]<br />
<br />
===1.x===<br />
<br />
==Stable Diffusion 2==<br />
[https://stability.ai/news/stable-diffusion-v2-release Release Blog Post]<br />
<br />
Stable Diffusion 2 replaces the CLIP model with OpenCLIP, a retraining of CLIP using the publicly available LAION-5B dataset with NSFW images removed. By default they generate both 512x512 and 768x768 images.<br />
<br />
In additional, SD2 also includes the release of the following:<br />
* Super-resolution model<br />
* Depth to image model<br />
* Inpainting model<br />
<br />
===2.1===<br />
<br />
==Stable Diffusion XL==<br />
Stable Diffusion XL is a larger model trained on 1024x1024 images.<br />
<br />
==Stable Diffusion (XL) Turbo==<br />
[https://stability.ai/news/stability-ai-sdxl-turbo Blog post] [https://arxiv.org/abs/2311.17042 ADD Paper]<br />
<br />
Released Nov 2023, [https://huggingface.co/stabilityai/sd-turbo SD-Turbo] and [https://huggingface.co/stabilityai/sdxl-turbo SDXL-Turbo] are fine-tuned versions of SD2 and SDXL trained using adversarial diffusion distillation (ADD). <br />
<br />
ADD applies fine-tuning using an adversarial loss (from GANs) and a score distillation loss (from DreamFusion) such that each iteration the model produces a complete image. This allows SD-Turbo to produce realistic images in a single iteration while preserving the ability to contine refining the images with additional diffusion iterations.<br />
<br />
==Stable Cascade==<br />
[https://stability.ai/news/introducing-stable-cascade Release blog post]<br />
Stable Cascade introduces a latent generator<br />
<br />
==Stable Diffusion 3==<br />
Stable Diffusion 3 replaces the diffusion UNet with a [https://arxiv.org/abs/2212.09748 diffusion transformer (DiT)].<br />
<br />
==See Also==<br />
* [[Wikipedia: Stable_Diffusion]]</div>Davidhttps://wiki.davidl.me/index.php?title=Interview_Algorithms&diff=6955Interview Algorithms2024-03-11T16:43:45Z<p>David: /* Linear Searching */</p>
<hr />
<div>Insights from Leetcode problems.<br />
<br />
==Two Pointers Algorithms==<br />
Having two pointers can make your algorithm run in linear time.<br />
<br />
====Finding a cycle in a linked-list====<br />
Use two runners. <math>O(n)</math><br><br />
Runner 1 goes two steps per iteration.<br><br />
Runner 2 goes one step per iteration.<br><br />
If there is a cycle, runner 2 will lap runner 1 within 2 cycles.<br />
<br />
==Backtracking==<br />
====Permutations====<br />
Print all permutations of an array.<br><br />
The idea here is that you need a for-loop nested for each element of an array.<br><br />
So n elements means n nested for-loops. You use recursion to nest the loops.<br><br />
You can also think of this as a graph problem when you need to find every possible path with DFS.<br><br />
<br />
* [https://leetcode.com/problems/permutations/ Permutations]<br />
* [https://leetcode.com/problems/permutations-ii/ Permutations-ii]<br />
{{ hidden | Permute Brute-force solution |<br />
A more advanced solution would use backtracking, however it is time-consuming to implement for an interview.<br><br />
Here is a quick brute-force solution.<br />
* Enumerate all possible n^n numbers from 000 to 999 and then filter out number with duplicate digits<br />
<syntaxhighlight lang="cpp"><br />
class Solution {<br />
public:<br />
vector<vector<int>> permute(vector<int>& nums) {<br />
vector<vector<int>> ans;<br />
vector<int> indices(nums.size());<br />
permuteHelper(nums, indices, 0, ans);<br />
return ans;<br />
}<br />
<br />
bool isValid(vector<int>& indices) {<br />
vector<char> check(indices.size(), false);<br />
for (int i = 0; i < indices.size(); i++) {<br />
if (check[indices[i]]) {<br />
return false;<br />
}<br />
check[indices[i]] = true;<br />
}<br />
return true;<br />
}<br />
<br />
void permuteHelper(vector<int>& nums, vector<int>& indices,<br />
int col, vector<vector<int>>& ans) {<br />
if (col == nums.size()) {<br />
if (isValid(indices))<br />
print(nums, indices, ans);<br />
return;<br />
}<br />
for (int i = 0; i < nums.size(); i++) {<br />
indices[col] = i;<br />
permuteHelper(nums, indices, col+1, ans);<br />
}<br />
}<br />
<br />
void print(vector<int>& nums, vector<int>& indices, vector<vector<int>>& ans) {<br />
vector<int> new_nums(nums.size());<br />
for (int i = 0; i < nums.size(); i++) {<br />
new_nums[i] = nums[indices[i]];<br />
}<br />
ans.push_back(new_nums);<br />
}<br />
};<br />
</syntaxhighlight><br />
}}<br />
<br />
==Bit tricks==<br />
See https://www.geeksforgeeks.org/bit-tricks-competitive-programming/<br />
<br />
The most useful one is <br />
<pre><br />
n & n-1<br />
</pre><br />
which zeros the least significant set bit.<br />
E.g. this can be used to count the number of set bits.<br />
<br />
==Tricks==<br />
===Bitmask===<br />
<br />
===Counting===<br />
Counting as in tabulate not as in combinatorial counting.<br />
<br />
===Prefix Sum===<br />
<br />
==Data Structures==<br />
===Hashmap===<br />
Also known as a dictionary or associative array. Theses are used everywhere.<br />
<br />
===Segment Trees===<br />
See [https://cp-algorithms.com/data_structures/segment_tree.html CP Algorithms segment tree]<br />
<br />
===Union Find===<br />
In Union Find, you build a tree where each tree represents a set.<br><br />
Your given a pair of relations where (a, b) indices a and b are in the same set.<br><br />
The ''Union'' operation places a and b in the same set by attaching the root of b to the root of a.<br />
The ''Find'' operation recursively looks up the parent of a to find the root of the tree of a.<br />
<br />
<syntaxhighlight lang="python"><br />
parents = {}<br />
<br />
def find(a):<br />
while parents[a] != a:<br />
a = parents[a]<br />
return a<br />
<br />
for (a, b) in relations:<br />
if a not in parents:<br />
parent[a] = a<br />
a_root = find(a)<br />
if b not in parents:<br />
parent[b] = b<br />
b_root = find(b)<br />
parents[b_root] = a_root # Attach b_root to a_root<br />
</syntaxhighlight><br />
<br />
==Misc Tricks==<br />
<br />
<br />
====Finding duplicates in an array====<br />
If you have an array of ints where each number appears <math>n</math> times and one number appears <math>m>n</math> times where <math>gcd(n,m)==1</math>, <br />
then you count the number of times each bit appears and take it mod <math>n</math>.<br><br />
The remaining bits will remain <math>m \mod n</math> times.<br><br />
* [https://leetcode.com/problems/single-number/ single-number]<br />
* [https://leetcode.com/problems/single-number-ii/ single-number-ii]<br />
* [https://leetcode.com/problems/single-number-iii/ single-number-iii]</div>Davidhttps://wiki.davidl.me/index.php?title=Interview_Algorithms&diff=6954Interview Algorithms2024-03-11T16:40:47Z<p>David: /* Data Structures */</p>
<hr />
<div>Insights from Leetcode problems.<br />
<br />
==Linear Searching==<br />
====Finding a cycle in a linked-list====<br />
Use two runners. <math>O(n)</math><br><br />
Runner 1 goes two steps per iteration.<br><br />
Runner 2 goes one step per iteration.<br><br />
If there is a cycle, runner 2 will lap runner 1 within 2 cycles.<br />
<br />
<br />
<br />
==Backtracking==<br />
====Permutations====<br />
Print all permutations of an array.<br><br />
The idea here is that you need a for-loop nested for each element of an array.<br><br />
So n elements means n nested for-loops. You use recursion to nest the loops.<br><br />
You can also think of this as a graph problem when you need to find every possible path with DFS.<br><br />
<br />
* [https://leetcode.com/problems/permutations/ Permutations]<br />
* [https://leetcode.com/problems/permutations-ii/ Permutations-ii]<br />
{{ hidden | Permute Brute-force solution |<br />
A more advanced solution would use backtracking, however it is time-consuming to implement for an interview.<br><br />
Here is a quick brute-force solution.<br />
* Enumerate all possible n^n numbers from 000 to 999 and then filter out number with duplicate digits<br />
<syntaxhighlight lang="cpp"><br />
class Solution {<br />
public:<br />
vector<vector<int>> permute(vector<int>& nums) {<br />
vector<vector<int>> ans;<br />
vector<int> indices(nums.size());<br />
permuteHelper(nums, indices, 0, ans);<br />
return ans;<br />
}<br />
<br />
bool isValid(vector<int>& indices) {<br />
vector<char> check(indices.size(), false);<br />
for (int i = 0; i < indices.size(); i++) {<br />
if (check[indices[i]]) {<br />
return false;<br />
}<br />
check[indices[i]] = true;<br />
}<br />
return true;<br />
}<br />
<br />
void permuteHelper(vector<int>& nums, vector<int>& indices,<br />
int col, vector<vector<int>>& ans) {<br />
if (col == nums.size()) {<br />
if (isValid(indices))<br />
print(nums, indices, ans);<br />
return;<br />
}<br />
for (int i = 0; i < nums.size(); i++) {<br />
indices[col] = i;<br />
permuteHelper(nums, indices, col+1, ans);<br />
}<br />
}<br />
<br />
void print(vector<int>& nums, vector<int>& indices, vector<vector<int>>& ans) {<br />
vector<int> new_nums(nums.size());<br />
for (int i = 0; i < nums.size(); i++) {<br />
new_nums[i] = nums[indices[i]];<br />
}<br />
ans.push_back(new_nums);<br />
}<br />
};<br />
</syntaxhighlight><br />
}}<br />
<br />
==Bit tricks==<br />
See https://www.geeksforgeeks.org/bit-tricks-competitive-programming/<br />
<br />
The most useful one is <br />
<pre><br />
n & n-1<br />
</pre><br />
which zeros the least significant set bit.<br />
E.g. this can be used to count the number of set bits.<br />
<br />
==Tricks==<br />
===Bitmask===<br />
<br />
===Counting===<br />
Counting as in tabulate not as in combinatorial counting.<br />
<br />
===Prefix Sum===<br />
<br />
==Data Structures==<br />
===Hashmap===<br />
Also known as a dictionary or associative array. Theses are used everywhere.<br />
<br />
===Segment Trees===<br />
See [https://cp-algorithms.com/data_structures/segment_tree.html CP Algorithms segment tree]<br />
<br />
===Union Find===<br />
In Union Find, you build a tree where each tree represents a set.<br><br />
Your given a pair of relations where (a, b) indices a and b are in the same set.<br><br />
The ''Union'' operation places a and b in the same set by attaching the root of b to the root of a.<br />
The ''Find'' operation recursively looks up the parent of a to find the root of the tree of a.<br />
<br />
<syntaxhighlight lang="python"><br />
parents = {}<br />
<br />
def find(a):<br />
while parents[a] != a:<br />
a = parents[a]<br />
return a<br />
<br />
for (a, b) in relations:<br />
if a not in parents:<br />
parent[a] = a<br />
a_root = find(a)<br />
if b not in parents:<br />
parent[b] = b<br />
b_root = find(b)<br />
parents[b_root] = a_root # Attach b_root to a_root<br />
</syntaxhighlight><br />
<br />
==Misc Tricks==<br />
<br />
<br />
====Finding duplicates in an array====<br />
If you have an array of ints where each number appears <math>n</math> times and one number appears <math>m>n</math> times where <math>gcd(n,m)==1</math>, <br />
then you count the number of times each bit appears and take it mod <math>n</math>.<br><br />
The remaining bits will remain <math>m \mod n</math> times.<br><br />
* [https://leetcode.com/problems/single-number/ single-number]<br />
* [https://leetcode.com/problems/single-number-ii/ single-number-ii]<br />
* [https://leetcode.com/problems/single-number-iii/ single-number-iii]</div>Davidhttps://wiki.davidl.me/index.php?title=Random_sample_consensus&diff=6953Random sample consensus2024-03-09T02:36:48Z<p>David: </p>
<hr />
<div><br />
Random sample consensus (RANSAC) is an iterative algorithm to estimate parameters of a model.<br />
<br />
The idea is to continuously randomly sample a subset of your data.<br><br />
For each subset, you build a model and do cross-validation until you find a model with sufficiently small error.<br />
You quit after <math>k</math> iterations or once your model has sufficiently low error.<br />
<br />
This is commonly used when you have a lot of points and building a model is worse than <math>O(n)</math>.<br><br />
An example is if you need to do least squares minimization or calculate an SVD to build your model.<br><br />
In this case, it is more efficient to build several models using a small subset of the points and pick the best model.<br />
<br />
==Algorithm==<br />
Copied from [[Wikipedia: Random sample consensus]]<br />
<pre><br />
Given:<br />
data – A set of observations.<br />
model – A model to explain observed data points.<br />
n – Minimum number of data points required to estimate model parameters.<br />
k – Maximum number of iterations allowed in the algorithm.<br />
t – Threshold value to determine data points that are fit well by model.<br />
d – Number of close data points required to assert that a model fits well to data.<br />
<br />
Return:<br />
bestFit – model parameters which best fit the data (or nul if no good model is found)<br />
<br />
iterations = 0<br />
bestFit = nul<br />
bestErr = something really large<br />
<br />
while iterations < k do<br />
maybeInliers := n randomly selected values from data<br />
maybeModel := model parameters fitted to maybeInliers<br />
alsoInliers := empty set<br />
for every point in data not in maybeInliers do<br />
if point fits maybeModel with an error smaller than t<br />
add point to alsoInliers<br />
end for<br />
if the number of elements in alsoInliers is > d then<br />
// This implies that we may have found a good model<br />
// now test how good it is.<br />
betterModel := model parameters fitted to all points in maybeInliers and alsoInliers<br />
thisErr := a measure of how well betterModel fits these points<br />
if thisErr < bestErr then<br />
bestFit := betterModel<br />
bestErr := thisErr<br />
end if<br />
end if<br />
increment iterations<br />
end while<br />
<br />
return bestFit<br />
</pre><br />
<br />
==Use Cases==<br />
* Fundamental matrix estimation</div>Davidhttps://wiki.davidl.me/index.php?title=Diffusion_Models&diff=6952Diffusion Models2024-03-08T20:35:01Z<p>David: /* Resources */</p>
<hr />
<div>==Background==<br />
By Sohl-Dickstein ''et al.''[https://arxiv.org/pdf/1503.03585.pdf].<br />
<br />
The goal is to define a mapping between a complex distribution <math>q(\mathbf{x}^{(0)})</math> (e.g. set of realistic images) to a simple distribution <math>\pi(\mathbf{y})=p(\mathbf{x}^{(T)})</math>(e.g. multivariate normal).<br><br />
This is done by defining a forward trajectory <math>q(\mathbf{x}^{(0...T)})</math> and optimizing a reverse trajectory <math>p(\mathbf{x}^{(0 ... T)})</math>.<br><br />
The forward trajectory is repeatedly applying a Markov diffusion kernel (i.e. a function with a steady distribution <math>\pi(\mathbf{y})</math>), performing T steps of diffusion.<br><br />
The reverse trajectory is again applying a diffusion kernel but with an estimated mean and variance.<br><br />
<br />
==Image Generation==<br />
===DDPM===<br />
See [https://arxiv.org/pdf/2006.11239.pdf DDPM paper]<br><br />
<br />
Here, the diffusion process is modeled as:<br />
* Forward: <math>q(\mathbf{x}_t, \mathbf{x}_{t-1}) \sim N(\sqrt{1-\beta_t} \mathbf{x}_{t-1}, \beta_t \mathbf{I})</math><br />
* Reverse: <math>p_\theta(\mathbf{x}_{t-1}, \mathbf{t}) \sim N( \mu_\theta (x_t, t), \beta_t \mathbf{I})</math><br />
<br />
The forward diffusion can be sampled for any <math>t</math> using:<br><br />
<math>\mathbf{x}_{t} = \sqrt{\bar\alpha_t} \mathbf{x}_0 - \sqrt{1-\bar\alpha_t} \boldsymbol{\epsilon}</math> where <math>\bar\alpha_t = \prod_{s=1}^{t}(1-\beta{s})</math><br />
<br />
The loss function is based on the mean of the posterior.<br><br />
If we estimate <math>\mu_\theta(x_t, t)</math> as <math>\frac{1}{\sqrt{\alpha_t}} \left( x_t - \frac{\beta_t}{\sqrt{1-\bar\alpha_t}} \boldsymbol{\epsilon}_\theta (\mathbf{x}_t, t) \right)</math>, then the loss function simplifies to:<br><br />
<math>E \left[ \frac{\beta^2_t}{2\sigma^2_t \alpha (1-\bar\alpha_t)} \Vert \boldsymbol{\epsilon} - \boldsymbol{\epsilon}_\theta( \sqrt{\bar\alpha_t} \mathbf{x}_0 - \sqrt{1-\bar\alpha_t} \boldsymbol{\epsilon}, t) \Vert^2 \right]</math><br />
<br />
===Super-resolution and other Image-to-image generation===<br />
See [https://iterative-refinement.github.io/ SR3 iterative refinement]<br><br />
Here we use <math>\mathbf{y}</math> to represent the sequence of priors and we condition on an extra input <math>\mathbf{x}</math> which is the low-resolution image.<br><br />
The neural network <math>f_{\theta}(\mathbf{x}, \mathbf{y}, \gamma)</math> continues to predict the added noise during training the reverse process.<br />
<br />
An unofficial PyTorch implementation of SR3 is available at [https://github.com/Janspiry/Image-Super-Resolution-via-Iterative-Refinement https://github.com/Janspiry/Image-Super-Resolution-via-Iterative-Refinement].<br />
<br />
In addition to SR3, the researchers at Google have also unveiled [https://iterative-refinement.github.io/palette/ Palette] which utilizes the same ideas to perform additional image operations such as colorization, uncropping, and inpainting. These tasks can be performed with a single model.<br />
<br />
===Text-to-image===<br />
OpenAI have unveiled two text-to-image models, [https://github.com/openai/glide-text2im GLIDE] and [https://openai.com/dall-e-2/ DALL-E 2], which rely on diffusion models to generate images.<br><br />
GLIDE has some open-source code which allows you to test a small version.<br />
<br />
At a high-level, GLIDE is a diffusion model which is conditioned on text embeddings and trained with a technique called classifier-free guidance.<br><br />
DALL-E 2 adds a ''prior'' model which first converts a text embedding to a CLIP image embedding.<br />
Then the diffusion ''decoder'' generates an image based on the image embedding.<br />
<br />
==Guided Diffusion==<br />
Guidance is a method used to push the diffusion process towards the input condition, e.g. the text input.<br><br />
There are two types of guidance: classifier guidance and classifier-free guidance.<br><br />
See [https://benanne.github.io/2022/05/26/guidance.html https://benanne.github.io/2022/05/26/guidance.html].<br />
<br />
Classifier guidance uses an image classifier (e.g. clip) to update the noisy input images towards the desired class.<br><br />
Classifier-free guidance<ref name="ho2021classifierfree"/> performs inference on the diffusion model to predict the noise with and without the class input, and extrapolating away from the output without noise.<br />
<br />
==Inversion==<br />
See [https://arxiv.org/abs/2105.05233 Diffusion Models Beat GANs on Image Synthesis].<br><br />
Inversion of a diffusion model can be done by using DDIM for the reverse process.<br><br />
This is done by using a variance of 0 for the sampling, hence making the reverse process (latent to image) deterministic.<br />
<br />
==Resources==<br />
* [https://ai.googleblog.com/2021/07/high-fidelity-image-generation-using.html Google AI Blog High Fidelity Image Generation Using Diffusion Models] - discusses SR3 and CDM<br />
* https://theaisummer.com/diffusion-models/<br />
<br />
==References==<br />
{{reflist|refs=<br />
<ref name="ho2021classifierfree">Ho, J., & Salimans, T. (2022). Classifier-Free Diffusion Guidance. doi:10.48550/ARXIV.2207.12598 https://arxiv.org/abs/2207.12598</ref><br />
}}</div>Davidhttps://wiki.davidl.me/index.php?title=Stable_Diffusion&diff=6951Stable Diffusion2024-03-08T16:11:49Z<p>David: /* Stable Diffusion Turbo */</p>
<hr />
<div>Notes on the different versions of Stable Diffusion from what I can find online.<br />
<br />
==Stable Diffusion 1==<br />
Stable diffusion consists of three main components<br />
* CLIP text encoder<br />
* VAE<br />
* UNet latent diffusion model<br />
<br />
The main difference between stable diffusion and other diffusion models is that the diffusion operations happens in a low-resolution latent space. For a 512x512 image, the latent may only be 64x64, a factor of 8 times smaller. This significantly reduces the compute resources necessary.<br />
<br />
===1.x===<br />
<br />
==Stable Diffusion 2==<br />
[https://stability.ai/news/stable-diffusion-v2-release Release Blog Post]<br />
<br />
Stable Diffusion 2 replaces the CLIP model with OpenCLIP, a retraining of CLIP using the publicly available LAION-5B dataset with NSFW images removed. By default they generate both 512x512 and 768x768 images.<br />
<br />
In additional, SD2 also includes the release of the following:<br />
* Super-resolution model<br />
* Depth to image model<br />
* Inpainting model<br />
<br />
===2.1===<br />
<br />
==Stable Diffusion XL==<br />
Stable Diffusion XL is a larger model trained on 1024x1024 images.<br />
<br />
==Stable Diffusion (XL) Turbo==<br />
[https://stability.ai/news/stability-ai-sdxl-turbo Blog post] [https://arxiv.org/abs/2311.17042 ADD Paper]<br />
<br />
Released Nov 2023, [https://huggingface.co/stabilityai/sd-turbo SD-Turbo] and [https://huggingface.co/stabilityai/sdxl-turbo SDXL-Turbo] are fine-tuned versions of SD2 and SDXL trained using adversarial diffusion distillation (ADD). <br />
<br />
ADD applies fine-tuning using an adversarial loss (from GANs) and a score distillation loss (from DreamFusion) such that each iteration the model produces a complete image. This allows SD-Turbo to produce realistic images in a single iteration while preserving the ability to contine refining the images with additional diffusion iterations.<br />
<br />
==Stable Cascade==<br />
[https://stability.ai/news/introducing-stable-cascade Release blog post]<br />
Stable Cascade introduces a latent generator<br />
<br />
==Stable Diffusion 3==<br />
Stable Diffusion 3 replaces the diffusion UNet with a [https://arxiv.org/abs/2212.09748 diffusion transformer (DiT)].<br />
<br />
==See Also==<br />
* [[Wikipedia: Stable_Diffusion]]</div>Davidhttps://wiki.davidl.me/index.php?title=Stable_Diffusion&diff=6950Stable Diffusion2024-03-08T16:11:03Z<p>David: /* Stable Diffusion Turbo */</p>
<hr />
<div>Notes on the different versions of Stable Diffusion from what I can find online.<br />
<br />
==Stable Diffusion 1==<br />
Stable diffusion consists of three main components<br />
* CLIP text encoder<br />
* VAE<br />
* UNet latent diffusion model<br />
<br />
The main difference between stable diffusion and other diffusion models is that the diffusion operations happens in a low-resolution latent space. For a 512x512 image, the latent may only be 64x64, a factor of 8 times smaller. This significantly reduces the compute resources necessary.<br />
<br />
===1.x===<br />
<br />
==Stable Diffusion 2==<br />
[https://stability.ai/news/stable-diffusion-v2-release Release Blog Post]<br />
<br />
Stable Diffusion 2 replaces the CLIP model with OpenCLIP, a retraining of CLIP using the publicly available LAION-5B dataset with NSFW images removed. By default they generate both 512x512 and 768x768 images.<br />
<br />
In additional, SD2 also includes the release of the following:<br />
* Super-resolution model<br />
* Depth to image model<br />
* Inpainting model<br />
<br />
===2.1===<br />
<br />
==Stable Diffusion XL==<br />
Stable Diffusion XL is a larger model trained on 1024x1024 images.<br />
<br />
==Stable Diffusion Turbo==<br />
[https://arxiv.org/abs/2311.17042 paper]<br />
<br />
Released Nov 2023, [https://huggingface.co/stabilityai/sd-turbo SD-Turbo] and [https://huggingface.co/stabilityai/sdxl-turbo SDXL-Turbo] are fine-tuned versions of SD2 and SDXL trained using adversarial diffusion distillation (ADD). <br />
<br />
ADD applies fine-tuning using an adversarial loss (from GANs) and a score distillation loss (from DreamFusion) such that each iteration the model produces a complete image. This allows SD-Turbo to produce realistic images in a single iteration while preserving the ability to contine refining the images with additional diffusion iterations.<br />
<br />
==Stable Cascade==<br />
[https://stability.ai/news/introducing-stable-cascade Release blog post]<br />
Stable Cascade introduces a latent generator<br />
<br />
==Stable Diffusion 3==<br />
Stable Diffusion 3 replaces the diffusion UNet with a [https://arxiv.org/abs/2212.09748 diffusion transformer (DiT)].<br />
<br />
==See Also==<br />
* [[Wikipedia: Stable_Diffusion]]</div>Davidhttps://wiki.davidl.me/index.php?title=Stable_Diffusion&diff=6949Stable Diffusion2024-03-08T16:10:43Z<p>David: Created page with "Notes on the different versions of Stable Diffusion from what I can find online. ==Stable Diffusion 1== Stable diffusion consists of three main components * CLIP text encoder * VAE * UNet latent diffusion model The main difference between stable diffusion and other diffusion models is that the diffusion operations happens in a low-resolution latent space. For a 512x512 image, the latent may only be 64x64, a factor of 8 times smaller. This significantly reduces the comp..."</p>
<hr />
<div>Notes on the different versions of Stable Diffusion from what I can find online.<br />
<br />
==Stable Diffusion 1==<br />
Stable diffusion consists of three main components<br />
* CLIP text encoder<br />
* VAE<br />
* UNet latent diffusion model<br />
<br />
The main difference between stable diffusion and other diffusion models is that the diffusion operations happens in a low-resolution latent space. For a 512x512 image, the latent may only be 64x64, a factor of 8 times smaller. This significantly reduces the compute resources necessary.<br />
<br />
===1.x===<br />
<br />
==Stable Diffusion 2==<br />
[https://stability.ai/news/stable-diffusion-v2-release Release Blog Post]<br />
<br />
Stable Diffusion 2 replaces the CLIP model with OpenCLIP, a retraining of CLIP using the publicly available LAION-5B dataset with NSFW images removed. By default they generate both 512x512 and 768x768 images.<br />
<br />
In additional, SD2 also includes the release of the following:<br />
* Super-resolution model<br />
* Depth to image model<br />
* Inpainting model<br />
<br />
===2.1===<br />
<br />
==Stable Diffusion XL==<br />
Stable Diffusion XL is a larger model trained on 1024x1024 images.<br />
<br />
==Stable Diffusion Turbo==<br />
[https://arxiv.org/abs/2311.17042 paper]<br />
Release Nov 2023, [https://huggingface.co/stabilityai/sd-turbo SD-Turbo] and [https://huggingface.co/stabilityai/sdxl-turbo SDXL-Turbo] are fine-tuned versions of SD2 and SDXL trained using adversarial diffusion distillation (ADD). ADD applies fine-tuning using an adversarial loss (from GANs) and a score distillation loss (from DreamFusion) such that each iteration the model produces a complete image. This allows SD-Turbo to produce realistic images in a single iteration while preserving the ability to contine refining the images with additional diffusion iterations.<br />
<br />
==Stable Cascade==<br />
[https://stability.ai/news/introducing-stable-cascade Release blog post]<br />
Stable Cascade introduces a latent generator<br />
<br />
==Stable Diffusion 3==<br />
Stable Diffusion 3 replaces the diffusion UNet with a [https://arxiv.org/abs/2212.09748 diffusion transformer (DiT)].<br />
<br />
==See Also==<br />
* [[Wikipedia: Stable_Diffusion]]</div>Davidhttps://wiki.davidl.me/index.php?title=3D_Representations&diff=69483D Representations2024-03-06T16:05:21Z<p>David: /* Reconstruction */</p>
<hr />
<div>Ways to represent 3D objects and scenes.<br />
<br />
==Representations==<br />
===Collection of images===<br />
Just a set of 2D images. Videos may also fall under this category. <br />
Images may or may not have depth and may or may not be posed.<br />
<br />
===Light Field===<br />
{{main | Light field}}<br />
This is similar to a collection of images.<br><br />
However, instead of thinking of it as a set of images, each pixel represents the color along a ray in 3D space.<br><br />
Thus, light fields are collections of rays in 3D space which can be modeled using the plenoptic function <math>F: \mathbb{R}^5 \to \mathbb{R}</math>.<br><br />
3-dimensions for the starting point of the ray and 2 dimensions for the direction of the ray.<br><br />
Typically we assume the rays lie in an empty/transparent space until they hit a surface thus rays can be models as lines which can be defined with 4 dimensions.<br><br />
<br />
===Volume===<br />
A volume is a dense 3D dataset <math>F: \mathbb{R}^3 \to \mathbb{R}</math> where the value at each position <math>(x,y,z)</math> corresponds to a density.<br><br />
Volume rendering is used project a 3D volume into a 2D image by sampling the volume along a ray for each pixel in the 2D image.<br><br />
Also known as a radiance field. These can be encoded as explicit functions or neural networks.<br />
<br />
===Signed Distance Field===<br />
A signed distance field is a dense 3D dataset <math>F: \mathbb{R}^2 \to \mathbb{R}</math> where each position represents a distance to the nearest surface. <br />
Positive values represent a point on the exterior of an object whereas negative values represent a point on the interior. <br />
Ray marching is used to render signed distance fields into 2D images.<br />
<br />
===Point-clouds===<br />
A list of points in 3D (<math>N \times 3</math>). Points may also have color or other values. <br />
Typically points are not semantically labeled so points are entirely unrelated to each other.<br />
<br />
===Mesh===<br />
A list of vertices (<math>N \times 3</math>) and triangles (<math>N \times 3</math>). <br />
The current standard representation used in real-time 3D applications.<br />
<br />
===CAD Models===<br />
These are vector representations with relationships between objects. <br />
E.g. Object A is left of Object B by 5 centimeters.<br />
<br />
==Conversions==<br />
===Volume rendering===<br />
Volume rendering converts volumes to 2D images.<br><br />
Differentiable volume rendering (NeRF) can convert posed 2D images to neural volumes.<br />
<br />
===Ray marching===<br />
Ray marching converts signed distance fields to 2D images.<br />
<br />
===Rasterization===<br />
Rasterization converts meshes to 2D images.<br />
<br />
===Marching cubes===<br />
Marching cubes converts volumes or signed distance fields to meshes.<br />
<br />
===Reconstruction===<br />
Structure from motion and multi view stereo methods can build point clouds from 2D images.<br><br />
Meshing, or [[Surface Reconstruction]], works on converting this point clouds into meshes.<br />
<br />
==See Also==<br />
* [[Image-based rendering]]</div>Davidhttps://wiki.davidl.me/index.php?title=Surface_Reconstruction&diff=6947Surface Reconstruction2024-03-06T16:04:42Z<p>David: Created page with "Surface reconstruction is the process of converting a point cloud into a mesh. ==Explicit Reconstruction== The idea here is to just connect the points to form triangles. ==Implicit Reconstruction== The idea here is to first estimate a signed distance field from the point cloud and then do marching cubes to generate a mesh. ==Resources== * [https://www.hao-li.com/cs599-ss2015/slides/Lecture06.2.pdf Hao Li lecture slides] * [https://graphics.stanford.edu/papers/zipper/..."</p>
<hr />
<div>Surface reconstruction is the process of converting a point cloud into a mesh.<br />
<br />
==Explicit Reconstruction==<br />
The idea here is to just connect the points to form triangles.<br />
<br />
<br />
==Implicit Reconstruction==<br />
The idea here is to first estimate a signed distance field from the point cloud and then do marching cubes to generate a mesh.<br />
<br />
==Resources==<br />
* [https://www.hao-li.com/cs599-ss2015/slides/Lecture06.2.pdf Hao Li lecture slides]<br />
* [https://graphics.stanford.edu/papers/zipper/zipper.pdf Zippered Polygon Meshes from Range Images (1994)]</div>Davidhttps://wiki.davidl.me/index.php?title=Mamba_(machine_learning_model)&diff=6946Mamba (machine learning model)2024-02-29T22:01:57Z<p>David: Created page with "See https://maartengrootendorst.substack.com/p/a-visual-guide-to-mamba-and-state"</p>
<hr />
<div>See https://maartengrootendorst.substack.com/p/a-visual-guide-to-mamba-and-state</div>Davidhttps://wiki.davidl.me/index.php?title=Cloud_Providers&diff=6945Cloud Providers2024-02-29T16:37:39Z<p>David: /* Big sizes */</p>
<hr />
<div>List of common cloud providers<br />
<br />
<br />
==Big sizes==<br />
Use these for professional applications where uptime, scaling, and support are essential.<br />
* Amazon Web Services (AWS)<br />
* Microsoft Azure<br />
* Google Cloud Platform (GCP)<br />
* Oracle Cloud<br />
<br />
==Medium sizes==<br />
These are reputable cloud providers, good for small businesss and self-hosted use cases where price is a concern.<br />
* Hetzner<br />
* Akamai Linode<br />
* DigitalOcean<br />
<br />
==Small sizes==<br />
See lowendbox.com for smaller cloud providers.<br />
<br />
==Storage==<br />
All the big cloud providers offer storage. These are additional options for different purposes.<br />
<br />
===Object Storage===<br />
;Backups<br />
* Backblaze B2<br />
* Wasabi<br />
;Heavy Egress<br />
* Cloudflare R2<br />
<br />
===SSH/SFTP Backup===<br />
* rsync.net</div>Davidhttps://wiki.davidl.me/index.php?title=Cloud_Providers&diff=6944Cloud Providers2024-02-29T16:36:08Z<p>David: /* Big sizes */</p>
<hr />
<div>List of common cloud providers<br />
<br />
<br />
==Big sizes==<br />
Use these for professional applications where you uptime, scaling, and support are essential.<br />
* Amazon Web Services (AWS)<br />
* Microsoft Azure<br />
* Google Cloud Platform (GCP)<br />
* Oracle Cloud<br />
<br />
==Medium sizes==<br />
These are reputable cloud providers, good for small businesss and self-hosted use cases where price is a concern.<br />
* Hetzner<br />
* Akamai Linode<br />
* DigitalOcean<br />
<br />
==Small sizes==<br />
See lowendbox.com for smaller cloud providers.<br />
<br />
==Storage==<br />
All the big cloud providers offer storage. These are additional options for different purposes.<br />
<br />
===Object Storage===<br />
;Backups<br />
* Backblaze B2<br />
* Wasabi<br />
;Heavy Egress<br />
* Cloudflare R2<br />
<br />
===SSH/SFTP Backup===<br />
* rsync.net</div>Davidhttps://wiki.davidl.me/index.php?title=Cloud_Providers&diff=6943Cloud Providers2024-02-29T16:35:19Z<p>David: /* Medium sizes */</p>
<hr />
<div>List of common cloud providers<br />
<br />
<br />
==Big sizes==<br />
Use these for professional applications<br />
* Amazon Web Services (AWS)<br />
* Microsoft Azure<br />
* Google Cloud Platform (GCP)<br />
* Oracle Cloud<br />
<br />
==Medium sizes==<br />
These are reputable cloud providers, good for small businesss and self-hosted use cases where price is a concern.<br />
* Hetzner<br />
* Akamai Linode<br />
* DigitalOcean<br />
<br />
==Small sizes==<br />
See lowendbox.com for smaller cloud providers.<br />
<br />
==Storage==<br />
All the big cloud providers offer storage. These are additional options for different purposes.<br />
<br />
===Object Storage===<br />
;Backups<br />
* Backblaze B2<br />
* Wasabi<br />
;Heavy Egress<br />
* Cloudflare R2<br />
<br />
===SSH/SFTP Backup===<br />
* rsync.net</div>Davidhttps://wiki.davidl.me/index.php?title=Cloud_Providers&diff=6942Cloud Providers2024-02-29T16:33:56Z<p>David: Created page with "List of common cloud providers ==Big sizes== Use these for professional applications * Amazon Web Services (AWS) * Microsoft Azure * Google Cloud Platform (GCP) * Oracle Cloud ==Medium sizes== These are reputable cloud providers, good for self-hosted use cases. * Hetzner * Akamai Linode ==Storage== All the big cloud providers offer storage. These are additional options for different purposes. ===Object Storage=== ;Backups * Backblaze B2 * Wasabi ;Heavy Egress * Clou..."</p>
<hr />
<div>List of common cloud providers<br />
<br />
<br />
==Big sizes==<br />
Use these for professional applications<br />
* Amazon Web Services (AWS)<br />
* Microsoft Azure<br />
* Google Cloud Platform (GCP)<br />
* Oracle Cloud<br />
<br />
==Medium sizes==<br />
These are reputable cloud providers, good for self-hosted use cases.<br />
* Hetzner<br />
* Akamai Linode<br />
<br />
==Storage==<br />
All the big cloud providers offer storage. These are additional options for different purposes.<br />
<br />
===Object Storage===<br />
;Backups<br />
* Backblaze B2<br />
* Wasabi<br />
;Heavy Egress<br />
* Cloudflare R2<br />
<br />
===SSH/SFTP Backup===<br />
* rsync.net</div>Davidhttps://wiki.davidl.me/index.php?title=Probability&diff=6941Probability2024-02-22T22:57:11Z<p>David: /* Order Statistics */</p>
<hr />
<div>Calculus-based Probability<br />
<br />
This is content covered in STAT410 and STAT700 at UMD.<br />
<br />
==Basics==<br />
===Axioms of Probability===<br />
* <math>0 \leq P(E) \leq 1</math><br />
* <math>P(S) = 1</math> where <math>S</math> is your sample space<br />
* For mutually exclusive events <math>E_1, E_2, ...</math>, <math>P\left(\bigcup_i^\infty E_i\right) = \sum_i^\infty P(E_i)</math><br />
<br />
===Monotonicity===<br />
* For all events <math>A</math> and <math>B</math>, <math>A \subset B \implies P(A) \leq P(B)</math><br />
{{hidden | Proof | }}<br />
<br />
===Conditional Probability===<br />
<math>P(A|B)</math> is the probability of event A given event B.<br><br />
Mathematically, this is defined as <math>P(A|B) = P(A,B) / P(B)</math>.<br><br />
Note that this can also be written as <math>P(A|B)P(B) = P(A, B)</math><br />
With some additional substitution, we get '''Baye's Theorem''':<br />
<math><br />
P(A|B) = \frac{P(B|A)P(A)}{P(B)}<br />
</math><br />
<br />
==Random Variables==<br />
A random variable is a variable which takes on a distribution rather than a value.<br />
<br />
===PMF, PDF, CDF===<br />
For discrete distributions, we call <math>p_{X}(x)=P(X=x)</math> the probability mass function (PMF).<br><br />
For continuous distributions, we have the probability density function (PDF) <math>f(x)</math>.<br><br />
The comulative distribution function (CDF) is <math>F(x) = P(X \leq x)</math>.<br><br />
The CDF is the prefix sum of the PMF or the integral of the PDF. Likewise, the PDF is the derivative of the CDF.<br />
<br />
===Joint Random Variables===<br />
Two random variables are independant iff <math>f_{X,Y}(x,y) = f_X(x) f_Y(y)</math>.<br><br />
Otherwise, the marginal distribution is <math>f_X(x) = \int f_{X,Y}(x,y) dy</math>.<br />
<br />
===Change of variables===<br />
Let <math>g</math> be a monotonic increasing function and <math>Y = g(X)</math>.<br><br />
Then <math>F_Y(y) = P(Y \leq y) = P(X \leq g^{-1}(y)) = F_X(g^{-1}(y))</math>.<br><br />
And <math>f_Y(y) = \frac{d}{dy} F_Y(y) = \frac{d}{dy} F_X(g^{-1}(y)) = f_X(g^{-1}(y)) \frac{d}{dy}g^{-1}(y)</math><br><br />
Hence:<br />
<math display="block"><br />
f_Y(y) = f_x(g^{-1}(y)) \frac{d}{dy} g^{-1}(y)<br />
</math><br />
<br />
==Expectation and Variance==<br />
Some definitions and properties.<br />
===Definitions===<br />
Let <math>X \sim D</math> for some distribution <math>D</math>.<br />
Let <math>S</math> be the support or domain of your distribution.<br />
* <math>E(X) = \sum_S xp(x)</math> or <math>\int_S xp(x)dx</math><br />
* <math>Var(X) = E[(X-E(X))^2] = E(X^2) - (E(X))^2</math><br />
<br />
===Total Expection===<br />
<math>E_{X}(X) = E_{Y}(E_{X|Y}(X|Y))</math><br><br />
Dr. Xu refers to this as the smooth property.<br />
{{hidden | Proof |<br />
<math><br />
\begin{aligned}<br />
E(X) &= \int_S x p(x)dx \\<br />
&= \int_x x \int_y p(x,y)dy dx \\<br />
&= \int_x x \int_y p(x|y)p(y)dy dx \\<br />
&= \int_y\int_x x p(x|y)dxp(y)dy<br />
\end{aligned}<br />
</math><br />
}}<br />
<br />
===Total Variance===<br />
<math>Var(Y) = E(Var(Y|X)) + Var(E(Y | X))</math><br><br />
This one is not used as often on tests as total expectation<br />
{{hidden | Proof |<br />
<math><br />
\begin{aligned}<br />
Var(Y) &= E(Y^2) - E(Y)^2 \\<br />
&= E(E(Y^2|X)) - E(E(Y|X))^2\\<br />
&= E(Var(Y|X) + E(Y|X)^2) - E(E(Y|X))^2\\<br />
&= E((Var(Y|X)) + E(E(Y|X)^2) - E(E(Y|X))^2\\<br />
&= E((Var(Y|X)) + Var(E(Y|X))\\<br />
\end{aligned}<br />
</math><br />
}}<br />
<br />
===Sample Mean and Variance===<br />
The sample mean is <math>\bar{X} = \frac{1}{n}\sum_{i=1}^{n}X_i</math>.<br><br />
The unbiased sample variance is <math>S^2 = \frac{1}{n-1}\sum_{i=1}^{n}(X_i - \bar{X})^2</math>.<br />
<br />
====Student's Theorem====<br />
Let <math>X_1,...,X_n</math> be from <math>N(\mu, \sigma^2)</math>.<br><br />
Then the following results about the sample mean <math>\bar{X}</math><br />
and the unbiased sample variance <math>S^2</math> hold:<br />
* <math>\bar{X}</math> and <math>S^2</math> are independent<br />
* <math>\bar{X} \sim N(\mu, \sigma^2 / n)</math><br />
* <math>(n-1)S^2 / \sigma^2 \sim \chi^2(n-1)</math><br />
<br />
===Jensen's Inequality===<br />
{{main | Wikipedia: Jensen's inequality}}<br />
Let g be a convex function (i.e. second derivative is positive).<br />
Then <math>g(E(x)) \leq E(g(x))</math>.<br />
<br />
==Moments and Moment Generating Functions==<br />
===Definitions===<br />
{{main | Wikipedia: Moment (mathematics) | Wikipedia: Central moment | Wikipedia: Moment-generating function}}<br />
* <math>E(X^n)</math> the n'th moment<br />
* <math>E((X-\mu)^n)</math> the n'th central moment<br />
* <math>E(((X-\mu) / \sigma)^n)</math> the n'th standardized moment<br />
Expectation is the first moment and variance is the second central moment.<br><br />
Additionally, ''skew'' is the third standardized moment and ''kurtosis'' is the fourth standardized moment.<br />
<br />
===Moment Generating Functions===<br />
To compute moments, we can use a moment generating function (MGF):<br />
<math display="block">M_X(t) = E(e^{tX})</math><br />
With the MGF, we can get any order moments by taking n derivatives and setting <math display="inline">t=0</math>.<br />
; Notes<br />
* The MGF, if it exists, uniquely defines the distribution.<br />
* The MGF of <math>X+Y</math> is <math>MGF_{X+Y}(t) = E(e^{t(X+Y)})=E(e^{tX})E(e^{tY}) = MGF_X(t) * MGF_Y(t)</math><br />
<br />
===Characteristic function===<br />
<br />
==Convergence==<br />
{{main | Wikipedia: Convergence of random variables}}<br />
There are 4 common types of convergence.<br />
<br />
===Almost Surely===<br />
* <math>P(\lim X_i = X) = 1</math><br />
<br />
===In Probability===<br />
For all <math>\epsilon > 0</math><br><br />
<math>\lim P(|X_i - X| \geq \epsilon) = 0</math><br />
* Implies Convergence in distribution<br />
<br />
===In Distribution===<br />
Pointwise convergence of the cdf<br><br />
A sequence of random variables <math>X_1,...</math> converges to <math>X</math> in probability <br />
if for all <math>x \in S</math>,<br><br />
<math>\lim_{i \rightarrow \infty} F_i(x) = F(x)</math><br />
* Equivalent to convergence in probability if it converges to a degenerate distribution (i.e. a number)<br />
<br />
===In Mean Squared===<br />
<math>\lim_{i \rightarrow \infty} E(|X_i-X|^2)=0</math><br />
<br />
==Delta Method==<br />
{{main | Wikipedia:Delta method}}<br />
<br />
Suppose <math>\sqrt{n}(X_n - \theta) \xrightarrow{D} N(0, \sigma^2)</math>.<br><br />
Let <math>g</math> be a function such that <math>g'</math> exists and <math>g'(\theta) \neq 0</math><br><br />
Then <math>\sqrt{n}(g(X_n) - g(\theta)) \xrightarrow{D} N(0, \sigma^2 g'(\theta)^2)</math><br />
<br />
Multivariate:<br><br />
<math>\sqrt{n}(B - \beta) \xrightarrow{D} N(0, \Sigma) \implies \sqrt{n}(h(B)-h(\beta)) \xrightarrow{D} N(0, h'(\theta)^T \Sigma h'(\theta))</math><br />
<br />
;Notes<br />
* You can think of this like the Mean Value theorem for random variables.<br />
** <math>(g(X_n) - g(\theta)) \approx g'(\theta)(X_n - \theta)</math><br />
<br />
==Order Statistics==<br />
<br />
Consider iid random variables <math>X_1, ..., X_n</math>.<br><br />
Then the order statistics are <math>X_{(1)}, ..., X_{(n)}</math> where <math>X_{(i)}</math> represents the i'th smallest number.<br />
<br />
===Min and Max===<br />
The easiest to reason about are the minimum and maximum order statistics:<br />
<math>P(X_{(1)} <= x) = P(\text{min}(X_i) <= x) = 1 - P(X_1 > x, ..., X_n > x)</math><br />
<math>P(X_{(n)} <= x) = P(\text{max}(X_i) <= x) = P(X_1 <= x, ..., X_n <= x)</math><br />
<br />
===Joint PDF===<br />
If <math>X_i</math> has pdf <math>f</math>, the joint pdf of <math>X_{(1)}, ..., X_{(n)}</math> is:<br />
<math><br />
g(x_1, ...) = n!*f(x_1)*...*f(x_n)<br />
</math><br />
since there are n! ways perform a change of variables.<br />
<br />
===Individual PDF===<br />
<math><br />
f_{X(i)}(x) = \frac{n!}{(i-1)!(n-i)!} F(x)^{i-1} f(x) [1-F(x)]^{n-1}<br />
</math><br />
<br />
==Inequalities and Limit Theorems==<br />
===Markov's Inequality===<br />
Let <math>X</math> be a non-negative random variable.<br><br />
Then <math>P(X \geq a) \leq \frac{E(X)}{a}</math><br />
{{hidden | Proof | <br />
<math><br />
\begin{aligned}<br />
E(X) <br />
&= \int_{0}^{\infty}xf(x)dx \\<br />
&= \int_{0}^{a}xf(x)dx + \int_{a}^{\infty}xf(x)dx\\<br />
&\geq \int_{a}^{\infty}xf(x)dx\\<br />
&\geq \int_{a}^{\infty}af(x)dx\\<br />
&=a \int_{a}^{\infty}f(x)dx\\<br />
&=a * P(X \geq a)\\<br />
\implies& P(X \geq a) \leq \frac{E(X)}{a}<br />
\end{aligned}<br />
</math><br />
}}<br />
<br />
===Chebyshev's Inequality===<br />
* <math>P(|X - \mu| \geq k \sigma) \leq \frac{1}{k^2}</math><br />
* <math>P(|X - \mu| \geq k) \leq \frac{\sigma^2}{k^2}</math><br />
{{hidden | Proof | <br />
Apply Markov's inequality:<br><br />
Let <math>Y = |X - \mu|</math><br><br />
Then:<br><br />
<math><br />
\begin{aligned}<br />
P(|X - \mu| \geq k) &= P(Y \geq k) \\<br />
&= P(Y^2 \geq k^2) \\<br />
&\leq \frac{E(Y^2)}{k^2} \\<br />
&= \frac{E((X - \mu)^2)}{k^2}<br />
\end{aligned}<br />
</math><br />
}}<br />
* Usually used to prove convergence in probability<br />
<br />
===Central Limit Theorem===<br />
Very very important. Never forget this.<br><br />
For any distribution, the sample mean converges in distribution to normal.<br><br />
Let <math>\mu = E(x)</math> and <math>\sigma^2 = Var(x)</math><br><br />
Different ways of saying the same thing:<br />
* <math>\sqrt{n}(\bar{x} - \mu) \sim N(0, \sigma^2)</math><br />
* <math>\frac{\sqrt{n}}{\sigma}(\bar{x} - \mu) \sim N(0, 1)</math><br />
* <math>\bar{x} \sim N(\mu, \sigma^2/n)</math><br />
<br />
===Law of Large Numbers===<br />
The sample mean converges to the population mean in probability.<br><br />
For all <math>\epsilon > 0</math>,<br />
<math>\lim_{n \rightarrow \infty} P(|\bar{X}_n - E(X)| \geq \epsilon) = 0</math><br />
;Notes<br />
* The sample mean converges to the population mean almost surely.<br />
<br />
==Properties and Relationships between distributions==<br />
{{main | Wikipedia: Relationships among probability distributions}}<br />
;This is important for exams.<br />
<br />
===Poisson Distribution===<br />
* If <math>X_i \sim Poisson(\lambda_i)</math> then <math>\sum X_i \sim Poisson(\sum \lambda_i)</math><br />
<br />
===Normal Distribution===<br />
* If <math>X_1 \sim N(\mu_1, \sigma_1^2)</math> and <math>X_2 \sim N(\mu_2, \sigma_2^2)</math> then <math>\lambda_1 X_1 + \lambda_2 X_2 \sim N(\lambda_1 \mu_1 + \lambda_2 X_2, \lambda_1^2 \sigma_1^2 + \lambda_2^2 + \sigma_2^2)</math> for any <math>\lambda_1, \lambda_2 \in \mathbb{R}</math><br />
<br />
===Exponential Distribution===<br />
* <math>\operatorname{Exp}(\lambda)</math> is equivalent to <math>\Gamma(1, 1/\lambda)</math><br />
** Note that some conventions flip the second parameter of gamma, so it would be <math>\Gamma(1, \lambda)</math><br />
* If <math>\epsilon_1, ..., \epsilon_n</math> are exponential distributions then <math>\min\{\epsilon_i\} \sim \exp(\sum \lambda_i)</math><br />
* Note that the maximum is not exponentially distributed<br />
** However, if <math>X_1, ..., X_n \sim \exp(1)</math> then <math>Z_n=n\exp(\max\{\epsilon_i\}) \rightarrow \exp(1)</math><br />
<br />
===Gamma Distribution===<br />
Note exponential distributions are also Gamma distrubitions<br />
* If <math>X \sim \Gamma(k, \theta)</math> then <math>\lambda X \sim \Gamma(k, c\theta)</math>.<br><br />
* If <math>X_1 \sim \Gamma(k_1, \theta)</math> and <math>X_2 \sim \Gamma(k_2, \theta)</math> then <math>X_2 + X_2 \sim \Gamma(k_1 + k_2, \theta)</math>.<br />
* If <math>X_1 \sim \Gamma(\alpha, \theta)</math> and <math>X_2 \sim \Gamma(\beta, \theta)</math>, then <math>\frac{X_1}{X_1 + X_2} \sim B(\alpha, \beta)</math>.<br />
<br />
===T-distribution===<br />
* Ratio of standard normal and squared-root of Chi-sq distribution yields T-distribution.<br />
** If <math>Z \sim N(0,1)</math> and <math> V \sim \Chi^2(v)</math> then <math>\frac{Z}{\sqrt{V/v}} \sim \text{t-dist}(v)</math><br />
<br />
===Chi-Sq Distribution===<br />
* The ratio of two normalized Chi-sq is an F-distributions<br />
** If <math>X \sim \chi^2_{d1}</math> and <math>Y \sim \chi^2_{d2}</math> then <math>\frac{X/d1}{Y/d2} \sim F(d1,d2)</math><br />
* If <math>Z_1,...,Z_k \sim N(0,1)</math> then <math>Z_1^2 + ... + Z_k^2 \sim \Chi^2(k)</math><br />
* If <math>X_i \sim \Chi^2(k_i)</math> then <math>X_1 + ... + X_n \sim \Chi^2(k_1 +...+ k_n)</math><br />
* <math>\Chi^2(k)</math> is equivalent to <math>\Gamma(k/2, 2)</math><br />
<br />
===F Distribution===<br />
Too many to list. See [[Wikipedia: F-distribution]].<br />
<br />
Most important are Chi-sq and T distribution:<br />
* If <math>X \sim \chi^2_{d1}</math> and <math>Y \sim \chi^2_{d2}</math> then <math>\frac{X/d1}{Y/d2} \sim F(d1,d2)</math><br />
* If <math>X \sim t_{(n)}</math> then <math>X^2 \sim F(1, n)</math> and <math>X^{-2} \sim F(n, 1)</math><br />
<br />
==Textbooks==<br />
* [https://smile.amazon.com/dp/032179477X Sheldon Ross' A First Course in Probability]<br />
* [https://smile.amazon.com/dp/0321795431 Hogg and Craig's Mathematical Statistics]<br />
* [https://smile.amazon.com/dp/0534243126 Casella and Burger's Statistical Inference]</div>Davidhttps://wiki.davidl.me/index.php?title=Interview_Algorithms&diff=6940Interview Algorithms2024-02-19T00:18:42Z<p>David: /* Bit tricks */</p>
<hr />
<div>Insights from Leetcode problems.<br />
<br />
==Linear Searching==<br />
====Finding a cycle in a linked-list====<br />
Use two runners. <math>O(n)</math><br><br />
Runner 1 goes two steps per iteration.<br><br />
Runner 2 goes one step per iteration.<br><br />
If there is a cycle, runner 2 will lap runner 1 within 2 cycles.<br />
<br />
<br />
<br />
==Backtracking==<br />
====Permutations====<br />
Print all permutations of an array.<br><br />
The idea here is that you need a for-loop nested for each element of an array.<br><br />
So n elements means n nested for-loops. You use recursion to nest the loops.<br><br />
You can also think of this as a graph problem when you need to find every possible path with DFS.<br><br />
<br />
* [https://leetcode.com/problems/permutations/ Permutations]<br />
* [https://leetcode.com/problems/permutations-ii/ Permutations-ii]<br />
{{ hidden | Permute Brute-force solution |<br />
A more advanced solution would use backtracking, however it is time-consuming to implement for an interview.<br><br />
Here is a quick brute-force solution.<br />
* Enumerate all possible n^n numbers from 000 to 999 and then filter out number with duplicate digits<br />
<syntaxhighlight lang="cpp"><br />
class Solution {<br />
public:<br />
vector<vector<int>> permute(vector<int>& nums) {<br />
vector<vector<int>> ans;<br />
vector<int> indices(nums.size());<br />
permuteHelper(nums, indices, 0, ans);<br />
return ans;<br />
}<br />
<br />
bool isValid(vector<int>& indices) {<br />
vector<char> check(indices.size(), false);<br />
for (int i = 0; i < indices.size(); i++) {<br />
if (check[indices[i]]) {<br />
return false;<br />
}<br />
check[indices[i]] = true;<br />
}<br />
return true;<br />
}<br />
<br />
void permuteHelper(vector<int>& nums, vector<int>& indices,<br />
int col, vector<vector<int>>& ans) {<br />
if (col == nums.size()) {<br />
if (isValid(indices))<br />
print(nums, indices, ans);<br />
return;<br />
}<br />
for (int i = 0; i < nums.size(); i++) {<br />
indices[col] = i;<br />
permuteHelper(nums, indices, col+1, ans);<br />
}<br />
}<br />
<br />
void print(vector<int>& nums, vector<int>& indices, vector<vector<int>>& ans) {<br />
vector<int> new_nums(nums.size());<br />
for (int i = 0; i < nums.size(); i++) {<br />
new_nums[i] = nums[indices[i]];<br />
}<br />
ans.push_back(new_nums);<br />
}<br />
};<br />
</syntaxhighlight><br />
}}<br />
<br />
==Bit tricks==<br />
See https://www.geeksforgeeks.org/bit-tricks-competitive-programming/<br />
<br />
The most useful one is <br />
<pre><br />
n & n-1<br />
</pre><br />
which zeros the least significant set bit.<br />
E.g. this can be used to count the number of set bits.<br />
<br />
==Tricks==<br />
===Bitmask===<br />
<br />
===Counting===<br />
Counting as in tabulate not as in combinatorial counting.<br />
<br />
===Prefix Sum===<br />
<br />
==Data Structures==<br />
===Hashmap===<br />
Also known as a dictionary or associative array. Theses are used everywhere.<br />
<br />
===Segment Trees===<br />
See [https://cp-algorithms.com/data_structures/segment_tree.html CP Algorithms segment tree]<br />
<br />
==Misc Tricks==<br />
<br />
<br />
====Finding duplicates in an array====<br />
If you have an array of ints where each number appears <math>n</math> times and one number appears <math>m>n</math> times where <math>gcd(n,m)==1</math>, <br />
then you count the number of times each bit appears and take it mod <math>n</math>.<br><br />
The remaining bits will remain <math>m \mod n</math> times.<br><br />
* [https://leetcode.com/problems/single-number/ single-number]<br />
* [https://leetcode.com/problems/single-number-ii/ single-number-ii]<br />
* [https://leetcode.com/problems/single-number-iii/ single-number-iii]</div>Davidhttps://wiki.davidl.me/index.php?title=Interview_Algorithms&diff=6939Interview Algorithms2024-02-19T00:18:22Z<p>David: /* Bit tricks */</p>
<hr />
<div>Insights from Leetcode problems.<br />
<br />
==Linear Searching==<br />
====Finding a cycle in a linked-list====<br />
Use two runners. <math>O(n)</math><br><br />
Runner 1 goes two steps per iteration.<br><br />
Runner 2 goes one step per iteration.<br><br />
If there is a cycle, runner 2 will lap runner 1 within 2 cycles.<br />
<br />
<br />
<br />
==Backtracking==<br />
====Permutations====<br />
Print all permutations of an array.<br><br />
The idea here is that you need a for-loop nested for each element of an array.<br><br />
So n elements means n nested for-loops. You use recursion to nest the loops.<br><br />
You can also think of this as a graph problem when you need to find every possible path with DFS.<br><br />
<br />
* [https://leetcode.com/problems/permutations/ Permutations]<br />
* [https://leetcode.com/problems/permutations-ii/ Permutations-ii]<br />
{{ hidden | Permute Brute-force solution |<br />
A more advanced solution would use backtracking, however it is time-consuming to implement for an interview.<br><br />
Here is a quick brute-force solution.<br />
* Enumerate all possible n^n numbers from 000 to 999 and then filter out number with duplicate digits<br />
<syntaxhighlight lang="cpp"><br />
class Solution {<br />
public:<br />
vector<vector<int>> permute(vector<int>& nums) {<br />
vector<vector<int>> ans;<br />
vector<int> indices(nums.size());<br />
permuteHelper(nums, indices, 0, ans);<br />
return ans;<br />
}<br />
<br />
bool isValid(vector<int>& indices) {<br />
vector<char> check(indices.size(), false);<br />
for (int i = 0; i < indices.size(); i++) {<br />
if (check[indices[i]]) {<br />
return false;<br />
}<br />
check[indices[i]] = true;<br />
}<br />
return true;<br />
}<br />
<br />
void permuteHelper(vector<int>& nums, vector<int>& indices,<br />
int col, vector<vector<int>>& ans) {<br />
if (col == nums.size()) {<br />
if (isValid(indices))<br />
print(nums, indices, ans);<br />
return;<br />
}<br />
for (int i = 0; i < nums.size(); i++) {<br />
indices[col] = i;<br />
permuteHelper(nums, indices, col+1, ans);<br />
}<br />
}<br />
<br />
void print(vector<int>& nums, vector<int>& indices, vector<vector<int>>& ans) {<br />
vector<int> new_nums(nums.size());<br />
for (int i = 0; i < nums.size(); i++) {<br />
new_nums[i] = nums[indices[i]];<br />
}<br />
ans.push_back(new_nums);<br />
}<br />
};<br />
</syntaxhighlight><br />
}}<br />
<br />
==Bit tricks==<br />
See https://www.geeksforgeeks.org/bit-tricks-competitive-programming/<br />
<br />
The most useful one is <br />
<pre><br />
n & n-1<br />
</pre><br />
which zeros the least significant set bit.<br />
<br />
==Tricks==<br />
===Bitmask===<br />
<br />
===Counting===<br />
Counting as in tabulate not as in combinatorial counting.<br />
<br />
===Prefix Sum===<br />
<br />
==Data Structures==<br />
===Hashmap===<br />
Also known as a dictionary or associative array. Theses are used everywhere.<br />
<br />
===Segment Trees===<br />
See [https://cp-algorithms.com/data_structures/segment_tree.html CP Algorithms segment tree]<br />
<br />
==Misc Tricks==<br />
<br />
<br />
====Finding duplicates in an array====<br />
If you have an array of ints where each number appears <math>n</math> times and one number appears <math>m>n</math> times where <math>gcd(n,m)==1</math>, <br />
then you count the number of times each bit appears and take it mod <math>n</math>.<br><br />
The remaining bits will remain <math>m \mod n</math> times.<br><br />
* [https://leetcode.com/problems/single-number/ single-number]<br />
* [https://leetcode.com/problems/single-number-ii/ single-number-ii]<br />
* [https://leetcode.com/problems/single-number-iii/ single-number-iii]</div>Davidhttps://wiki.davidl.me/index.php?title=Interview_Algorithms&diff=6938Interview Algorithms2024-02-19T00:17:09Z<p>David: /* Tricks */</p>
<hr />
<div>Insights from Leetcode problems.<br />
<br />
==Linear Searching==<br />
====Finding a cycle in a linked-list====<br />
Use two runners. <math>O(n)</math><br><br />
Runner 1 goes two steps per iteration.<br><br />
Runner 2 goes one step per iteration.<br><br />
If there is a cycle, runner 2 will lap runner 1 within 2 cycles.<br />
<br />
<br />
<br />
==Backtracking==<br />
====Permutations====<br />
Print all permutations of an array.<br><br />
The idea here is that you need a for-loop nested for each element of an array.<br><br />
So n elements means n nested for-loops. You use recursion to nest the loops.<br><br />
You can also think of this as a graph problem when you need to find every possible path with DFS.<br><br />
<br />
* [https://leetcode.com/problems/permutations/ Permutations]<br />
* [https://leetcode.com/problems/permutations-ii/ Permutations-ii]<br />
{{ hidden | Permute Brute-force solution |<br />
A more advanced solution would use backtracking, however it is time-consuming to implement for an interview.<br><br />
Here is a quick brute-force solution.<br />
* Enumerate all possible n^n numbers from 000 to 999 and then filter out number with duplicate digits<br />
<syntaxhighlight lang="cpp"><br />
class Solution {<br />
public:<br />
vector<vector<int>> permute(vector<int>& nums) {<br />
vector<vector<int>> ans;<br />
vector<int> indices(nums.size());<br />
permuteHelper(nums, indices, 0, ans);<br />
return ans;<br />
}<br />
<br />
bool isValid(vector<int>& indices) {<br />
vector<char> check(indices.size(), false);<br />
for (int i = 0; i < indices.size(); i++) {<br />
if (check[indices[i]]) {<br />
return false;<br />
}<br />
check[indices[i]] = true;<br />
}<br />
return true;<br />
}<br />
<br />
void permuteHelper(vector<int>& nums, vector<int>& indices,<br />
int col, vector<vector<int>>& ans) {<br />
if (col == nums.size()) {<br />
if (isValid(indices))<br />
print(nums, indices, ans);<br />
return;<br />
}<br />
for (int i = 0; i < nums.size(); i++) {<br />
indices[col] = i;<br />
permuteHelper(nums, indices, col+1, ans);<br />
}<br />
}<br />
<br />
void print(vector<int>& nums, vector<int>& indices, vector<vector<int>>& ans) {<br />
vector<int> new_nums(nums.size());<br />
for (int i = 0; i < nums.size(); i++) {<br />
new_nums[i] = nums[indices[i]];<br />
}<br />
ans.push_back(new_nums);<br />
}<br />
};<br />
</syntaxhighlight><br />
}}<br />
<br />
==Bit tricks==<br />
See https://www.geeksforgeeks.org/bit-tricks-competitive-programming/<br />
<br />
<br />
==Tricks==<br />
===Bitmask===<br />
<br />
===Counting===<br />
Counting as in tabulate not as in combinatorial counting.<br />
<br />
===Prefix Sum===<br />
<br />
==Data Structures==<br />
===Hashmap===<br />
Also known as a dictionary or associative array. Theses are used everywhere.<br />
<br />
===Segment Trees===<br />
See [https://cp-algorithms.com/data_structures/segment_tree.html CP Algorithms segment tree]<br />
<br />
==Misc Tricks==<br />
<br />
<br />
====Finding duplicates in an array====<br />
If you have an array of ints where each number appears <math>n</math> times and one number appears <math>m>n</math> times where <math>gcd(n,m)==1</math>, <br />
then you count the number of times each bit appears and take it mod <math>n</math>.<br><br />
The remaining bits will remain <math>m \mod n</math> times.<br><br />
* [https://leetcode.com/problems/single-number/ single-number]<br />
* [https://leetcode.com/problems/single-number-ii/ single-number-ii]<br />
* [https://leetcode.com/problems/single-number-iii/ single-number-iii]</div>Davidhttps://wiki.davidl.me/index.php?title=JSON&diff=6937JSON2024-02-12T18:40:30Z<p>David: /* See Also */</p>
<hr />
<div><br />
<br />
==JQ==<br />
https://jqlang.github.io/jq/<br />
<br />
==See also==<br />
* [[YAML]]</div>Davidhttps://wiki.davidl.me/index.php?title=YAML&diff=6936YAML2024-02-12T18:40:23Z<p>David: </p>
<hr />
<div>==YQ==<br />
https://mikefarah.gitbook.io/yq/<br />
<br />
==See also==<br />
* [[JSON]]</div>Davidhttps://wiki.davidl.me/index.php?title=YAML&diff=6935YAML2024-02-12T18:39:37Z<p>David: Created page with "==YQ== https://mikefarah.gitbook.io/yq/"</p>
<hr />
<div>==YQ==<br />
https://mikefarah.gitbook.io/yq/</div>Davidhttps://wiki.davidl.me/index.php?title=JSON&diff=6934JSON2024-02-12T18:39:04Z<p>David: Created page with " ==JQ== https://jqlang.github.io/jq/ ==See Also== * YAML"</p>
<hr />
<div><br />
<br />
==JQ==<br />
https://jqlang.github.io/jq/<br />
<br />
==See Also==<br />
* [[YAML]]</div>Davidhttps://wiki.davidl.me/index.php?title=Serialization&diff=6933Serialization2024-02-12T18:38:34Z<p>David: /* Text-based */</p>
<hr />
<div>Serialization - different ways of storing data.<br />
<br />
==Text-based==<br />
Encode data as strings. <br />
Pros are that it's human readable and widely supported. You can dump JSON without third-party libraries in most languages. <br />
Cons are that it takes up much more space/bandwidth and that binary data must first be converted into base64 which can be slow.<br />
<br />
* XML<br />
* [[JSON]]<br />
* [[YAML]] - a superset of JSON which uses spaces and is a bit easier to read<br />
<br />
==Binary==<br />
* [[Protocol Buffers]], also known as ProtoBuf, is a popular serialization library by Google.<br />
* [https://google.github.io/flatbuffers/ flatbuffers] is another serialization library by Google meant for high performance.<br />
* [https://capnproto.org/ Cap'n Proto], a zero-encoding serialization library by a former ProtoBuf author.</div>Davidhttps://wiki.davidl.me/index.php?title=SQL&diff=6932SQL2024-02-12T01:43:35Z<p>David: </p>
<hr />
<div>SQL basics<br />
<br />
==Common functions==<br />
===Math functions===<br />
See [https://www.postgresql.org/docs/16/functions-math.html Postgres math functions]<br />
* Average<br />
* Sum<br />
* Round<br />
===Conditional functions===<br />
See [https://www.postgresql.org/docs/current/functions-conditional.html Postgres conditional functions].<br />
* [https://www.postgresql.org/docs/current/functions-conditional.html#FUNCTIONS-COALESCE-NVL-IFNULL Coalesce] - return the first non-null parameter.<br />
* [https://www.postgresql.org/docs/current/functions-conditional.html#FUNCTIONS-CASE Case]<br />
<br />
==Joins==<br />
Joins merge two tables into a single table. You can think of this like an outer product, applying some conditions to subset from every possible combination of rows from the two tables.<br />
<br />
* Inner join - creates rows only if keys match between the rows<br />
* Left join - keep all rows from the left table<br />
* Right join - keep all rows from the right table<br />
* Outer join - keep rows from both tables.<br />
<br />
==Subqueries==</div>Davidhttps://wiki.davidl.me/index.php?title=SQL&diff=6931SQL2024-02-12T01:43:22Z<p>David: /* Common functions */</p>
<hr />
<div>SQL basics<br />
<br />
<br />
==Common functions==<br />
===Math functions===<br />
See [https://www.postgresql.org/docs/16/functions-math.html Postgres math functions]<br />
* Average<br />
* Sum<br />
* Round<br />
===Conditional functions===<br />
See [https://www.postgresql.org/docs/current/functions-conditional.html Postgres conditional functions].<br />
* [https://www.postgresql.org/docs/current/functions-conditional.html#FUNCTIONS-COALESCE-NVL-IFNULL Coalesce] - return the first non-null parameter.<br />
* [https://www.postgresql.org/docs/current/functions-conditional.html#FUNCTIONS-CASE Case]<br />
<br />
==Joins==<br />
Joins merge two tables into a single table. You can think of this like an outer product, applying some conditions to subset from every possible combination of rows from the two tables.<br />
<br />
* Inner join - creates rows only if keys match between the rows<br />
* Left join - keep all rows from the left table<br />
* Right join - keep all rows from the right table<br />
* Outer join - keep rows from both tables.<br />
<br />
==Subqueries==</div>Davidhttps://wiki.davidl.me/index.php?title=SQL&diff=6930SQL2024-02-12T01:42:53Z<p>David: Created page with "SQL basics ==Common functions== See [https://www.postgresql.org/docs/16/functions-math.html Postgres math functions] and [https://www.postgresql.org/docs/current/functions-conditional.html Postgres conditional functions]. * Average * Sum * Round * [https://www.postgresql.org/docs/current/functions-conditional.html#FUNCTIONS-COALESCE-NVL-IFNULL Coalesce] - return the first non-null parameter. * [https://www.postgresql.org/docs/current/functions-conditional.html#FUNCTIO..."</p>
<hr />
<div>SQL basics<br />
<br />
<br />
==Common functions==<br />
See [https://www.postgresql.org/docs/16/functions-math.html Postgres math functions] and [https://www.postgresql.org/docs/current/functions-conditional.html Postgres conditional functions].<br />
<br />
* Average<br />
* Sum<br />
* Round<br />
* [https://www.postgresql.org/docs/current/functions-conditional.html#FUNCTIONS-COALESCE-NVL-IFNULL Coalesce] - return the first non-null parameter.<br />
* [https://www.postgresql.org/docs/current/functions-conditional.html#FUNCTIONS-CASE Case]<br />
<br />
==Joins==<br />
Joins merge two tables into a single table. You can think of this like an outer product, applying some conditions to subset from every possible combination of rows from the two tables.<br />
<br />
* Inner join - creates rows only if keys match between the rows<br />
* Left join - keep all rows from the left table<br />
* Right join - keep all rows from the right table<br />
* Outer join - keep rows from both tables.<br />
<br />
==Subqueries==</div>Davidhttps://wiki.davidl.me/index.php?title=File_Systems&diff=6929File Systems2024-02-09T21:57:11Z<p>David: /* Databases */</p>
<hr />
<div>There are several common ways to store binary information:<br />
* Database or key-value store (e.g. PostgreSQL, SQLite) - Good for small files or a finite amount of files which fit within the confines of a database.<br />
* Object store (e.g. S3) - same as a key-value store but typically designed to scale lots of files across multiple HDDs and hosts.<br />
* File systems (e.g. EXT4) - good for files where certain operations benefit from a hierarchical data structure, e.g. list, delete. File systems typically come with metadata such as permissions and owners.<br />
* Block storage - you get raw disk access but need to layout your binary data manually and in fixed block sizes.<br />
<br />
==Standard File Systems==<br />
* BTRFS<br />
* [[ZFS]]<br />
* EXT4<br />
* XFS<br />
* NTFS<br />
<br />
==Overlay File Systems==<br />
* [[MergerFS]] - a union file system to combine multiple folders on a single computer.<br />
<br />
==Block Overlays==<br />
The create a view of one or more block storage, typically using one or more block storage.<br />
* [[LUKS]] - encrypts a partition<br />
* [[LVM]] - joins multiple blocks into a pool from which to allocate blocks<br />
* [[mdraid]]<br />
<br />
==Object Stores==<br />
* Minio - S3-compatible object store<br />
* Ceph - joins drives across multiple computers. Has block, file, and object storage APIs.<br />
* Rook - deployment of Ceph using Kubernetes<br />
* SeaweedFS - joins drives across multiple computers to object storage APIs (incl. S3). Has file storage when paired with a database using the SeaweedFS Filer.<br />
<br />
==Distributed File Systems==<br />
* GlusterFS - joins filesystem directories across multiple computers<br />
* Ceph - joins drives across multiple computers. Has block, file, and object storage APIs.<br />
* JuiceFS - creates a POSIX-compatable file storage using an S3 object storage and metadata database.<br />
<br />
==Databases==<br />
===SQL===<br />
* PostgreSQL<br />
* MySQL<br />
* SQLite<br />
===NoSQL===<br />
* MongoDB</div>Davidhttps://wiki.davidl.me/index.php?title=File_Systems&diff=6928File Systems2024-02-09T21:56:54Z<p>David: /* Databases */</p>
<hr />
<div>There are several common ways to store binary information:<br />
* Database or key-value store (e.g. PostgreSQL, SQLite) - Good for small files or a finite amount of files which fit within the confines of a database.<br />
* Object store (e.g. S3) - same as a key-value store but typically designed to scale lots of files across multiple HDDs and hosts.<br />
* File systems (e.g. EXT4) - good for files where certain operations benefit from a hierarchical data structure, e.g. list, delete. File systems typically come with metadata such as permissions and owners.<br />
* Block storage - you get raw disk access but need to layout your binary data manually and in fixed block sizes.<br />
<br />
==Standard File Systems==<br />
* BTRFS<br />
* [[ZFS]]<br />
* EXT4<br />
* XFS<br />
* NTFS<br />
<br />
==Overlay File Systems==<br />
* [[MergerFS]] - a union file system to combine multiple folders on a single computer.<br />
<br />
==Block Overlays==<br />
The create a view of one or more block storage, typically using one or more block storage.<br />
* [[LUKS]] - encrypts a partition<br />
* [[LVM]] - joins multiple blocks into a pool from which to allocate blocks<br />
* [[mdraid]]<br />
<br />
==Object Stores==<br />
* Minio - S3-compatible object store<br />
* Ceph - joins drives across multiple computers. Has block, file, and object storage APIs.<br />
* Rook - deployment of Ceph using Kubernetes<br />
* SeaweedFS - joins drives across multiple computers to object storage APIs (incl. S3). Has file storage when paired with a database using the SeaweedFS Filer.<br />
<br />
==Distributed File Systems==<br />
* GlusterFS - joins filesystem directories across multiple computers<br />
* Ceph - joins drives across multiple computers. Has block, file, and object storage APIs.<br />
* JuiceFS - creates a POSIX-compatable file storage using an S3 object storage and metadata database.<br />
<br />
==Databases==<br />
;SQL<br />
* PostgreSQL<br />
* MySQL<br />
* SQLite<br />
;NoSQL<br />
* MongoDB</div>Davidhttps://wiki.davidl.me/index.php?title=File_Systems&diff=6927File Systems2024-02-09T21:56:07Z<p>David: /* Distributed File Systems and Object Stores */</p>
<hr />
<div>There are several common ways to store binary information:<br />
* Database or key-value store (e.g. PostgreSQL, SQLite) - Good for small files or a finite amount of files which fit within the confines of a database.<br />
* Object store (e.g. S3) - same as a key-value store but typically designed to scale lots of files across multiple HDDs and hosts.<br />
* File systems (e.g. EXT4) - good for files where certain operations benefit from a hierarchical data structure, e.g. list, delete. File systems typically come with metadata such as permissions and owners.<br />
* Block storage - you get raw disk access but need to layout your binary data manually and in fixed block sizes.<br />
<br />
==Standard File Systems==<br />
* BTRFS<br />
* [[ZFS]]<br />
* EXT4<br />
* XFS<br />
* NTFS<br />
<br />
==Overlay File Systems==<br />
* [[MergerFS]] - a union file system to combine multiple folders on a single computer.<br />
<br />
==Block Overlays==<br />
The create a view of one or more block storage, typically using one or more block storage.<br />
* [[LUKS]] - encrypts a partition<br />
* [[LVM]] - joins multiple blocks into a pool from which to allocate blocks<br />
* [[mdraid]]<br />
<br />
==Object Stores==<br />
* Minio - S3-compatible object store<br />
* Ceph - joins drives across multiple computers. Has block, file, and object storage APIs.<br />
* Rook - deployment of Ceph using Kubernetes<br />
* SeaweedFS - joins drives across multiple computers to object storage APIs (incl. S3). Has file storage when paired with a database using the SeaweedFS Filer.<br />
<br />
==Distributed File Systems==<br />
* GlusterFS - joins filesystem directories across multiple computers<br />
* Ceph - joins drives across multiple computers. Has block, file, and object storage APIs.<br />
* JuiceFS - creates a POSIX-compatable file storage using an S3 object storage and metadata database.<br />
<br />
==Databases==<br />
* PostgreSQL<br />
* MySQL<br />
* SQLite</div>Davidhttps://wiki.davidl.me/index.php?title=File_Systems&diff=6926File Systems2024-02-09T21:54:41Z<p>David: /* Distributed File Systems and Object Stores */</p>
<hr />
<div>There are several common ways to store binary information:<br />
* Database or key-value store (e.g. PostgreSQL, SQLite) - Good for small files or a finite amount of files which fit within the confines of a database.<br />
* Object store (e.g. S3) - same as a key-value store but typically designed to scale lots of files across multiple HDDs and hosts.<br />
* File systems (e.g. EXT4) - good for files where certain operations benefit from a hierarchical data structure, e.g. list, delete. File systems typically come with metadata such as permissions and owners.<br />
* Block storage - you get raw disk access but need to layout your binary data manually and in fixed block sizes.<br />
<br />
==Standard File Systems==<br />
* BTRFS<br />
* [[ZFS]]<br />
* EXT4<br />
* XFS<br />
* NTFS<br />
<br />
==Overlay File Systems==<br />
* [[MergerFS]] - a union file system to combine multiple folders on a single computer.<br />
<br />
==Block Overlays==<br />
The create a view of one or more block storage, typically using one or more block storage.<br />
* [[LUKS]] - encrypts a partition<br />
* [[LVM]] - joins multiple blocks into a pool from which to allocate blocks<br />
* [[mdraid]]<br />
<br />
==Distributed File Systems and Object Stores==<br />
* GlusterFS - joins filesystem directories across multiple computers<br />
* Ceph - joins drives across multiple computers. Has block, file, and object storage APIs.<br />
* SeaweedFS - joins drives across multiple computers to object storage APIs (incl. S3). Has file storage when paired with a database using the SeaweedFS Filer.<br />
* JuiceFS - creates a POSIX-compatable file storage using an S3 object storage and metadata database.<br />
* Rook - deployment of Ceph using Kubernetes<br />
* Minio - S3-compatible object store<br />
<br />
==Databases==<br />
* PostgreSQL<br />
* MySQL<br />
* SQLite</div>Davidhttps://wiki.davidl.me/index.php?title=File_Systems&diff=6925File Systems2024-02-09T21:53:06Z<p>David: </p>
<hr />
<div>There are several common ways to store binary information:<br />
* Database or key-value store (e.g. PostgreSQL, SQLite) - Good for small files or a finite amount of files which fit within the confines of a database.<br />
* Object store (e.g. S3) - same as a key-value store but typically designed to scale lots of files across multiple HDDs and hosts.<br />
* File systems (e.g. EXT4) - good for files where certain operations benefit from a hierarchical data structure, e.g. list, delete. File systems typically come with metadata such as permissions and owners.<br />
* Block storage - you get raw disk access but need to layout your binary data manually and in fixed block sizes.<br />
<br />
==Standard File Systems==<br />
* BTRFS<br />
* [[ZFS]]<br />
* EXT4<br />
* XFS<br />
* NTFS<br />
<br />
==Overlay File Systems==<br />
* [[MergerFS]] - a union file system to combine multiple folders on a single computer.<br />
<br />
==Block Overlays==<br />
The create a view of one or more block storage, typically using one or more block storage.<br />
* [[LUKS]] - encrypts a partition<br />
* [[LVM]] - joins multiple blocks into a pool from which to allocate blocks<br />
* [[mdraid]]<br />
<br />
==Distributed File Systems and Object Stores==<br />
* GlusterFS - joins filesystem directories across multiple computers<br />
* Ceph - joins drives across multiple computers. Has block, file, and object storage APIs.<br />
* SeaweedFS - joins drives across multiple computers. Has file (with filer extension) and object storage APIs.<br />
* JuiceFS - creates a POSIX-compatable file storage using an S3 object storage and metadata database.<br />
* Rook - deployment of Ceph using Kubernetes<br />
* Minio - S3-compatible object store<br />
<br />
==Databases==<br />
* PostgreSQL<br />
* MySQL<br />
* SQLite</div>Davidhttps://wiki.davidl.me/index.php?title=File_Systems&diff=6924File Systems2024-02-09T21:51:49Z<p>David: /* Block Overlays */</p>
<hr />
<div>There are several common ways to store binary information:<br />
* Database or key-value store (e.g. PostgreSQL, SQLite) - Good for small files or a finite amount of files which fit within the confines of a database.<br />
* Object store (e.g. S3) - same as a key-value store but typically designed to scale lots of files across multiple HDDs and hosts.<br />
* File systems (e.g. EXT4) - good for files where certain operations benefit from a hierarchical data structure, e.g. list, delete. File systems typically come with metadata such as permissions and owners.<br />
* Block storage - you get raw disk access but need to layout your binary data manually and in fixed block sizes.<br />
<br />
==Standard File Systems==<br />
* BTRFS<br />
* [[ZFS]]<br />
* EXT4<br />
* XFS<br />
* NTFS<br />
<br />
==Overlay File Systems==<br />
* [[MergerFS]] - a union file system to combine multiple folders on a single computer.<br />
<br />
==Block Overlays==<br />
The create a view of one or more block storage, typically using one or more block storage.<br />
* [[LUKS]] - encrypts a partition<br />
* [[LVM]] - joins multiple blocks into a pool from which to allocate blocks<br />
* [[mdraid]]<br />
<br />
==Distributed File Systems==<br />
* GlusterFS - joins filesystem directories across multiple computers<br />
* Ceph - joins drives across multiple computers. Has block, file, and object storage APIs.<br />
* SeaweedFS - joins drives across multiple computers. Has file (with filer extension) and object storage APIs.<br />
* JuiceFS - creates a POSIX-compatable file storage using an S3 object storage and metadata database.<br />
* Rook - deployment of Ceph using Kubernetes<br />
<br />
==Databases==<br />
* PostgreSQL<br />
* MySQL<br />
* SQLite</div>Davidhttps://wiki.davidl.me/index.php?title=File_Systems&diff=6923File Systems2024-02-09T21:50:25Z<p>David: </p>
<hr />
<div>There are several common ways to store binary information:<br />
* Database or key-value store (e.g. PostgreSQL, SQLite) - Good for small files or a finite amount of files which fit within the confines of a database.<br />
* Object store (e.g. S3) - same as a key-value store but typically designed to scale lots of files across multiple HDDs and hosts.<br />
* File systems (e.g. EXT4) - good for files where certain operations benefit from a hierarchical data structure, e.g. list, delete. File systems typically come with metadata such as permissions and owners.<br />
* Block storage - you get raw disk access but need to layout your binary data manually and in fixed block sizes.<br />
<br />
==Standard File Systems==<br />
* BTRFS<br />
* [[ZFS]]<br />
* EXT4<br />
* XFS<br />
* NTFS<br />
<br />
==Overlay File Systems==<br />
* [[MergerFS]] - a union file system to combine multiple folders on a single computer.<br />
<br />
==Block Overlays==<br />
* [[LUKS]] - encrypts a partition<br />
* [[LVM]] - joins multiple blocks into a pool from which to allocate blocks<br />
* [[mdraid]]<br />
<br />
==Distributed File Systems==<br />
* GlusterFS - joins filesystem directories across multiple computers<br />
* Ceph - joins drives across multiple computers. Has block, file, and object storage APIs.<br />
* SeaweedFS - joins drives across multiple computers. Has file (with filer extension) and object storage APIs.<br />
* JuiceFS - creates a POSIX-compatable file storage using an S3 object storage and metadata database.<br />
* Rook - deployment of Ceph using Kubernetes<br />
<br />
==Databases==<br />
* PostgreSQL<br />
* MySQL<br />
* SQLite</div>Davidhttps://wiki.davidl.me/index.php?title=File_Systems&diff=6922File Systems2024-02-09T21:43:12Z<p>David: /* Distributed File Systems */</p>
<hr />
<div>List of file systems<br />
<br />
==Standard File Systems==<br />
* BTRFS<br />
* [[ZFS]]<br />
* EXT4<br />
* XFS<br />
* NTFS<br />
<br />
==Overlay File Systems==<br />
* [[MergerFS]] - a union file system to combine multiple folders on a single computer.<br />
<br />
==Block Overlays==<br />
* [[LUKS]] - encrypts a partition<br />
* [[LVM]] - joins multiple blocks into a pool from which to allocate blocks<br />
* [[mdraid]]<br />
<br />
==Distributed File Systems==<br />
* GlusterFS - joins filesystem directories across multiple computers<br />
* Ceph - joins drives across multiple computers. Has block, file, and object storage APIs.<br />
* SeaweedFS - joins drives across multiple computers. Has file (with filer extension) and object storage APIs.<br />
* JuiceFS - creates a POSIX-compatable file storage using an S3 object storage and metadata database.<br />
* Rook - deployment of Ceph using Kubernetes</div>Davidhttps://wiki.davidl.me/index.php?title=File_Systems&diff=6921File Systems2024-02-08T20:08:45Z<p>David: </p>
<hr />
<div>List of file systems<br />
<br />
==Standard File Systems==<br />
* BTRFS<br />
* [[ZFS]]<br />
* EXT4<br />
* XFS<br />
* NTFS<br />
<br />
==Overlay File Systems==<br />
* [[MergerFS]] - a union file system to combine multiple folders on a single computer.<br />
<br />
==Block Overlays==<br />
* [[LUKS]] - encrypts a partition<br />
* [[LVM]] - joins multiple blocks into a pool from which to allocate blocks<br />
* [[mdraid]]<br />
<br />
==Distributed File Systems==<br />
* GlusterFS - joins filesystem directories across multiple computers<br />
* Ceph - joins drives across multiple computers. Has block, file, and object storage APIs.<br />
* SeaweedFS - joins drives across multiple computers. Has file (with filer extension) and object storage APIs.<br />
* JuiceFS - creates a POSIX-compatable file storage using a object storage and metadata database.<br />
* Rook - deployment of Ceph using Kubernetes</div>Davidhttps://wiki.davidl.me/index.php?title=File_Systems&diff=6920File Systems2024-02-08T20:08:21Z<p>David: /* Distributed File Systems */</p>
<hr />
<div>List of file systems<br />
<br />
<br />
==Standard File Systems==<br />
* BTRFS<br />
* [[ZFS]]<br />
* EXT4<br />
* XFS<br />
* NTFS<br />
<br />
==Overlay File Systems==<br />
* [[MergerFS]] - a union file system to combine multiple folders on a single computer.<br />
<br />
==Block Overlays==<br />
* [[LUKS]] - encrypts a partition<br />
* [[LVM]] - joins multiple blocks into a pool from which to allocate blocks<br />
* [[mdraid]]<br />
<br />
==Distributed File Systems==<br />
* GlusterFS - joins directories across multiple computers<br />
* Ceph - joins drives across multiple computers. Has block, file, and object storage APIs.<br />
* SeaweedFS - joins drives across multiple computers. Has file (with filer extension) and object storage APIs.<br />
* JuiceFS - creates a POSIX-compatable file storage using a object storage and metadata database.<br />
* Rook - deployment of Ceph using Kubernetes</div>Davidhttps://wiki.davidl.me/index.php?title=File_Systems&diff=6919File Systems2024-02-08T20:07:53Z<p>David: Created page with "List of file systems ==Standard File Systems== * BTRFS * ZFS * EXT4 * XFS * NTFS ==Overlay File Systems== * MergerFS - a union file system to combine multiple folders on a single computer. ==Block Overlays== * LUKS - encrypts a partition * LVM - joins multiple blocks into a pool from which to allocate blocks * mdraid ==Distributed File Systems== * GlusterFS - joins directories across multiple computers * CephFS - joins drives across multiple comp..."</p>
<hr />
<div>List of file systems<br />
<br />
<br />
==Standard File Systems==<br />
* BTRFS<br />
* [[ZFS]]<br />
* EXT4<br />
* XFS<br />
* NTFS<br />
<br />
==Overlay File Systems==<br />
* [[MergerFS]] - a union file system to combine multiple folders on a single computer.<br />
<br />
==Block Overlays==<br />
* [[LUKS]] - encrypts a partition<br />
* [[LVM]] - joins multiple blocks into a pool from which to allocate blocks<br />
* [[mdraid]]<br />
<br />
==Distributed File Systems==<br />
* GlusterFS - joins directories across multiple computers<br />
* CephFS - joins drives across multiple computers. Has block, file, and object storage APIs.<br />
* SeaweedFS - joins drives across multiple computers. Has file (with filer extension) and object storage APIs.<br />
* JuiceFS - creates a POSIX-compatable file storage using a object storage and metadata database.</div>David