Database Reference
In-Depth Information
Fig. 8.5
Average precision
rate, obtained for different
numbers of clusters,
k
,fora
query
Fig. 8.6
Total number of
images to be searched as a
function of
k
In order to find the successor of a given key, each node has a routing table called a
finger table.
The finger table has multiple columns; two of them represent the target
key and the successor of the target key. The target key at row
i
is
N
2
i
−
1
, where
N
is the current node. Figure
8.7
shows an example of nodes with the finger tables on
the identifier space of size 2
5
. The table size is a maximum of
m
rows, and the first
row (
i
+
1) gives the node successor. In addition, the table also has a predecessor
node ID that is used to identify the node previous to the current node.
To find the successor of a key, the system performs the
lookup
operation, as
outlined in Fig.
8.8
. If the node is responsible for the key, it returns its own ID;
otherwise, it needs to help other nodes find the predecessor of a key. The node
firstly searches its finger table to find another node that is closer to the predecessor
node than itself. It then passes the duty of finding the predecessor node to the other
node. The task is forwarded from node to node until the predecessor node of the
=
Search WWH ::
Custom Search