News for hackers. Stuff that matters.

A comment on Inverted Indexes: A Step-by-Step Implementation Guide.

Re:Inverted Indexes: A Step-by-Step Implementation Guide by bob1029 on Sunday July 27, 2025 @05:38AM (#44700052)
Combining n-grams and bitmap indexes can give you most of the magic in the space.

I've been working on an architecture for code search that relies on a repo-level trigram index and a per-repo FM-index (actual code). The trigram index is used to find the bitmaps of repos that contain each term. These are then ANDed together to produce the final list of repos to search via FM-index.

[ Parent | on HN ]
Re:Inverted Indexes: A Step-by-Step Implementation Guide by lazamar on Sunday July 27, 2025 @08:34AM (#44700873)
Why not search the FM-indexes directly? It is faster than the n-gram search and you can use the exact full text of the needle.
[ Parent | on HN ]
Re:Inverted Indexes: A Step-by-Step Implementation Guide by bob1029 on Sunday July 27, 2025 @09:05AM (#44701055)
If you have millions of them, searching all every time could become a problem.
[ Parent | on HN ]