[OT] Best algorithm for extremely large hashtable?

[John Colvin]

On Friday, 15 November 2013 at 20:07:24 UTC, H. S. Teoh wrote:
> On Fri, Nov 15, 2013 at 08:48:19PM +0100, John Colvin wrote:
>> On Friday, 15 November 2013 at 18:43:12 UTC, H. S. Teoh wrote:
>> >so the edges of the graph may be thought of as a subset of the
>> >edges of an n-dimensional grid.
>> 
>> Could perhaps elaborate on this point?
>> 
>> As far as I can see, the possible values of the nodes are all 
>> the
>> points in N^n (or Z^n, dunno whether you have negatives) and 
>> the
>> edges are all in the set of i*e_j for i in Z and j in N, where 
>> e_j
>> is the unit vector along one axis, i.e. the edges are the 
>> euclidean
>> basis vectors and their negatives.
>
> Actually, i can only be 1 or -1.
>
>
>> How is this the same as the edges of an n-dimensional grid?
>
> Basically, adjacent nodes differ only in a single coordinate, 
> and that
> difference can only be 1 or -1.

Ah, ok.

> So for the 2D case, if you graph the
> nodes on the plane, the edges would be horizontal/vertical line 
> segments
> of unit length. If you consider the 2D grid's edges to be *all* 
> possible
> such line segments, then in that sense you could think of the 
> graph's
> edges as being a subset of the 2D grid's.

If you're going to chuck away the orthogonal location of the 
edges and only consider parallel position then you might as well 
go all the way:

In the 2-D example, the edges are all +/-(0,1) and +/-(1,0). 
There's no difference between the edge connecting (x, p) to (x, 
p+1) and the edge connecting (x, q) to (x, q+1). In the general 
case there's only 2N possible unique edges.