Inverted Index

The core mechanism of an inverted index is a dictionary that maps each unique term (or token) to a postings list. This list enumerates every document where the term appears, often accompanied by metadata like term frequency and positions within the document. This structure inverts the natural document-centric view, enabling queries to find all documents containing a specific term in constant or near-constant time, regardless of corpus size.

• Example: For the term 'neural', the postings list might be: {doc_42: [pos_5, pos_87], doc_101: [pos_3]}.
• Efficiency: This design is optimal for conjunctive queries (e.g., 'neural AND network') where results are found by intersecting postings lists.

An inverted index is a classic sparse representation. It only stores information for terms that actually exist in documents, ignoring the vast space of all possible terms. This contrasts with dense vector embeddings, which represent documents as fixed-length vectors in a continuous space where every dimension has a value.

• Sparse Vector: Represented as {'neural': 2, 'network': 1, 'embedding': 0} where only non-zero entries are stored.
• Memory Efficiency: For text where most terms appear in only a few documents, the inverted index is highly memory-efficient compared to a dense matrix of document-term counts.
• Foundation for BM25: This sparse representation directly enables the term frequency-inverse document frequency (TF-IDF) calculations and the BM25 ranking algorithm.

Advanced inverted indices store positional data within each postings list entry, recording the exact word offsets where a term appears in a document. This enables phrase queries and proximity searches, which are critical for precise information retrieval.

• Phrase Search: To find the phrase 'inverted index', the system retrieves the postings lists for both 'inverted' and 'index', then checks if their positions are consecutive in any document.
• Proximity Search: Queries like 'neural NEAR/5 network' can be resolved by checking if the positions of the two terms are within five words of each other.
• Trade-off: Storing positions increases the index size but is essential for high-recall, linguistically-aware search.

Because postings lists for common terms can be very long, sophisticated integer compression algorithms are applied to reduce memory footprint and improve cache efficiency during query processing. These techniques exploit the fact that document IDs and positions are sorted integers.

• Delta Encoding: Stores the gaps between consecutive document IDs (d-gaps) instead of the full IDs. The sequence [450, 453, 460] becomes [450, 3, 7], which typically contains smaller numbers.
• Variable-Byte Encoding: Compresses these smaller gap integers using a variable number of bytes.
• Impact: Compression can reduce index size by 50-75%, enabling larger corpora to reside in RAM for ultra-fast query performance.

Maintaining an inverted index for a changing corpus requires strategies for incremental indexing. A simple, immutable index is fast for search but requires a full rebuild for updates. Production systems use more complex architectures to support real-time or near-real-time document additions and deletions.

• Log-Structured Merge Trees (LSM): New documents are written to an in-memory buffer, which is periodically merged with the main on-disk index.
• Delta Indexes: A small, mutable 'delta' index holds recent updates and is searched alongside the main index; periodic merges consolidate them.
• Challenge: Efficiently handling document deletion requires either tombstoning or periodic re-indexing to reclaim space.

The modern hybrid search paradigm combines the precision of keyword-based inverted index search with the semantic understanding of dense vector search. The inverted index executes lexical matching via algorithms like BM25, which is excellent for exact term matching, spelling correction, and matching rare keywords.

• Complementary Strengths: A query for 'Python' benefits from an inverted index to distinguish the programming language from the snake, while a query for 'programming language with simple syntax' requires semantic vector search.
• Rank Fusion: Results from the sparse (inverted index) and dense retrieval paths are combined using techniques like weighted scoring or reciprocal rank fusion (RRF).
• System Design: This makes the inverted index a critical, non-replaceable component in Retrieval-Augmented Generation (RAG) architectures that demand high precision.

A dense vector index is a database index optimized for storing and performing approximate nearest neighbor (ANN) search over high-dimensional vector embeddings.

• Semantic Search Core: It is the primary data structure enabling semantic search, where queries and documents are encoded into vectors (embeddings) by a model like Sentence-BERT.
• Contrast with Inverted Index: While an inverted index maps terms to documents, a dense vector index maps document vectors to IDs and finds other nearby vectors in the embedding space.
• Common Algorithms: Implementations often use algorithms like HNSW (Hierarchical Navigable Small World) or IVF (Inverted File Index) for efficient search in high-dimensional spaces. This is the technology underpinning vector stores like Pinecone, Weaviate, and Qdrant.

Hybrid search is an information retrieval strategy that combines the results of sparse (keyword-based) and dense (semantic vector-based) retrieval methods.

• Best of Both Worlds: It leverages the precision of BM25 for exact term matching and the conceptual understanding of dense vector search for synonym and context matching.
• Implementation: Typically involves running both searches in parallel, then using a weighted scoring function (e.g., score_hybrid = α * score_sparse + (1-α) * score_dense) to fuse and rerank the results.
• Production Standard: For enterprise Retrieval-Augmented Generation (RAG), hybrid search is considered a best practice, as it mitigates the weaknesses of either approach used in isolation.

Semantic chunking is the process of segmenting a document into coherent units based on contextual meaning and topic boundaries, rather than arbitrary character or token counts.

• Retrieval Optimization: The goal is to create chunks that are self-contained and semantically unified, which dramatically improves the relevance of information retrieved for a language model's context window.
• Beyond Recursive Splitting: Moves past simple recursive character text splitting by using techniques like embedding-based chunking (measuring cosine similarity between sentences) or TextTiling (analyzing lexical cohesion) to find natural breakpoints.
• Critical Preprocessing: High-quality semantic chunks are a prerequisite for generating accurate embeddings, making this a foundational step for building effective dense vector indices.

Query expansion is an information retrieval technique that augments a user's original search query with additional related terms or phrases to improve recall.

• Addressing Vocabulary Gap: It helps bridge the gap between the terms a user employs and the terms present in relevant documents (the "vocabulary problem").
• Methods: Can be done using:
  • Lexical Resources: Like WordNet for synonyms and hyponyms.
  • Statistical Methods: Like analyzing top results from an initial search (pseudo-relevance feedback).
  • LLM-Based Generation: Using a language model to generate related concepts or reformulations of the query.
• Synergy with Indexes: The expanded query is then executed against the inverted index or dense vector index, retrieving a broader and often more relevant set of candidate documents.