Open Research Problem

Όπως κάθε μέρα σχεδόν - αυτό το εξάμηνο που έχω μπλέξει με το hiring committee - , έτσι και η σημερινή πήγε υπερ πίστεως. Μια από τις "extra-curriculum" δραστηριότητες που μου έφαγε μιάμιση ώρα ήταν η ομιλία του Muthu Muthukrishnan από την Google. Αφού μίλησε για την όμορφη κι ωραία δουλειά του πάνω σε e-auctions στο τέλος έθεσε ένα από τα πολλά open problems που έχουν στη Google και το μεταφέρω κι εγώ εδώ με τη σειρά μου για όποιον ενδιαφέρεται.

Το πρόβλημα έχει ως εξής. Ας υποθέσουμε ότι έχουμε έναν γράφο πολλαπλών ακμών (multigraph). Ένα τέτοιο παράδειγμα ας πούμε είναι τα blogs. Κάθε blogger είναι ένας κόμβος που συνδέεται με άλλους κόμβους (άλλους bloggers). Ορισμένοι από τους κόμβους του γράφου περιέχουν πληροφορίες, όπως για παράδειγμα την ηλικία του blogger, τα ενδιαφέροντά του κοκ., και κάποιοι άλλοι όχι. Το ερώτημα που τίθεται είναι πως μπορεί κανείς να συνάγει πληροφορίες για τους κόμβους του γράφου που είναι κενοί.

Μια απλή πρώτη λύση είναι το data fusion, δηλαδή π.χ. μπορεί κανείς να συμπεράνει την ηλικία κάποιου blogger παίρνοντας τον μέσο όρο των ηλικιών όλων των bloggers που συνδέονται μ'αυτον. Αυτή λύση βέβαια είναι υπεραπλουστευμένη και τα περιθώρια βελτίωσης είναι μεγάλα. Για παράδειγμα, θα μπορούσε κανείς να κοιτάξει τα ενδιαφέροντα αυτού του blogger και αν αυτά έχουν μεγάλες ομοιότητες με τα ενδιαφέροντα άλλων bloggers που έχουν δηλώσει την ηλικία τους να συμπεράνει την ηλικία του blogger μέσω αυτού του υποσυνόλου και όχι μέσω των άμεσων γειτόνων στον γράφο κ.ο.κ. Αν το καλοσκεφτεί κανείς, μοιάζει αρκετά με το διαγωνισμό της Netflix.

Start thinking!!