Lets say I'm developing a dapp that helps people redeem their beer coins by buying each other beers. They need to find each other and so they use a mobile DAPP. Bar owners are be able to add their bar struct Bar {int lat; int long; string32 bar_name; uint ownerID} and drinkers can find their nearest bar findknearest(int lat,int long), check in checkIn(barID,userID), which would enable them to be found and find other people in the same bar who owe them a beer whoCanBuyMeABeer(uint barID).
So there needs to be a way to store and efficiently query lot of lat,long points. What are your opinions on the best way to do this.
My initial idea is to:
- Simply store the bars in a contract as array of structs
Bar[] bars - Load into a KDtree using client side code that
findknearest(int lat,int long)is implemented client side.
However it seems wasteful:
- Each client has to parse all the points in the world in order to find nearby bars's.
- Storing a lot of information on the blockchain
So I wondered if you had any better ideas e.g. :
- is there a smart way of splitting the state up. e.g. number of grids cells over earth and bar owner decides where to insert their bar. (might also help with spherical geometry)
- is there an efficient way to build a searchable tree structure on insert. e.g. inserts are optimal but tree is not rebalanced.
- store data in IPFS/SWARM (can you store as an append only data structure? as a tree?)
Best Answer
You don't really need a string name or a bar owner id (the coordinates alone can be the identifier (two bars cannot have the same coordinates)).
Instead of the KDtree you could simply use an array of bar structs for each geographical area (the bar coordinates must fulfill a positional relationship, for example, that of belonging to a grid that covers the area).
Sort the bars based on latitude or longitude and use a binary search to look for the closest bar (this is easy given the user's and bar's coordinates).
You could then use a contract to store each area and include it in a "main" contract depending on the user's current location. This avoids the block size limit issue.