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.
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.
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.
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.
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.
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.
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 want research experiences, then try to email professors directly. Summarize your experiences and how it aligns with the professors' interests.
Otherwise, try reimplementing algorithms and blogging about them. Do fun projects like deploying a model online or to phones. If you are a fan of competitions, then you can try some Kaggle competitions. With some projects (if you say you have experience then you probably already done some) it should not be hard to get research experiences because you have something to show off. Remember to post your projects on Reddit and HackerNews to get internet points and encouragement! It is quite motivating.
Well, I used to play a lot of competitive FPS games because I found it fun. I have also done competitive programming problems for fun/accolades. But after doing more practical research, I realized it felt better to do impactful stuff (especially getting recognized). Also, research is nice because I perform terrible at short events (games, contests) under pressure. I think that if I tried something else before research that met the same criteria I probably wouldn't have done research.
There is one thing I forgot in my advice: you need to have a good foundation first. For example, when I cold emailed, I had many programming projects and I wrote about them in the email. But after you have stuff done, I think aggressively (but politely) "marketing" your work is important to get those opportunities.
I don't really think its fair to say that the "field is in a sad state". Plenty of insightful and well-written papers are put out everyday by hardworking and intelligent people. I still have a long way to go.
I do research because I like solving hard problems that people have never considered. I like to ensure that what I have learned will be put into practical use.
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.