[p2p-hackers] complexity theory for small world / shortcut based routing approaches

[Alexander Löser]

Hi,
DHT approaches provide a framework for deterministic query execution. 
E.g. most algorithm require O(logN) messages to route a query within a 
network of N peers.  Nowadays a new group of query routing algorithms 
[1,2,3,4]  is evolving. Based on an unstructured p2p network these 
algorithms cluster nodes with similar interests. In such algorithms each 
node recieving the message forwards it to one if its neighbors until the 
target is found or the maxium radius is reached. Based on the decision 
criteria they use in selecting a forwarding node, these algorithms can 
be categorized as follows:

* Degree based: The decision is based on the degree structure of 
neighboring nodes. E.g. Nodes with a high in and out degree are chosen.
* Simiraity based: The decision is based on how similar the neighboring 
nodes are to the target node in terms of attribute values. E.g., nodes 
having asked similar queries or providing similar content are chosen.

Using such navigation the overlays often have small world properties, 
e.g. a small average path length, a high clustering coefficient. 
However, calculating the algorithm complexity  for such overlays is 
still a hard problem. Does anybody know (academic or emperical) work, on 
how to estimate the algorithm complexity, e.g. O(N²), O(log N), O(N) 
....   ?

Best's Alex


[1] V. Cholvi, P. Felber, and E.W. Biersack. Efficient Search in
Unstructured Peer-to-Peer Networks.
[2] Adriana Iamnitchi, Matei Ripeanu and Ian Foster, Small World File
Sharing Communities.
[3] K. Sripanidkulchai. B. Maggs. H. Zhang. Efficient Content Location Using Interest Based Locality in
Peer-to-Peer Systems
[4] Searching dynamic communities with personal indexes.
A. Löser, C Tempich, B. Quilitz, W.T. Balke, S. Staab and W. Nejdl, ISWC '05



-- 
___________________________________________________________

  Alexander Löser
  Technische Universität Berlin
  http://cis.cs.tu-berlin.de/~aloeser/
  office : +49- 30-314-25551
  fax    : +49- 30-314-21601
___________________________________________________________