[erlang-questions] Getting attributes

Anthony Molinaro anthonym@REDACTED
Mon Oct 15 21:15:37 CEST 2012


On Sat, Oct 13, 2012 at 06:38:32PM -0500, Steve Davis wrote:
> I understated the issue:
> 
> The position of the entity can also change: 
> {id, {x,y}, attribute}
> 
> So, in fact, the id is the only constant and the pos and attribute are independently mutable.
> 
> 
> 
> On Oct 13, 2012, at 6:23 PM, Steve Davis <steven.charles.davis@REDACTED> wrote:
> 
> > Hi all,
> > 
> > Suppose I have a 2 dimensional plane {x, y} of 64k by 64k coordinates.
> > 
> > Each coordinate has a mutable attribute {{x, y}, attribute}
> > 
> > If I need to query: What are the attributes of positions "next to" my position, i.e: x +- 1, y +- 1?
> > 
> > What is the correct solution to this without storing everything in "Oracle" and using relational queries?
> > 
> > Can this be sensibly maintained in a KV store?

This problem reminds me of one I had to do to map latitude and longitude
to location, then look up the closest location based on the latitude and
longitude of an input.

I used an ordered_set ets table inserting records like

{Latitude, Longitude, Record}

Then when looking things up given an input latitude and longitude, I would
add/subtract a small number of degrees to the input to get a range of
latitudes and longitudes.

Then query ets first using ets:prev/2 with the input latitude and walking
down by repeatedly calling ets:prev/2 until I either hit the start of the
table or the lower bound on the latitude.

You then do the same with ets:next/2 to the upper bound and
finally ets:lookup/2 in case its an exact match.

I would pass the upper and lower bound of the longitude along so I could
filter out things out of range as I was walking through the latitudes.

I've got about 60000 entries in the ets table and queries take about
0.085 milliseconds on average.  I found that using ets:prev/2 and ets:next/2
was much faster than say ets:match with a matchspec to do the range
checking.  I've also got another ordered_set table with 11 million entries
which I don't do range checks but just an ets:prev/2 and an ets:lookup/2
and that runs even faster (average about 0.010 millis per pair of calls).

Unfortunately the code is not shareable, but its relatively straightforward
so shouldn't be hard to recreate.

Good Luck,

-Anthony

-- 
------------------------------------------------------------------------
Anthony Molinaro                           <anthonym@REDACTED>



More information about the erlang-questions mailing list