The paper presents a new version of the MegaBLAST module in the BLAST software package, which preprocessed the database to improve search performance. The authors developed a program called `makembindex` to create a data structure for rapid seed searching. The new 'indexed MegaBLAST' was found to be faster than the non-indexed version and another implementation called miBLAST for most practical uses. The indexed MegaBLAST was deployed in the NCBI Web BLAST service, improving response times for queries against the human and mouse genomes. The paper also discusses the design of the database index structure, testing methods, and comparisons with other tools. The results show that indexed MegaBLAST is particularly effective for masked databases and shorter queries, while non-indexed MegaBLAST performs better for longer queries. The authors suggest potential improvements and extensions to the implementation, including using non-uniform strides and more sophisticated data structures.The paper presents a new version of the MegaBLAST module in the BLAST software package, which preprocessed the database to improve search performance. The authors developed a program called `makembindex` to create a data structure for rapid seed searching. The new 'indexed MegaBLAST' was found to be faster than the non-indexed version and another implementation called miBLAST for most practical uses. The indexed MegaBLAST was deployed in the NCBI Web BLAST service, improving response times for queries against the human and mouse genomes. The paper also discusses the design of the database index structure, testing methods, and comparisons with other tools. The results show that indexed MegaBLAST is particularly effective for masked databases and shorter queries, while non-indexed MegaBLAST performs better for longer queries. The authors suggest potential improvements and extensions to the implementation, including using non-uniform strides and more sophisticated data structures.