Μηχανές αναζήτησης

Η δομή μίας μηχανής αναζήτησης σε μία εικόνα

Επισκέπτες

• Υπεύθυνοι για την ανάκτηση εγγράφων από το διαδύκτιο
• Συνήθως συνεργάζονται πολλοι υπολογιστές παράλληλα ενώ κάθε υπολογιστής επισκέπτεται ταυτόχρονα πολλούς προορισμούς
• Τα ανακτημένα έγγραφα αποθηκεύονται και για κάθε ένα από αυτά δημιουργείται ένα άθροισμα ελέγχου
• Στρατηγικές επανεξέτασης
  • Κάθε έγγραφο επανεξετάζεται με την ίδια συχνότητα
  • Κάθε έγγραφο επανεξετάζεται σύμφωνα με τον ρυθμό που ανανεώνεται
  • Έγγραφα που δεν ανανεώνονται συχνά δεν εξετάζονται συχνά, έγγραφα που ανανεώνονται συνεχώς δεν εξετάζονται καθόλου, έγγραφα που ανανεώνονται συχνά εξετάζονται συχνά
• Στρατηγικές επίσκεψης
  • Εκκίνηση από τυχαία έγγραφα
  • Εκκίνηση από "σημαντικά" έγγραφα

Ταμιευτήρας εγγράφων

• Αποθηκεύει συμπιεσμένα έγγραφα και αθροίσματα ελέγχου
• Μεγαλύτερη συμπίεση συνήθως σημαίνει μικρότερη ταχύτητα
• Το Google προτιμάει το γρηγορότερο zlib που δινει συμπίεση 3:1 από το bzip2 θα έδινε 4:1 αλλά είναι πολύ πιο αργό

  Μηχανή αναζήτησης	Αριθμός διαθέσιμων εγγράφων
  Google	> 4,2 δις
  AllTheWeb	> 3,1 δις

Δημιουργός ευρετηρίου

• Υπεύθυνος για την δημιουργία του αντεστραμένου ευρετηρίου και του ταμιευτήρα συνδέσμων
• Ανάλυση εγγράφων και διαχωρισμός σε όρους (λέξεις) από τις οποίες προκύπτει το αντεστραμένο ευρετήριο
  • Οι όροι μπορεί να απλοποιηθούν πριν την αποθήκευση τους, π.χ. κεφαλαία σε μικρά
  • Από έναν όρο μπορεί να προκύψουν περισσότερες από μία καταχωρήσεις, π.χ. U.S.A. → [U.S.A., USA] ή on-line → [online, on, line, on-line]
• Ανάκτηση συνδέσμων και αποθήκευση τους στον ταμιευτήρα συνδέσμων

Αντιστραμμένο ευρετήριο

• Αποθηκεύει τις εξής πληροφορίες για κάθε όρο:
  • Συχνότητα εμφάνισης του όρου σε κάθε έγγραφο
  • Σχετικότητα του όρου με κάθε έγγραφο στο οποίο συναντάται
  • Τοποθεσία του ορου σε κάθε έγγραφο στο οποίο συναντάται
• Συνήθως η σχετικότητα ενός όρου με ενα έγγραφο υπολογίζεται ως εξής: TF * log(IDF) [cf. Salton]
  • TF = συχνότητα εμφάνισης του όρου στο συγκεκριμένο έγγραφο
  • IDF = αντιστραμμένη συχνότητα εγγράφου ως προς τον όρο = συνολικος αριθμός εγγράφων / αριθμός εγγράφων που περιέχουν τον όρο
  • Aν έχουμε 1000 έγγραφα και ο όρος εμφανίζεται σε 950 από αυτα τοτε log(1000/950) = 0.02
  • Aν έχουμε 1000 έγγραφα και ο όρος εμφανίζεται σε 50 από αυτα τοτε log(1000/5) = 2.3
  • Ο υπολογισμός αυτός διακρίνει όρους με μεγάλη συχνοτητα σε λίγα έγγραφα

Ταμιευτήρας συνδέσμων

• Για κάθε έγγραφο καταχωρεί:
  • Τους συνδέσμους που οδηγούν σε αυτό το έγγραφο
  • Τους συνδέσμους που οδηγούν σε άλλα έγγραφα
  • Το κείμενο των συνδεσμων
• Στατιστικά τα οποία είναι χρήσιμα για των προσδιορισμό "σημαντικών" σελίδων ανεξαρτήτως των όρων αναζήτησης

Βαθμολογητής εγγράφων

• Βαθμολόγηση με βάση τις αναφορές
  • Αν ένα έγγραφο έχει πολλούς εξωτερικούς συνδέσμους που οδηγούν σε αυτήν τότε μπορούμε να πούμε πως είναι "αυθεντία" σε κάποιο θέμα
  • Αν ένα έγγραφο περιέχει πολλούς συνδέσμους που οδηγούν σε "αυθεντίες" τότε είναι σημαντικός κόμβος
