3

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?)
2

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.

  • I like your idea but I'm new to Ethereum and have trouble figuring out how to implement it. What would a smart contract for a geographical area look like and how would contracts be added to it? – David J. Oct 15 '16 at 21:42
  • 1
    A contract for a geographical area would need to define the area, for example, by using two points to define a rectangular area and the coordinates of bars located within that area (you can use these coordinates as identifiers and implement them through nested structures of coordinates); see this answer for an example: ethereum.stackexchange.com/questions/7180/… . For calling external contracts from a contract you need to have both a sufficient balance assigned to the calling contract (cont'd). – Sebi Oct 17 '16 at 15:17
  • 1
    (cont'd) as well as the addresses of the callee contracts (the ones that contain geographical areas). You can use an address array for each area contract. The syntax for invoking a method in a remote contract is detailed in this answer: ethereum.stackexchange.com/questions/2876/… – Sebi Oct 17 '16 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.