Michele Riva

Writing a full-text search engine in TypeScript

Can TypeScript power a search engine that queries a million titles in 41 microseconds? Discover the data structures and algorithms that make it possible.

Writing a full-text search engine in TypeScript
#1about 2 minutes

Why build a full-text search engine from scratch

Building a search engine from scratch is the best way to understand the underlying data structures and algorithms that power it.

#2about 2 minutes

An overview of existing full-text search solutions

Full-text search uses text indexes to quickly find terms, with established solutions like Elasticsearch, Algolia, and newer ones like Meilisearch.

#3about 6 minutes

Preparing text data with tokenization and stemming

Raw text is processed through tokenization, lowercasing, stop-word removal, and stemming to create a clean set of searchable terms.

#4about 6 minutes

Using hash maps to create an inverted index

An inverted index, implemented with a hash map, provides constant-time (O(1)) lookups by mapping search tokens directly to the documents that contain them.

#5about 8 minutes

Optimizing storage space with prefix trees (tries)

Prefix trees, or tries, optimize memory usage by storing common prefixes of words only once, avoiding redundant data storage.

#6about 9 minutes

Implementing typo tolerance with Levenshtein distance

The Levenshtein distance algorithm uses dynamic programming to calculate the "edit distance" between two strings, enabling effective typo tolerance in search queries.

#7about 2 minutes

Introducing Lyra, a fast TypeScript search engine

Lyra is a new, open-source full-text search engine written in TypeScript that achieves microsecond search times by leveraging efficient data structures.

#8about 3 minutes

Q&A on hash functions and memory constraints

The Q&A covers the educational value of custom hash functions, handling acronyms versus stop words, and Lyra's current in-memory architecture.

Related jobs
Jobs that call for the skills explored in this talk.

Featured Partners

Related Videos

See all videos
Things I learned while writing high-performance JavaScript applications27:27

Things I learned while writing high-performance JavaScript applications

Michele Riva

Building software that scales with Typescript37:18

Building software that scales with Typescript

Tal Joffe

Advanced Typing in TypeScript28:44

Advanced Typing in TypeScript

Lars Hupel

Lies we Tell Ourselves As Developers31:13

Lies we Tell Ourselves As Developers

Stefan Baumgartner

Don't compromise on speedy delivery nor type-safety by choosing TypeScript29:44

Don't compromise on speedy delivery nor type-safety by choosing TypeScript

Jens Claes

From clicks to cribs - How to find your dream home with web scraping26:08

From clicks to cribs - How to find your dream home with web scraping

Alexander Lichter

Where we're going we don't need JavaScript - Programming with Type Annotations29:30

Where we're going we don't need JavaScript - Programming with Type Annotations

Peter Kröner

All you need is types48:56

All you need is types

Tal Joffe

From learning to earning

Jobs that call for the skills explored in this talk.