Information Retrieval Search Engine
Disk-backed Python search engine with tf-idf ranking over 55,393 crawled web pages, built to never hold the index in memory.
The index doesn't fit in memory. Everything else follows from that.
Building an inverted index is a first-week exercise until you're told you can't hold it. Ours ends up at 370 MB across 722,602 terms, and the machine it had to build on couldn't be assumed to have that to spare. So the interesting part was never the data structure, it was where the data structure lives.
That single constraint decides the shape of the whole system. The build can't accumulate; it has to flush. The flushed pieces have to be mergeable without reading them all at once. And a query can't scan the merged file, because scanning 370 MB per search is not a search engine. It has to know the byte to jump to before it opens anything.
What it had to do.
Index 55,393 crawled pages of raw HTML in bounded memory, tokenizing, stemming, and weighting terms found in titles and headings above body text.
Fold the partial blocks into one term-sorted file without loading them, computing each term's document frequency and idf on the way through.
Answer a query from disk in milliseconds: Boolean AND over the matching documents, ranked by tf-idf, top five URLs, behind a small FastAPI web UI.
A three-week course project for CS121 at UC Irvine, with Shawn Gazin and Hodaka Nakamura. Single machine, single process, no external search library.
Flush, merge, and seek.
The build is SPIMI: postings accumulate in a plain dict of term to list, and every thousand documents (or whenever psutil reports system memory above 80%) the dictionary is written out to its own partial file with the terms in sorted order, then cleared. Peak memory is a block, not an index, and the number of blocks is just however many the corpus needs.
Merging is a k-way heap merge across those files. One line is read from each partial to seed the heap, the smallest term is popped, every other file sitting on the same term is drained into it, and the combined postings are sorted by doc id and written out as a single line. Because each partial was written sorted, the merge never needs more than one line per file in memory, no matter how many files there are.
The last build step is what makes queries cheap: walk the merged file once, record the byte offset where each term's line begins, and save that map. At query time the index file is opened once at import and stays open, and a lookup is a seek to the offset plus a readline, so the process reads exactly the postings for the terms asked about and never touches the rest of the 370 MB.
Three passes over the data, then a seek per term.
Parse, weight, flush
BeautifulSoup pulls the text out of each page, NLTK tokenizes and Porter-stems it, and terms inside title, h1–h3, b, and strong are counted again with weights of 8 down to 2. Every thousand documents the block goes to disk sorted.
One heap, one line per file
A k-way merge pops the lowest term across all partials, drains every file holding it, sorts the postings by doc id, computes idf as log10(N/df), and writes one line per term to the final index.
Byte address per term
A final pass records where each term's line starts, so retrieval never scans. The map is the only part of the index that stays resident.
From typed text to five ranked URLs.
Every search runs this path, and the whole point is how little of the index it touches.
Normalize the query the same way the corpus was normalized
The string is split on a literal AND, broken into alphanumeric tokens, lowercased, and Porter-stemmed, the identical treatment the indexer gave the documents. If the query and the index disagree about stemming, nothing matches, so there is exactly one tokenizer's worth of behaviour to keep in sync.
Seek to each term instead of scanning for it
Each stemmed term is looked up in the offset map, and its line is read with a seek plus a readline against the already-open index file, under a lock so concurrent requests can share the handle. A term that isn't in the map returns nothing without any file access at all.
Intersect the document sets
The doc ids from each term's postings are intersected, bailing out the moment the running intersection is empty. Retrieval is strict AND: a document has to contain every term to be a candidate.
Score the survivors with tf-idf
For each term, tf is 1 + log10(term frequency) and idf is log10(N/df); the product is summed across terms per document. Because heading and title occurrences were folded into term frequency at index time, a page that says it in its title outranks one that mentions it in passing.
Return the top five with their URLs
Documents are sorted by score, the top five doc ids are mapped back to their crawled URLs, and the response carries the stemmed terms and the measured latency alongside the results.
Choices behind the index.
What I'd flag reading it back.
Storing postings as JSON objects
CostEvery posting on disk is a full object with its keys spelled out, which is most of why the index is 370 MB rather than a fraction of it. A pair of integers per posting would have cut the file dramatically and sped up every line parse. It is the single change with the best ratio of effort to payoff.
Computing idf in the merge and then again at query time
CostThe merger writes each term's idf into the index, and the query path recomputes it from the length of the postings list and ignores the stored value. Harmless, but it's the kind of duplication that turns into a bug the moment the two definitions drift.
Leaving the earlier in-memory implementation in the repo
Costsearch/search.py still holds the first approach: load the whole index into a dict, with TODOs for the scoring that was never written there. It doesn't run and it can't, since it parses the two-field index format that the merger stopped producing. It should have been deleted when engine.py replaced it.
The first working version was Boolean-only: intersect the postings, take whatever five documents came out first. Adding tf-idf was the obvious fix and it's the change the write-up talks about, but the thing that decided whether any of it worked was that the query has to be mangled in exactly the same way the corpus was. The indexer lowercases, drops anything non-alphanumeric, and Porter-stems; the query path has to do all three, in the same order, or the term you look up is not the term that was stored. It's the least interesting code in the project and the only code where being 'close enough' means every search silently returns nothing. Our own test sheet has a query for this, a string of nonsense that should return no results, precisely because a system that returns nothing for a bad query and a system that returns nothing for everything look identical from the outside.
Where I'd take it.
Compact the postings. Two integers per posting instead of a JSON object, and the 370 MB index gets small enough that the parse cost stops mattering. The offset map already makes the format swappable without touching the query path.
Fall back from AND to a ranked OR when the intersection comes up empty, so a long conversational query degrades into its best matches instead of into nothing.
Store positions in the postings. It's the prerequisite for phrase queries, and it's the difference between finding pages that contain both words and pages that contain the phrase.