Possible to find K closest points using S2 library (and is it effective)?

Question

Background

I recently discovered Google's open source S2 library for manipulating geometric shapes.

https://github.com/google/s2geometry

I'm developing an app that needs to locate the K nearest points to a target point. Currently, I'm utilizing PostgreSQL with geospatial indexing on the latitude/longitude columns. I'm exploring alternative options and S2 has caught my attention.

Questions

I have limited knowledge about the library and I have some questions about it. I would be grateful for any information on its practicality for use.

Question 1) Does anyone know if it is possible to find K closest points using the S2 library?

Question 2) Does anyone know how fast the query would be in S2 vs Geospatial indexes?

I understand that a complete answer is challenging and depends on many variables. I am simply seeking a rough guideline and the perspective of someone more experienced as a starting point.

Answer 1

Google's S2 library is a form of geohashing. It can be used to optimize your geo lookups significantly since it's just a hash/id lookup.

One method of indexing could be:

1. Index all your points that you care about on a fairly large S2 cell level. You should evaluate your points and see what level works for you based on this chart.

2. On retrieval, convert your search point to an S2 cell at that level, and then pull all candidate points based on that.

3. (Optional depending on the accuracy you care about) Calculate distance between candidate points and search point and sort

There are some trade-offs with this performance gain:

• Indexing S2-cells on your points means slightly more storage (64-bit integers per id)

• You may miss points outside of the S2 cell that you queried by. You could index on multiple levels of S2 to ensure you retrieve enough points. Depending on the density of your points, this might not be an issue.

• Retrieving by S2 cell IDs won't actually give you the distance between points - you'll have to calculate that yourself

Here's a code example from the Node S2 library:

const s2 = require('@radarlabs/s2');

const user1LongLat = [-73.95772933959961, 40.71623280185081];
const user2LongLat = [-73.95927429199219, 40.71629785715124];
const user3LongLat = [-73.99206161499023, 40.688708709249646];

const user1S2 = ["user1", new s2.CellId(new s2.LatLng(user1LongLat[1], user1LongLat[0])).parent(13)];
const user2S2 = ["user2", new s2.CellId(new s2.LatLng(user2LongLat[1], user2LongLat[0])).parent(13)];
const user3S2 = ["user3", new s2.CellId(new s2.LatLng(user3LongLat[1], user3LongLat[0])).parent(13)];

const groups = {};
[user1S2, user2S2, user3S2].forEach(([userId, cellId]) => {
  const group = groups[cellId.token()] || [];
  group.push(userId);
  groups[cellId.token()] = group;
});

const searchPointLongLat = [-73.98991584777832, 40.69528168934989];
const searchPointS2 = new s2.CellId(new s2.LatLng(searchPointLongLat[1], searchPointLongLat[0])).parent(13);

console.log(searchPointS2.token()); // '89c25a4c'
console.log(groups); // { '89c2595c': [ 'user1', 'user2' ], '89c25a4c': [ 'user3' ] }

const closePoints = groups[searchPointS2.token()];
console.log(closePoints); // [ 'user3' ]

Here's a map visualization of the S2 tokens that were created.

Long story short is, yes, it is a form of hashing so you get faster performance with the trade-off of storage, but there are some aspects of accuracy you may have to tune depending on your requirements.