Topics in Database Systems: Data Management in Peer-to-Peer Systems
      		   Fall Semester 2006
----------------------------------------------------------------------

			ASSIGNMENT 4
	       	      Due: Nov 22, 2006
                      (Unstructured P2P)

Σε ομάδες έως 3 άτομα.


Διαβάστε το άρθρο για τα Routing Indexes και το άρθρο των Lv et al
έως και το section 4.

1. Μελετήστε τους Πίνακες 2-5 στο paper των Lv. 
Προτείνετε την "καλύτερη" μέθοδο αναζήτησης για κάθε τοπολογία και
συνδυασμό query/replication. Εξηγείστε πως ορίζετε εσείς τι σημαίνει
"καλύτερη" και γιατί.

Οι δύο παρακάτω ερωτήσεις αφορούν το paper σε Routing Indexes.

2. Εξηγείστε πως τα HRIs θα δούλευαν σε ένα grid και σε ένα power-law:
(i) Ποια θα ήταν μια καλή τιμή για τον ορίζοντα;
(ii) Το μέγεθος των HRI θα ήταν ομοιόμορφο;
(iii) Πόσο ποιο γρήγορη θα ήταν η αναζήτηση από το να μην είχαμε
καθόλου RI;
Θεωρείστε ομοιόμορφη κατανομή για τα δεδομένα και τις ερωτήσεις σε
αυτά και δύο περιπτώσεις:
ότι (α) κάθε δεδομένο βρίσκεται στο 1% και (β) στο 10% των κόμβων. 

3. Ορίστε ένα ERI για ένα grid και για ένα power-law, δηλαδή
εξηγείστε ποιο μοντέλο κόστους θα χρησιμοποιούσατε για να μειώσετε την
επίδραση μακρυνών κόμβων.