One of these days, I began to wonder how Google was able to establish itself as the most popular search engine, what is behind Google, and how he obtained such a large number of URLs.
Behind google is complex system and there is lot of caching:
- Crawl + Index High-PageRank URLs
- Preprocessing via LLMs (e.g., BERT, MUM)
- Candidate Document Retrieval
- Neural Matching & RankBrain Filtering
- Ranking Function (Weighted Scoring)
And I’d like to start at the top and work my way down.
One step at a time
The first question I asked myself was how Google truly acquires the URLs, because crawling requires at least one URL and does not guarantee that you will get all URLs, and what if the missing URL has the solution you were searching for?
Google uses a variety of sources, including seed URLs (gov, edu, and media), recursive crawling (link discovery — google bot), user contribution via API, and direct ingest from partner APIs or curated sources.
If we have pages we can search for information. Keyword matching was previously employed in a variety of ways, but Google now uses AI to determine what you’re looking for, such as RankBrain, Neural Matching, and LLMs.
Crawling
Building your own bot to tour the internet is not a tough effort if you know how to use Python; all you have to do is request a URL and check for an element with a link, then do it recursively. It’s another story if you want it to be efficient and multi-threaded.
A good example of crawler is gospider
PageRank
Google’s success can be attributed to the Markov chain, which is formed into PageRank.
By “formed,” I mean that it derives from a Markov chain and the key idea behind PageRank is to measure the importance of a webpage in simple words.
The difference between them is that transition probability is calculated from links and teleportation step (don’t worry, it’s math, but not that difficult).
Transition probability is declared by outgoing links.
When we look at page “A”, we can see that page has 2 outgoing links so the transition probability row is:
** A - B - C - D - E - F
A: [0, .5, 0.5, 0, 0, 0]
For example: P(B|A) = 1/N = 1/2 = 0.5
why 0s, because the probability of getting for example to the page A is 0.
Full transition probability matrix would look like this:
A B C D E F
A [ 0, 0.5, 0.5, 0, 0, 0 ]
B [ 0, 0, 0.5, 0.5, 0, 0 ]
C [ 1, 0, 0, 0, 0, 0 ]
D [ 0, 0, 0.5, 0, 0.5, 0 ]
E [ 0, 0, 0.5, 0, 0, 0.5 ]
F [ 0, 0, 1.0, 0, 0, 0 ]
Page rank vector (π) is declared by random state, because after while it converges(reach) to a number, size of page rank vector is number of pages.
Where next iteration of rank vector is dot product (previous state and transition probability).
This is calculated until change is lower then tolerable threshold.
Teleportation
With that explained, there is one more tiny thing to perform to solve problems such as a person becoming stranded on the internet or sporadically switching pages.
During the calculating procedure, there is a random state known as the dumping factor.
P’ = αP + (1 — α)E
where:
- E = matrix where elements “1/N” (size of P)
- α = dumping factor usually “0.85”
- P = transition probability
If you are interested in seeing more or just formal explanation about PageRank I recommend this video.
Note a little bit out of context: do not get stuck at the idea of just the webpage, Markov chain is powerful thing and is also used in AI for predicting next word. If you understand PageRank then you understand Markov chain.
RankBrain
RankBrain is one of Google’s top 3 ranking factors (along with backlinks[PageRank] & content relevance,).
In high point of view you can see search like this:
Query → Query Interpretation (vectorization, context) → Search Similar → Rank → Return
RankBrain cooperates with LLM (BART or similar), RankBrain will calculate similarity to reduce number of results and forward it into the LLM to find perfect match.
To understand more and apply this knowledge, I chose to create a custom file search that uses RankBrain and LLM to match correct files or directories.
As our small RankBrain I will be using FAISS (Facebook AI Similarity Search), it is a library for fast nearest-neighbor search in large vector collections.
This library include two approaches on searching the large vector collection:
- IndexFlatIP: Exact search using dot product similarity.
- IndexHNSWFlat: Approximate search using Hierarchical Navigable Small World (HNSW) graphs with flat storage.
The main idea behind is that FlatIP is focused on accuracy and HNSWFlat is focused on speed.
next on the list is LLM, this LLM needs to be focused on ranking (giving score for a match) for this I choose CrossEncoder specially model ms-marco-MiniLM-L-6-v2 .
Applying this knowledge to create custom file search
Whole project can be found on github here.
I started with classic file retrieval and used docs to create script that look like this:
from sentence_transformers import SentenceTransformer, CrossEncoder
import faiss
import numpy as np
# Load sample documents
def read_files_from_dir(dir_path: str):
for root, _, files in os.walk(dir_path):
for file in files:
yield root + "/" + file
dir_path = os.environ['HOME']
documents = [file for file in read_files_from_dir(dir_path)]
# Encode documents
encoder = SentenceTransformer('all-MiniLM-L6-v2')
doc_vectors = encoder.encode(documents, normalize_embeddings=True)
# Create FAISS index
dimension = doc_vectors.shape[1]
index = faiss.IndexFlatIP(dimension)
index.add(doc_vectors)
doc_map = {i: doc for i, doc in enumerate(documents)}
def search_docs(request):
query_vector = encoder.encode([request.query], normalize_embeddings=True)
D, I = index.search(np.array(query_vector), request.top_k)
candidates = [doc_map[i] for i in I[0]]
pairs = [(request.query, doc) for doc in candidates]
scores = cross_encoder.predict(pairs)
reranked_docs = [doc for _, doc in sorted(zip(scores, candidates), reverse=True)]
return QueryResponse(query=request.query, results=reranked_docs)
print(search_docs({query: "idek attachments"}))
Reading files and directories
Quickly I realized kind of hard or impossible problem to solve “performance”, because looping home directory isn’t that good idea as I thought.
We will be looping around millions of files and we are still in python even in C/++, rust and in other high performance language it still takes around 25 seconds to loop the files and we do not only want to loop it but also encode it into vectors. Well it’s a great start I guess.
So clearly we need to be more smarter then looping though home directory we need relevance, multiprocessing and caching.
So I started with the read_directories function that will loop directories when I look back I should just recreate it in C and import it into python, but end up with a much more faster version (compared to single threaded in python) that is using multiprocessing:
def read_dirs_from_dir(dir_path: str, max_workers=8):
"""Yield directories under dir_path as soon as they are found."""
base_path = Path(dir_path)
with ThreadPoolExecutor(max_workers=max_workers) as executor:
futures = {executor.submit(scan_dirs, base_path): base_path}
while futures:
for future in as_completed(futures.keys()):
futures.pop(future)
try:
subdirs = future.result()
except OSError:
# future does not exist
continue
for subdir in subdirs:
yield str(subdir)
futures[executor.submit(scan_dirs, subdir)] = subdir
Then implemented with similar logic read_files function, but I wanted to add some context to them, so I read 200 bytes from the file, and if it’s a programming language file, I get a function list using regex:
def read_n_bytes_from_file(file_path: Path, n: int) -> bytes:
try:
with file_path.open("rb") as f:
return f"{str(file_path)}: {f.read(n).decode('utf-8', errors='ignore')}"
except OSError:
# binary file (cannot decode bytes)
return f"{str(file_path)}: ''"
def process_file(file_path: Path) -> tuple[str, str]:
"""Return (file_path, text)."""
ext = file_path.suffix.lstrip(".").lower()
regex = COMPILED_PATTERNS.get(ext)
if regex:
return str(file_path), extract_functions_from_file(file_path, regex, ext)
else:
return read_n_bytes_from_file(file_path, 200)
Caching, batching and indexing
Okay from this point we got some solid functions for reading files, but we will have memory issues when it comes to large lists of files. So next is caching, I end up creating sqlite3 database.
def create_connection(database_path: str = "documents.db", first_time: bool = False):
cx = sqlite3.connect(database_path)
cu = cx.cursor()
cu.execute("ATTACH DATABASE 'cache.db' AS cache")
if first_time:
clear_cache(cu, clear_all=True)
create_cache(cu)
return cx, cu
definitely I didn’t planning to open connecting for every file/directory found So the next step is to break the files/directories into batches and then enter them into the database using pickle and base64; during this process, I also began indexing them in the FAISS index.
# init cache
cx, cu = create_connection(first_time=True)
cx.close()
def index_strings(encoder, dir_path: str, table: str, read_func, index, batch_size=3000, max_workers=8):
"""indexing in parallel with FAISS"""
def save_and_clear():
vectors = encoder.encode(batch_buffer, normalize_embeddings=True)
index.add(np.array(vectors, dtype=np.float32))
# cache - 3000
cx, cu = create_connection()
# just database query insert to table
insert_cache(cx, cu, b64e(pickle.dumps(batch_buffer)), table)
cx.close()
batch_buffer.clear()
# run garbage collection after batch
gc.collect()
batch_buffer = []
for string in read_func(dir_path, max_workers=max_workers):
batch_buffer.append(string)
if len(batch_buffer) >= batch_size:
save_and_clear()
if batch_buffer:
save_and_clear()
The reason for exiting the database at the start is that we are going to run a multiprocessing function, and if we get a connection in a different thread, we will run into a lot of problems, so we need to create a new connection for each thread.
I also made this function into general purpose in order to swap type of index at the fly.
Only batching
Now we could have used the rest of the code from the beginning, but hold on, we must figure out the batching from database.
It’s small normalization, but painful to be honest:
def batch_normalization(candidates, I):
indices = []
for i in I[0]:
tmp = int((i // BATCH_SIZE) + 1)
if not tmp in indices:
indices.append(tmp)
candidates = get_docs_by_ids(cu, indices, "cache.directories")
valid_candidates = []
for c, index in zip(candidates, indices):
for i in I[0]:
if int((i // BATCH_SIZE) + 1) == index:
candidate = pickle.loads(b64d(c.encode("utf-8")))[i % BATCH_SIZE]
valid_candidates.append(candidate)
return valid_candidates
The problem here is that database starts from index 1 instead of 0 and we need to find the correct batch using:
# F_index from FAISS starts from 0
F_index // BATCH_SIZE + 1
BATCH_SIZE # just our batch size
# this will get from the n file/directory
i % BATCH_SIZE
# i = index of the array saved that's why not again +1
# F_index = 4532, BATCH_SIZE = 2000
# to query: 4532 // 2000 (+1) = 2 (+ 1) we get correct batch
# then correct position [532] = [4532 % 2000]
At the end I’ve wrapped it into web interface:
Conclusion and final words
Still it’s far from good optimization, because even 2411 directories took 13 seconds, but it was interesting experience.
Some potential upgrades include rewriting into rust or just a few functions into C, and to not loop without relevance for example each folder is known for some purpose (.git, node_moduls, vendor) and git repositories have usually README.md, the name can tell you whether it is worth continuing or not.
I was planning to also use summaries from models to add more context, but even looping directories took a lot of time so it’s just left it there and not used.
If you enjoyed this article, clap and follow me! Thanks for reading, and I wish you the best luck on your journey👋.