I am making an app in Flutter which will have some mixed features like a classified app / Tinder. I need a logic or some suggestion on how this can be achieved. Please be patient with my explanation.
Use Case: User A: Posts an AD about selling his TV and add his address to the ad - (Lat and long) User B: In the same app, he is looking for TV ads but he sets his search radius as 5 km. (We have user B's location from his device. Lat/Long)
- Now in my items_db table TV ad info is saved alongwith location
- To show user B the TV near him; I can calculate distance between item and user (Using Google APi)
- But to show him all the TV near him, I will have to first calculate distance between the user and ALL the items available in Classified/items_db to find out how many of them are actually under the 5km filter he applied.
- Right now we are talking about 1 user: But then if I have 1000 users then I will have to calculate the distance between ALL the items against all users position and then show him only the ones that are in their specified range (i.e. 5km or 10 km)
This seems too big or just bad to be implemented like that. So my question is how do we do this?
If this wasn't clear enough then use Tinder as an example here:
When I select in Tinder that "show me people in 2 km radius only". Then how does Tinder know that? I mean in order to figure out who is 2 km away; they will first have to calculate the distance for ALL THE USERS AVAILABLE in order to see which ones can be shown to end user that fit that 2 km criteria!! How is it done there?
You certainly could check the distance between every pair of points, but that is not the only option you have.
In general, what you want is to find the nearest neighbor(s) of each point. That is, you only want to find other points that are within some set distance. Generally this is called nearest neighbor search. There is no single best method to do this, and indeed performance may very well vary based on your exact data, but two methods that might be worth consideration are locality-sensitive hashing which is using a hash function that attempts to place similar points in the same buckets (or even in buckets that are close) so that you only need to check those buckets to find neighbors, and k-d trees, a datastructure designed with nearest neighbor search in mind.