What I learnt this week:
Reverse Indexing
I am making a YouTube search application that allows you to search videos that you have saved in your account. This lead me to learning about how searches work and how they are optimised. One of the biggest thing i learnt was about reverse indexing.
If you've worked with SQL databases before you'd know that data is stored in tables with a primary key used to index through the entries. Of course you can add other indexes as well, this is regular indexing, but it has a major limitation for search speeds. Imagine this table below (maybe insert table pic), if you wanted to search for a title "x" in this you'd have to go through all the entries using the index and match each entry's value to the value searched. This takes O(n) time which is not very fast.
This is where reverse indexing comes. Reverse indexing is when the entry values are instead used as the indexes and the values they hold are references to the rows that store these values.
Now you don't have to go through all records to find the entry and can just search in the value index.
PostgreSQL is my database of choice, so i learnt that PostgreSQL implements reverse indexing using a tsvector(text search vector) function which converts a column(or columns) of a table to a vector that represents reverse indexes. tsquery is a function used to convert the search query in a form that can be easily used to match the tsvector values to find the result faster.
Finally there's a GIN or Generalised Inverted Index, which is the actual index structure PostgreSQL uses under the hood for tsvector columns. Think of it like an index but for every unique word, it keeps a list of which rows that word shows up in, so a search for a word goes straight to the word's row to find where the word shows up instead of scanning every row.
This is the first layer of optimisation for my search feature. Depending on the results, I'll decide if it needs more optimisation or not.
Clustering
This is something i revisited on reading Algorithm design by Jon Kleinberg and Éva Tardos. Clustering is basically grouping of elements based on how similar they are. Pretty easy. Now how do we know how similar two elements are? Well we use a distance function duhh and obvious enough smaller distance = more similar. Now there are some basic rules for this distance function
- d(a,a) = 0, basically for the same element distance is zero meaning its 100% similar
- d(a,b) > 0, different elements have positive distance
- d(a,b) = d(b,a), distance between 2 elements is similar no matter where you start from
K-clustering
K-clustering basically means grouping a set S into k number of clusters. There's a very easy way to think about doing this and this is where a new term comes up: spacing. Spacing is the smallest distance between two elements that belong to different clusters.
Spacing tells you how close 2 clusters are to coming in contact. Now if we want clusters to be as distinct as possible we would want 2 clusters to have maximum spacing in between them. This is called maximum spacing clustering. There may be different ways to cluster a set but I'll focus on the clustering with the max spacing.
An easy algorithm proposed for maximum space clustering is Kruskal's algorithm but with slight tweaks. We merge nearby points as early as possible. we simply merge points in order of closeness until k clusters are formed. a different approach could also be to just delete k-1 of the max distance edges from a minimum spanning tree and it would result in a max spacing cluster.
Top comments (0)