• Βαθμολόγηση με βάση την πιθανότητα επίσκεψης
  • 'Ένας επισκέπτης που ξεκινάει από ένα τυχαίο έγγραφο και ακολουθεί τυχαίους συνδέσμους έχει μεγαλύτερη πιθανότητα να φτάσει σε κάποια έγγραφα από ότι σε κάποια άλλα
• PageRank
  • Ο αλγόριθμος που χρησιμοποιεί το Google
  • P(A) = (1-d) + d(P(T1)/C(T1) + ... + P(Tn)/C(Tn))
  • P(A): PageRank της σελίδας A
  • PC(Ti): Ο αριθμός εξερχομένων συνδέσμων της σελίδας Ti
  • d: Μια σταθερά μεταξύ 0 και 1 που αντιπροσωπεύει την πιθανότητα ο χρήστης να συνεχίσει την πλοήγηση του ακολουθώντας ακόμη έναν σύνδεσμο

Μηχανή αναζήτησης

• Δέχεται ως ερώτηση ένα συνδιασμό όρων
• Συνδιάζει την ανέξαρτητη βαθμόλογια κάθε εγγράφου που περιέχει όλους τους όρους με την βαθμολογία κάθε όρου σε κάθε έγγραφο που παρουσιάζεται
• Συνήθως δεν είναι γνωστο πώς γίνεται αυτός ο συνδιασμός
• Παρουσιαζει τα έγγραφα ανάλογα με την βαθμολογία τους

Ποσοτική αποτίμηση

• Ακρίβεια
  • Από το σύνολο των εγγράφων που επέστρεψε η μηχανή αναζήτησης πόσα είναι σχετικά;
  • Πιθανόν τα σχετικά έγγραφα να παρουσιάζονται πρώτα και τα άσχετα τελευταία οπότε μπορεί η μικρή ακρίβεια να μην είναι μεγάλο πρόβλημα
• Κάλυψη
  • Από το σύνολο των σχετικών εγγράφων πόσα επέστρεψε η μηχανή αναζήτησης;
  • Δύσκολο έως αδύνατο να υπολογίσουμε τον αριθμό των όλων σχετικών εγγράφων

Αποτίμηση μηχανών αναζήτησης

• Ταχύτητα απάντησης
• Χαλασμένοι σύνδεσμοι
• Πολλαπλές όμοιες απαντήσεις
• Σχετικά αποτελέσματα μέσα στην πρώτη σελίδα αποτελεσμάτων
• Ειδικές κατηγορίες χρηστων: άτομα με ειδικές αναγκες, ηλικιωμένοι

Διαχωρισμός σε συστοιχίες

• Προϋπόθεση: παρόμοια έγγραφα έχουν παρόμοια λεξικά ιστογράμματα
• Ιεραρχικός διαχωρισμός σε συστοιχίες
  • Ξεκινάμε υπολογίζοντας τις ομοίοτητες των εγγράφων ανά δύο
  • Διαλέγουμε τα δύο έγγραφα με την μέγιστη ομοιότητα και δημιουργούμε μια συστοιχία
  • Συνεχίζουμε συγκρινοντας έγγραφα και συστοιχίες μεταξύ τους
• Επαναληπτικός (ευρετικός) διαχωρισμός σε συστοιχίες
  • Ξεκινάμε με κάποιες συστοιχίες
  • Συγκρίνουμε κάθε έγγραφο με όλες τις συστοιχίες και αν η ομοιότητα του με κάποια από αυτές ξεπερνάει ένα επιλεγμένο όριο το τοποθετούμε εκεί
  • Γρήγορη μέθοδος αλλά με μικρότερη ακρίβεια
• Χρήσεις
  • Μετά απο μία αναζήτηση: διαχωρισμός των αποτελεσμάτων σε συστοιχίες με βάση την μεταξύ τους ομοιότητα
  • Πριν την αναζήτηση: αναζήτηση σε μια απο τις συστοιχίες με βαση την ομοίοτητα της ερώτησης με τις υπάρχουσες συστοιχίες

Ομαδοποίηση

• Με βάση μία υπάρχουσα ιεραρχία από κατηγορίες (π.χ. Yahoo) σε ποιά κατηγορία ανήκει ένα συγκεκριμένο έγγραφο;

Εκεί όπου οι μηχανές αναζήτησης δεν φτάνουν

• Οι μηχανές αναζήτησης βλέπουν λιγότερο από 1% των διαθέσιμων εγγράφων
• Παραδείγματα:
  • Βάσεις δεδομένων
  • Μικρές αγγελίες
  • Πληστειριασμοί
  • Oι εκδόσεις του μεγαλύτερου εκδότη παγκοσμίως, της Αμερικανίκης κυβέρνησης, δεν ειναι προσβάσιμες μεσω των μηχανών αναζήτησης

Οι μεγαλύτεροι σε βάθος δικτύακοι τόποι

