Oskar wrote:
> The only (possible) solution I have come up with to the problem is
the sexy
> but probably impossibly impractical idea that the answer to the
question:
> "What can find the closest key fast having only a closeness
relation between
> them?" is, of course, Freenet - so the DataStore ADT should be
modeled as a
> Freenet microcosmos within each node (with each node unit in the
microcosmos
> having a datastore small enough for linear searches). If somebody
has a better
> idea I would be VERY interested.
This doesn't seem that impractical to me, actually. Not a full
mini-freenet implementation, but an optimized mini-network. Imagine a
bi-directional graph where each node is a single key structure. In
addition to the elements you need (key, address of a node, reference
to actual data stored) you also have a list of nodes to which this
node is the "nearest" you know about (using whatever closeness
relation is appropriate).
Performing a lookup is done by choosing any random node (better:
having N random root nodes, linearly looking at them, and starting
with the nearest to the key you are looking for). Then you linearly
look at each neighbor of that node and move towards whichever one is
closest to the key you are looking for. Repeat as neccesary until you
find the key you are looking for, or there is no nearer key.
To perform an insertion, you find the nearest key (as above), make a
link from the nearest key to your new key structure, then iterate
over the links in the nearest key, moving the link to your new key
structure if the new key is nearer than the old nearest key.
For a single dimensional keyspace (like lexicographic nearness) this
results in a nearly linear search (each key structure will have at
most two neighbors - the graph will be a long doubly-linked list, so
the only advantage you have over linear is starting randomly and
moving in the right direction). Obviously this sucks compared to a
lexicographically ordered tree structure. However, the higher the
dimensionality of the key space, the more efficient this data
structure becomes, and it is exactly what you are looking for: you
can find the closest key fast given only a closeness relation.
--Greg
_______________________________________________
Freenet-dev mailing list
Freenet-dev at lists.sourceforge.net
http://lists.sourceforge.net/mailman/listinfo/freenet-dev
