Previous work: Plaxton trees
Distributed tree structure where every node is the root of a tree
Simple mapping from object ID to root ID of the tree it belongs to
Nodes keep “nearest” neighbor pointers differing in 1 ID digit
- Along with a referrer map of closest referrer nodes
Insertion:
- Insert object at local node
- Proceed to root node hop by hop
- Leave back-pointers to object at each hop
Benefits:
- Decouples tree traversal from any single node
- Exploits locality with short-cutting back-pointers
- Guaranteed # of hops O(Log(N)) where N = size of namespace
- Query:
- Proceed to root node hop by hop
- If intersect node w/ desired back-pointer, follow it
- If root or best approximate node reached and no pointer to object, then it has not been inserted