• Σύμφωνα με την Brightplanel Corporation

  Name	Type	Web Size (GBs)	Rec Num (000)
  National Climatic Data Center (NOAA)	Public	366,000	41,012,794
  NASA EOSDIS	Public	219,600	24,607,676
  National Oceanographic (combined with Geophysical) Data Center (NOAA)	Public/Fee	32,940	3,691,151
  Alexa	Public (partial)	15,860	1,777,221
  Right-to-Know Network (RTK Net)	Public	14,640	1,640,512
  MP3.com	Public	4,300	481,844

Αναζήτηση εικόνων με βάση τα συμφραζόμενα

• Έτσι δουλεύουν οι περισσότερες μηχανές αναζήτησης
• Αναζητούμε τις λέξεις κλειδία:
  • στο τμήμα alt="" της εικόνας
  • στις λέξεις κοντά στην εικόνα
  • στο όνομα του αρχείου

Αναζήτηση εικόνων με βάση το περιεχόμενο

• Χρησιμοποιούμε χαρακτηριστικά της εικόνας όπως
  • η τοποθέτεση των απεικονισθέντων αντικειμένων στον χώρο και η σχετική τους διάταξη (πιθανώς αργή αναζήτηση)
  • το χρωματικό ιστόγραμμα (γρηγορότερη αναζήτηση)

Αναζήτηση σε ομότιμα δίκτυα

• Μη αυστηρώς δομημένα δίκτυα
  • Gnutella (BFS)
  • Freenet (DFS)
  • Δυνατότητα αναζήτησης με βάση το κλειδί του υπό αναζήτηση αντικειμένου (πχ όνομα αρχείου) αλλά και ένα μέρος του περιεχομένου (πχ MP3 info)
  • Μη αποδοτική αναζήτηση, δίχως εγγυήσεις ως προς την εύρεση αντικειμένων ακόμη και αν αυτά είναι διαθέσιμα
  • Βελτιστοποίηση της μεθόδου επιλογής κόμβων για την δρομολόγηση της ερώτησης με βάση κριτήρια όπως ο αριθμός και η ποιότητα των αποτελεσμάτων τους σε προηγούμενες αναζητήσεις, η ταχύτητα απάντησης, κτλ.
  • Εναλλακτική λύση η δημιουργία τοπικών υπέρ-κόμβων που μπορούν να απαντήσουν ερωτήσεις εκ μέρους όλων των κόμβων που απέχουν N βήματα
• Αυστηρώς δομημένα δίκτυα
  • Chord
  • CAN
  • Tapestry
  • Kademlia
  • Κάθε αντικείμενο έχει μία (ή παραπάνω) προσδιορισμένη θέση στο δίκτυο ανάλογα με τις ιδιότητες του
  • Η ανάκτηση οποιοδήποτε αντικειμένου υπάρχει στο δίκτυο είναι εγγυημένη μέσα σε ένα οριοθετημένο αριθμό βημάτων
  • Η αναζήτηση με βάση το περιεχόμενο είναι δυσκολότερη και δεν παρέχεται εγγενώς
    • Τοπικό ευρετήριο, μεγάλο κόστος για την επικοινωνία με όλους τους κόμβους του δικτύου
    • Καθολικό ευρετήριο, μεγάλο κόστος για τον συνδυασμό αποτελεσμάτων

Περαιτέρω μελέτη

• Automatic text processing, Gerald Salton
• The Anatomy of a Large-Scale Hypertextual Web Search Engine, Sergey Brin and Lawrence Page (http://www7.scu.edu.au/programme/fullpapers/1921/com1921.htm)
• The PageRank Citation Ranking: Bringing Order to the Web. Page, Lawrence; Brin, Sergey; Motwani, Rajeev; Winograd, Terry (http://dbpubs.stanford.edu/pub/1999-66)
• Estimating the Usefulness of Search Engines, Weiyi Meng and King-Lup Liu and Clement T. Yu and Wensheng Wu and Naphtali Rishe (http://csdl.computer.org/comp/proceedings/icde/1999/0071/00/00710146abs.htm)
• Risks of Quantitative Studies, Jakob Nielsen (http://www.useit.com/alertbox/20040301.html)
• The Cluster-Abstraction Model: Unsupervised Learning of Topic Hierarchies from Text Data, Thomas Hofmann (http://www.cs.brown.edu/~th/papers/Hofmann-IJCAI99.pdf)
• Deep Web White Paper (http://brightplanet.com/technology/deepweb.asp)
• VisualSEEk: a fully automated content-based image query system, John R. Smith and Shih-Fu Chang (http://www.ctr.columbia.edu/~jrsmith/html/pubs/acmmm96/acmfin.html)
• The State Hermitage Musuem: QBIC Colour and Layout Searches (http://www.hermitagemuseum.org/fcgi-bin/db2www/qbicSearch.mac/qbic?selLang=English)

• Περιεχόμενα

 Τελευταία αλλαγή: Τετάρτη, 2 Ιουνίου 2004 12:58 πμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».Η σελίδα αυτή γράφτηκε από τον Γιώργο Ζέρβα