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

user_3810748 0
Viewed 1264

Background

Hey everyone, I recently discovered Google's open source S2 library

https://github.com/google/s2geometry

I am currently programming an application that requires finding K closest points, given an original target point. Currently I am using PostgreSQL with geospatial indexes on columns containing latitude/longitude values to achieve this - However, I am looking for alternatives when S2 caught my eye.

Questions

I am rather unfamiliar with the library, and I have some questions regarding it.

1) Is it possible to find K closest points using the S2 library

2) How fast would the query in S2 be vs Geospatial indexes (superior/inferior/same/etc)

geospatial geolocation geometry
1 Answers

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.

user_5373480
Related