c0deb0t

PTHash and other minimum perfect hash functions return an arbitrary value if the query key did not exist when building the MPHF, so they can be a lot smaller. B-field can identify query keys that don't exist in the set (with high probability?).

What I'm wondering is why the Kraken2 probabilistic hash table doesn't work. It uses 32 bits per element in an open addressing hash table. For 1 billion k-mers and 19 bits for the value, 32 - 19 = 13 bits of the key hash can be stored alongside the value, helping disambiguate hash collisions. If the load factor is 1.25x, then that's 4 * 10^9 * 1.25 = 5GB total, better than ~7GB. Also, this is only one cache miss (+ linear probing that can be SIMD accelerated) per lookup.

Adversarial attacks is a super interesting field, but unfortunately I feel that a lot of papers are just incremental attack or defense improvements like a cat-and-mouse game. I originally did some research on 3D point cloud attacks, but later stopped because making super successful attacks (eg., attacks with higher success rates than all the previous techniques for some very specific task) don't really help us understand that much more about neural nets, its just optimizing a metric for publishing papers. This kind of research is quite common, even at top conferences.

Despite this, recently, we made a 1 minute explainer video introducing adversarial attacks on neural nets as a submission for the Veritasium contest: https://youtu.be/hNuhdf-fL_g Give it a watch!

Yes, this will uwuify your text at high speeds. It reached 2.3 GB/s on my 8-core macbook pro, while uwu-ing the first 1 GB of english Wikipedia. This Rust command-line tool takes advantage of SSE4.1 SIMD vectorization and multithreading (exploit all your CPU cores for this!) to be almost as fast as simply copying a file. Installing it is simply cargo install uwuify, assuming you already have Rust installed. It is on crate.io too: https://crates.io/crates/uwuify

In case you don't know what uwu'd text looks like, here's an example:

hey... i think i w-weawwy wuv you. (⑅˘꒳˘) d-do you want a headpat?

Yes, this will uwuify your text at high speeds. It reached 2.3 GB/s on my 8-core macbook pro, while uwu-ing the first 1 GB of english Wikipedia. This Rust command-line tool takes advantage of SSE4.1 SIMD vectorization and multithreading to be almost as fast as simply copying a file. Installing it is simply cargo install uwuify, assuming you already have Rust installed. It is on crate.io: https://crates.io/crates/uwuify

For binary trees, indexing can be done by saving the subtree size of each node and doing a sort of binary search. Not sure if this is fast for B-trees that have more than 2 children nodes, though.

I'm a high school student that is quite new to Rust, and I am liking it so far. I learned a lot from this project and I hope that it can be a good learning resource for others.

In addition to this, I am also working on a SIMD edit distance library in Rust.

Since I am storing the entire DP matrix as diagonal vectors that are flattened, I don't think there will be many cache misses. Each diagonal only depends on its previous two diagonals, and each diagonal is stored contiguously in memory.

The problem with handling diagonals is that indexing cells and comparing characters on the diagonal becomes complex. Dealing with this without many branches (less branch mispredictions) is the hard part.

I took a look at the code, and read the paper. It seems that they directly calculate the entire 2D DP array, but use SIMD to allow each cell to contain multiple values, one for each query string. My approach uses anti-diagonals instead, but it is fast for one vs one comparisons, instead of handling multiple query strings.

Regardless, my goal was to learn some SIMD and Rust (first time for both), so I did not read many background papers.

Though I probably won't implement the different weighting schemes, I currently have alignment traceback and searching (allow "free shifts" for the pattern string) features.

High school is out so I am learning SIMD instruction sets, like AVX2 and SSE, and using these to speed up Hamming/Levenshtein distance calculations in Rust. Preliminary testing shows a 20x speedup using vectorized SIMD operations! The end goal is a full Rust library for edit distance routines.

Sneak peek of the code: https://twitter.com/daniel_c0deb0t/status/124224838155819008...

I am a high school student, and this is a published paper that I wrote. If you want to read a shorter blog version of my work, please take a look at my blog: https://blog.liudaniel.com/n-grams-BK-trees. I enjoy working on bringing computer science algorithms to other fields like biology. I have also worked on algorithms for machine learning security.

The general problem that this paper addressed is grouping similar DNA/RNA sequences based on something known as a Unique Molecular Identifier, and then collapsing those groups into consensus sequences. This helps estimate the number of unique sequences while efficiently accounting for substitution errors in sequencing or PCR amplification.

If you have any questions, feel free to ask me!

I am a high school student, and this is a published paper that I wrote. If you want to read a shorter blog version of my work, please take a look at my blog: https://blog.liudaniel.com/n-grams-BK-trees. I enjoy working on bringing computer science to other fields like biology. I have also worked on algorithms for machine learning security.

The general problem that this paper addressed is grouping similar DNA/RNA sequences based on something known as a Unique Molecular Identifier, and then collapsing those groups into consensus sequences. This helps estimate the number of unique sequences while efficiently accounting for substitution errors in sequencing or PCR amplification.

If you have any questions, feel free to ask me!

I am a high school student, and this is a published paper that I wrote. If you want to read a shorter blog version of my work, please take a look at my blog: https://blog.liudaniel.com/n-grams-BK-trees. I enjoy working on bringing computer science to other fields like biology. I have also worked on algorithms for machine learning security.

The general problem that this paper addressed is grouping similar DNA/RNA sequences based on something known as a Unique Molecular Identifier, and then collapsing those groups into consensus sequences. This helps estimate the number of unique sequences while efficiently accounting for substitution errors in sequencing or PCR amplification.

If you have any questions, feel free to ask me!

I implemented many deep learning algorithms in this library, mainly as a way to learn about deep learning. Beware, it is very slow since it is written in Java and there is no GPU acceleration. Maybe this will be of use to people who are learning new deep learning concepts.

If you have any questions, feel free to ask me!

I am a high school student, and this is a published paper that I wrote. If you want to read a shorter blog version of my work, go here: https://blog.liudaniel.com/n-grams-BK-trees.

The general problem is grouping similar DNA/RNA sequences based on something known as a Unique Molecular Identifier, and then collapsing those groups into consensus sequences. This helps estimate the number of unique sequences while efficiently accounting for errors in sequencing or PCR amplification.

If you have any questions, feel free to ask me!

I am a high school student and this blog post is a summary of a research project I did. The full published paper can be viewed here: https://peerj.com/articles/8275/.

This is not really explained in the blog post, but the "naive" method is O(N^2) brute force search, and the "combos" method is recursively going through all combinations of UMIs within a certain edit distance. There are also some other variants that are evaluated.

If you have any questions, feel free to ask me!