The limits of 2 dimensions
Tags: webdev, maps, rating, sql
Published: 2020-11-05 10:58:54

---
title: The limits of 2 dimensions
published: true
description: Have you ever thought how article rating is done? It's multidimensional!
tags: webdev, maps, rating, sql
cover_image: https://dev-to-uploads.s3.amazonaws.com/i/ti3z6z1wcbd1og4pvn4w.jpg
---
> This article was written to design a solution for [terravigil.com](https://terravigil.com) articles ordering. It will start as a problem related to articles, and will end with the same problem as well. But in between...

Let's do some math:
1. open your favourite site with some articles on the main page - `bbc.com`, `reddit` or `dev.to`, it does not matter.
2. check what you see
3. probably that's latest and the best news or articles

> `latest` AND `the best`.
These are __two__ different __properties__ to order. Simultaneously.
These are __two__ different __dimensions__ to discover.

💡 There is an easy way to "experience" this problem - open any `table` within some table processor (Excel) and try to sort by a field. And then another field. And then by two fields simultaneously - 

```
😅 but there is no such operation.
```

Speaking in a more common language (SQL):

- you can `ORDER BY time, rating LIMIT 10`
- but it will first sort by `time` and only then by `rating`.

Want to get _by time AND by rating_ simultaneously - that is not possible, the ordering is happening sequentially, or it's better to say _in the `1D world`_.

However, it's easy to start the story from another example. From the actual `2D world`. Something we all experienced, and able to understand.

From __maps__ 😉

# Maps
> 🗺 Maps are 2D. Obviously.

Let's do some math:
1. open your favourite site, powered by some maps, and displaying some stuff on the map (that's important!).
2. check what you see.
3. probably there are some "dots"(Points Of Interest) on that map.

For the sake of simplicity - let's use [domain.com.au](https://www.domain.com.au/rent/?excludedeposittaken=1&startloc=-33.82907940464621%2C151.08880273011536&endloc=-33.9215763365357%2C151.25874749329896&displaymap=1) as an example.

![Domain.com.au](https://dev-to-uploads.s3.amazonaws.com/i/ku15iaokw5hb34qpkdxs.png)

Let's check what we actually looking at:
- ✅ it's a City Of Sydney
- ✅ majority of POIs are located in the Downtown
- ✅ there are almost 9000 places to rent
- 💩 just a few dozen are displayed

So, this is "our situation" - we have __more data__ than we could, or should display, so we have to apply some `limits` -  we have to pick "`latest` AND `the best`" items to display. 
> We have to pick `the best` items with restriction by `X` and `Y`. Already 1-dimensional ordering and 2-dimensional filtering.

However, I would like to point in that strange fact, that there is __almost no information outside of Downtown__. 

Probably nobody is selling or leasing their houses so far from the centre. People are not living in those wild areas! Sounds reasonable? 🤷‍♂️ why not?

However, let's double-check it - zoo-oo-ooming in!

![Empty Sydney](https://dev-to-uploads.s3.amazonaws.com/i/fz9yqihbcib4pkvlxqxe.png)

😎 I would assure you, there is life outside of Sydney's CBD, we just are not able to see it due to __limitation of 2D dimensions__.

I've got a video for you
{% youtube -kOZdUAj5V4 %}
👉 In short: there is A LOT of "dots" outside the Downtown, but we don't see them.

The root cause of this effect is - __information tend to be displayed in the areas of higher density__. And yes - it comes, and become worse and worse, with a scale.

> information tend to be displayed in the areas of higher density. Every entity has an equal probability to be picked, and that's why higher "density" produces more "picks"

Actually, the root cause here can be observed as the overall "speed" of updating information on the map as well.
Every time I move the map, `domain` fetches the new information from the backend, and then displays it. Very often, especially within "areas of high density", the updated data does not represent the previous dataset (it might be very different), even if I am searching roughly the same area.

> This causes heavy load on the backend, very slow and non-responsive frontend, as well as annoying _POI-glittering_. Really VERY annoying. Especially when some point you had a plans to inspect just disappears... 

{% twitter 1248453560146116609 %}

# Living in 2-dimensions

We have two problems here:

### Problem 1
Every request is unique. You can move a map as you want, and every time it would be absolutely unique. You will have to reach the server, spend time, return a unique result.

Two customers, looking at one area, are looking at ABSOLUTELY different ones.

![Example from Yandex maps](https://dev-to-uploads.s3.amazonaws.com/i/d8wqxo0wybfcinuexwle.png)

There is one thing you have to understand - maps "displaying" some stuff are here for some time. For "some time" - since IE6 and pre-iPhone era. Since "before" AWS. Since the times, when you had a single database for all 1000000 customers per day.
In other words - 10 years ago you were not able to "scale up", and had to provide performant and efficient backend, or __your Frontend will DDOS your backend__.
- And cartographical services of the past __have__ to solve the problem. And had solved it. 
- But cartographical services of the present are not giving a crap, resulting in the issue mention above, the fix for which is known for years.
> The solution will be explained later

### Problem 2
Problem number 2 consist of the other two problems:
- `SELECT * WHERE X and Y` gives us 10.000 records. So you can select much more information than you can display. So you have to `LIMIT` it. But limiting needs sorting to keep "the best" records.
- `ORDER BY rating` is keeping records in the areas of higher density. And you want to display all possible _opportunitues_.
If all records have the same probability to be displayed - the result would represent just information density.

And "information density" is the problem you have to fix first. Not to _fix_ - but _neutralize_.

### Clustering
For example,​ you can do N smaller requests to "cover" the whole requested area.
```
SELECT WHERE X and Y ORDER BY rating LIMIT 100 
⬇️⬇️⬇️
100 times x(SELECT WHERE x and y ORDER BY rating LIMIT 1)
```

This time instead of one big select we are making a dozen smaller, every of which still tends to display the most "dense" part of it, but covering the whole block more or less __evenly__.

However - __it is not efficient__. There is a better way - `group by`

```
SELECT WHERE X and Y ORDER BY rating LIMIT 100
⬇️⬇️⬇️
SELECT WHERE X and Y GROUP BY (ROUND(x/10), ROUND(y/10)) ORDER BY rating
```
In this case we have grouped all points in some "smaller area" together, resulting potentially up to 100 rows(0.1x0.1 grouping).
This is, again, not efficient, but could it help us with reducing dev city of the data and making coverage a bit more “flat”.

We just make a complex task a bit simpler.

However, __this is not clusterization__ we probably should use to properly display high density information. All we did is __aggregation__, and that's enough! But we did it not in the best way.
There is a better one.

# Problems with "random queries"
- `group by ROUND(x/10)` is not working. `/10` should be different for every zoom level. With every zoom, Map becomes twice bigger, so multiplier should also adjust (x2 every zoom)
> Plus grouping is actually slow. No matter how you do it - it would be slow.
- `WHERE x BETWEEN left and right` would be unique for every user looking at your map. And that is a problem bot only for the network cache, but for the database cache as well
> 👉 Two customers, looking at one area, are looking at ABSOLUTELY different ones.

# Z for Z-code
The goal of aggregation is to _collapse_ some records, which could be grouped somehow, into one record.
For 2d data the most common solution is known as [Z or Morton code](https://en.wikipedia.org/wiki/Z-order_curve), as well as [geohash](https://en.wikipedia.org/wiki/Geohash), [Gray code](https://en.wikipedia.org/wiki/Gray_code) or [Hilbert curve](https://en.wikipedia.org/wiki/Hilbert_curve) - they all are some sort of _spatial filling curves_, literally a _line_ which stitches N dimension together.

> it is called "Z" because every iteration it "Z" itself (and Hilbert curve "U" itself)

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/452b01lh4gljhq3ii20z.png)

It might take a while to understand how such curves work, but the essence of the idea is simple:

> values which are "close" on the curve, are "close" in the N-dimension as well

In our case that would sounds like
```
SELECT WHERE X and Y 
GROUP BY zcode & 0xFFFF00  <---
ORDER BY rating LIMIT 100
```
Where `0xFFFF00` is playing a role of a "mask" and groups 😎_values which are "close" on the curve_😎 effectively clustering elements which are close to each other in 2D.

The explanation how "clustering" work is best seen on [Bings Tile "coordinate" System](https://docs.microsoft.com/en-us/bingmaps/articles/bing-maps-tile-system) - quadkeys (the same Z code) which uses 2 bits (0-1-2-3) per one "division". So masking the "following" bits can "group" all points with the same _beginning_ of the code. And all points in one "rectangle" will have the same beginning.

![QuadKey](https://dev-to-uploads.s3.amazonaws.com/i/159fj6mz1059h6xlecyd.jpg)


# Word-to-vec
A bit different approach is used in search engines, which also need to _find and rank_ something among a billion documents.
"Similarity" search is one of key algorithms there, and [word2vec](https://en.wikipedia.org/wiki/Word2vec) is a key technique here.

> As the name implies, word2vec represents each distinct word with a particular list of numbers called a vector. The vectors are chosen carefully such that a simple mathematical function (the cosine similarity between the vectors) indicates the level of semantic similarity between the words represented by those vectors.

![word 2 vec](https://dev-to-uploads.s3.amazonaws.com/i/bzipb3txldnpb4j3wwl2.png)

Mathematically speaking it's the same case - "close" words or "documents" would end "close" to each other in the (very) multi-dimension space (for the reference it's not 2D or 3D, but closer to 1000D).

# Terravigil
However let's back to our articles case, about displaying "the best and the most fresh" data.

What we actually want:
- we want to see "the best of the best" news longer - more people should read them
- we want to display hot news as soon as possible, so _freshness_ is important
- but there two points violates each other

There are two possible solutions here: `buckets` and `score`

### Buckets
Selects news in predefined time internals, and order inside each group separately.
Literally "display top news of today" and then "display top news of tomorrow". 
- the size of a bucket can be adjusted, like more than a day or less than a day
- buckets might overlap, like you can merge the top news today, and the top news from the past week.
- buckets can be fixed (in time), thus cacheable, or floating, changing intervals they represent every minute or hour.

> Buckets are first ~~sort by time~~ bucket by time, then sort by rate.

### Score
Selects news ordered by a single "score", which is the main problem of this article.
While spatial curves can help with 2D and other _geometrical_ cases - they are more or less useless for this particular case. 

Why? Because some elements "close" on the 2D plot would be VERY far on the curve. Just think for "start" is different from the "end", while curve starts and ends in the same point.

Solution here is to use or special "vector" data formats or databases known as KNN - [k-nearest neighbours search](https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm) (or [Nearest centroid](https://en.wikipedia.org/wiki/Nearest_centroid_classifier).
- `Javascript` implementation https://github.com/mourner/rbush-knn
- `ElasticSearch` https://docs.aws.amazon.com/elasticsearch-service/latest/developerguide/knn.html
- `Postgres` support it as a part of `PostGIS` - remember that our problem can be seen as a geometrical problem
- MySQL does not have any [efficient](https://stackoverflow.com/questions/574691/mysql-great-circle-distance-haversine-formula) way to handle this, and you will probably kill your database if you try.

![KNN](https://dev-to-uploads.s3.amazonaws.com/i/tqcwjfvujwh5tev0fv0k.png)
> A sample data set of points considered as "neighbours"

# Conclusion
Long story short - `Terravigil` uses __buckets__ as long as it's easy to _design_ them and understand how they work, so you can create a correct result.
As well it uses __score__ to derive a single metric from many different other signals to at least understand which article is "the best". 

But all you have to do - just look at the problem from another angle. If you were told to do a 2-dimensional sorting, thinks about limits of the 2-nd dimension.

And it's not just about how to do it, it's also about how to make it FAST.