Back to Playground

Inverted Index + TF-IDF

Lucene-style search internals: posting lists, skip pointers, term positions, and TF-IDF scoring. Watch step-by-step query execution as documents are iterated and scored.

1.5s

Query Execution

Enter a query and click "Execute" to see step-by-step execution

Posting Lists

the
DF: 6IDF: 0.12
1
2
skip↓
3
4
skip↓
5
7
for
DF: 6IDF: 0.12
1
2
skip↓
3
6
skip↓
7
8
time
DF: 5IDF: 0.20
1
3
skip↓
4
5
skip↓
7
ride
DF: 4IDF: 0.30
1
4
skip↓
5
8
and
DF: 4IDF: 0.30
4
5
skip↓
6
8
matching
DF: 3IDF: 0.43
1
3
skip↓
4
algorithm
DF: 3IDF: 0.43
1
4
skip↓
7
drivers
DF: 3IDF: 0.43
1
3
skip↓
7
real
DF: 3IDF: 0.43
1
4
skip↓
7
with
DF: 3IDF: 0.43
2
3
skip↓
5
driver
DF: 3IDF: 0.43
3
4
skip↓
6
uses
DF: 2IDF: 0.60
1
5
find
DF: 2IDF: 0.60
1
2
riders
DF: 2IDF: 0.60
1
3
geospatial
DF: 1IDF: 0.90
1

Document Store (8 docs)

ID: 1Uber Ride Matching

The ride matching algorithm uses geospatial indexing to find nearby drivers for riders requesting trips in real time

ID: 2Search Ranking

Search ranking combines relevance scoring with personalization to find the best results for each user query

ID: 3Driver Dispatch

Driver dispatch optimizes for minimal wait time by matching riders with the nearest available drivers

ID: 4Real-time Analytics

Real time analytics track ride patterns and driver availability to optimize the matching algorithm

ID: 5Fare Calculation

Fare calculation uses distance and time to compute the ride cost with surge pricing during high demand

ID: 6Driver Onboarding

Driver onboarding process includes background checks and vehicle inspection for rider safety

ID: 7Route Optimization

Route optimization algorithm finds the fastest path using real time traffic data for drivers

ID: 8Payment Processing

Payment processing handles credit cards and digital wallets for seamless ride transactions

Lucene Index Internals

Posting List

Sorted list of document IDs containing a term. Sorted order enables efficient parallel iteration.

Parallel Pointers

For AND queries: maintain pointers into each posting list. Compare docIds, advance smaller pointer. Match when all equal. O(n+m) time.

Skip Pointers

Jump ahead when gaps are large. If pointer A is at doc 5 and B is at doc 100, skip A forward using skip list.

Merge Algorithm

For OR queries: walk through both lists, output minimum docId, advance that pointer. Like merge-sort merge phase.

Term Positions

Word positions within documents. Enables phrase queries like "ride matching" (adjacent terms).

Segment Iteration

Lucene iterates segments, merging results. Each segment has its own posting lists and skip lists.