Ανάκτηση Πληροφορίας — Φεβρουάριος 2021 (Ομάδα 8)¶
themata8.pdf¶
ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ ΚΑΙ ΠΛΗΡΟΦΟΡΙΚΗΣ ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΑΣ ΑΝΑΚΤΗΣΗ ΠΛΗΡΟΦΟΡΙΑΣ ΕΞΕΤΑΣΕΙΣ ΦΕΒΡΟΥΑΡΙΟΥ 2021 Διδάσκων: [όνομα παραλείπεται] ΔΙΑΡΚΕΙΑ 1:30 (ΟΜΑΔΑ 8)
ΘΕΜΑ 1 ( Μονάδες 3.5 )¶
α.Λόγω του μεγάλου όγκου δεδομένων που έχουν να χειριστούν οι μηχανές ψαξίματος στον παγκόσμιο ιστό, συχνά διατηρούν δύο ανεστραμμένα αρχεία, ένα που περιέχει πληροφορία για όλα τα κείμενα και αποθηκεύεται στο δίσκο και ένα μικρότερου μεγέθους που περιέχει ένα υποσύνολο της συνολικής πληροφορίας και αποθηκεύεται στην κύρια μνήμη. Τα δύο αυτά ανεστραμμένα αρχεία λειτουργούν με τη λογική ότι σε δοθέν ερώτημα, πρώτα θα ερωτηθεί η δομή στην κύρια μνήμη και αν η απάντηση δεν είναι ικανοποιητική θα ερωτηθεί και η δομή στον δίσκο. Προτείνετε πολιτικές δημιουργίας και ενημέρωσης της δομής ανεστραμμένων αρχείων της κύριας μνήμης, υποθέτοντας ότι η μηχανή ακολουθεί ένα συνδυασμό μοντέλου διανυσματικού χώρου, και μίας link μετρικής (ανεξάρτητης περιεχομένου), στη βαθμολόγηση των ιστοσελίδων.
β. Καταγράψτε τους βασικούς αλγορίθμους συμπίεσης ανεστραμμένων αρχείων, και συγκρίνετέ τους μεταξύ τους.
ΘΕΜΑ 2 ( Μονάδες 3.5 )¶
α. Θεωρώντας ότι ο αριθμός των επιστρεφόμενων κειμένων είναι 30, θεωρήστε τις ακόλουθες δύο μηχανές που απαντάνε στο ίδιο ερώτημα (δίνονται ο αριθμός των σχετικών κειμένων και η θέση τους στο αποτέλεσμα) :
Μηχανή1 Αριθμός: 10, Θέση: 1, 3, 6, 9, 13, 18, 24, 25, 27, 30 Μηχανή2 Αριθμός: 10, Θέση: 1, 2, 3, 7, 10, 19, 22, 26, 27, 30. Θεωρήστε ότι οι εμπειρογνώμονες εκτός από το αν ένα κείμενο είναι σχετικό ή όχι δίνουν και βαρύτητα σχετικότητας : 1 (αρκετά σχετικό), και 2 (πολύ σχετικό), και υποθέστε ότι στις δύο ανωτέρω μηχανές συμβαίνει κατά την ανάκτηση τα πέντε πρώτα σχετικά κείμενα να έχουν βαρύτητα σχετικότητας 2, και τα επόμενα έχουν βαρύτητα σχετικότητας 1.
ΣΥΓΚΡΙΝΕΤΕ ΤΙΣ ΔΥΟ ΜΗΧΑΝΕΣ χρησιμοποιώντας τη μετρική NDCG¶
(ξεκινήστε να υπολογίζετε τον τύπο, και φθάστε το μέχρι το σημείο που μπορεί να γίνει η σύγκριση).
β. Εξηγήστε πως ο αλγόριθμος βαθμολόγησης σελίδων Pagerank του Google και HITS του CLEVER μπορεί να επεκταθεί έτσι ώστε να ενσωματώνει πληροφορίες σχετικά με τη δεδομένα κίνησης πληροφορίας στο διαδίκτυο και προσπελασιμότητας των ιστοσελίδων από τους χρήστες.
ΘΕΜΑ 3 ( Μονάδες 3)¶
Υποθέστε ότι το γράφημα του Web είναι αποθηκευμένο στον δίσκο ενός υπολογιστικού συστήματος, με τη μορφή ενός σύνολου adjacency lists (λίστες γειτνιάσεως) που είναι βασικά λίστες που περιέχουν για κάθε κορυφή v του
γραφήματος τη λίστα των άμεσα προσβάσιμων κορυφών από τον κόμβο v . Με τον τρόπο αυτό μπορούμε να ρωτήσουμε για τους γείτονες που έχει ένας συγκεκριμένος κόμβος και να τους προσπελάσουμε σαν μία λίστα ΑΜΕΣΑ από τον δίσκο. α. Περιγράψτε τα βασικά βήματα του αλγόριθμο που υπολογίζει το PageRank στο σενάριο αυτό.
β. Υποθέστε ότι σε κάθε σελίδα απεικονίζουμε ένα ακέραιο αριθμό από 1 έως Ν ( Ν το πλήθος των σελίδων). Πως μπορεί να συμπιεστεί η αναπαράστασή μας του γραφήματος στο σχήμα αυτό;
γ. Εξηγήστε γιατί η λεξικογραφική διάταξη των αλφαριθμητικών των URLs των σελίδων και η ανάθεση αύξοντων αριθμών σε αυτές οδηγεί σε καλή συμπίεση του γραφήματος.
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash, gemini-3.7-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-02-h¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
α. Η δομή στην κύρια μνήμη πρέπει να λειτουργεί ως “πρώτο επίπεδο”/cache του πλήρους δίσκου. Επειδή η βαθμολόγηση συνδυάζει VSM και μία link μετρική ανεξάρτητη περιεχομένου, προτείνονται συνδυαστικά: - Page-centric πολιτική: κρατάμε στη μνήμη πλήρεις καταχωρίσεις (terms/postings) για σελίδες με υψηλή στατική σημαντικότητα, π.χ. υψηλό PageRank/HITS, υψηλή επισκεψιμότητα, χρήσιμες/δημοφιλείς σελίδες. Έτσι, αν ένα ερώτημα τις “πιάνει”, η απάντηση από τη μνήμη είναι ήδη ποιοτική ως προς το link score. - Term-centric πολιτική: για δημοφιλείς όρους/ερωτήματα αποθηκεύουμε τις κορυφαίες \(K\) καταχωρίσεις της posting list κατά σύνθετο score, π.χ. κατά \(w_{t,d}\cdot L(d)\), όπου \(L(d)\) η link μετρική. Οι σπάνιοι όροι ή οι ουρά της posting list μένουν στον δίσκο. Έτσι η μνήμη επαρκεί για έγκαιρη επιστροφή των πιθανών top-k αποτελεσμάτων. - Query-log driven πολιτική: χρησιμοποιούμε logs για να προβλέψουμε ποιοι όροι/queries θα ζητηθούν και κρατάμε caching με LRU/LFU. Η μνήμη ερωτάται πρώτα· αν επιστρέψει αρκετά αποτελέσματα και το κάτω φράγμα βαθμολογίας του top-k δεν μπορεί να βελτιωθεί από τον δίσκο, σταματάμε· αλλιώς συμπληρώνουμε/ελέγχουμε τον δίσκο. - Ενημέρωση: περιοδική ανακατασκευή/merge από το πλήρες index μετά από αλλαγές link scores, περιοδική ανανέωση των δημοφιλών queries, σταδιακή (incremental) εισαγωγή νέων/αλλαγμένων σελίδων, lazy updates με generations, και eviction σελίδων/όρων με χαμηλή χρησιμότητα. Αν μια σελίδα αποκτήσει υψηλό link score ή συχνή πρόσβαση, προβιβάζεται στη μνήμη· αν πέσει, διαγράφεται/αντικαθίσταται.
β. Βασικές κατηγορίες/αλγόριθμοι συμπίεσης ανεστραμμένων αρχείων: - Συμπίεση λεξικού: front coding/prefix compression, καθώς οι όροι είναι ταξινομημένοι και μοιράζονται προθέματα. - Συμπίεση posting lists: αποθήκευση docIDs ως διαφορών (d-gaps) και κωδικοποίηση των διαφορών με unary, Elias gamma/delta, Golomb/Rice, variable-byte (VByte), byte/word-aligned κώδικες (π.χ. Simple-9, PForDelta), run-length/intervals για συνεχόμενες θέσεις. - Σύγκριση: το unary είναι απλό και καλό μόνο για πολύ μικρά gaps· οι Elias \(\gamma/\delta\) είναι universal χωρίς παραμέτρους αλλά σχετικά αργοί στην αποκωδικοποίηση· Golomb/Rice είναι πολύ αποδοτικοί για γεωμετρική κατανομή gaps αλλά απαιτούν παράμετρο· VByte είναι γρήγορο και εύκολο με μέτρια συμπίεση· word-aligned/PForDelta προσφέρουν μεγάλη ταχύτητα αποκωδικοποίησης και καλή συμπίεση με μεγαλύτερη πολυπλοκότητα· front coding μειώνει πολύ το λεξικό αλλά απαιτεί σειριακή αποκωδικοποίηση. Γενικά επιλέγεται συμβιβασμός συμπίεσης–ταχύτητας: Golomb/Elias για χώρο, VByte/PForDelta για γρήγορη ανάκτηση.
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
α. Χρησιμοποιώ τον συνήθη ορισμό [ DCG@30=\sum_{i=1}^{30}\frac{2^{r_i}-1}{\log_2(i+1)}, ] όπου \(r_i\in\{0,1,2\}\) η βαρύτητα σχετικότητας στη θέση \(i\). Η ιδανική διάταξη βάζει πρώτα τα πέντε έγγραφα βαθμού \(2\) και μετά τα πέντε βαθμού \(1\), άρα [ IDCG@30 =3\left(1+\frac1{\log_2 3}+\frac1{\log_2 4}+\frac1{\log_2 5}+\frac1{\log_2 6}\right) +\left(\frac1{\log_2 7}+\frac1{\log_2 8}+\frac1{\log_2 9}+\frac1{\log_2 10}+\frac1{\log_2 11}\right) \approx 10.4405. ]
Μηχανή 1: σχετικά στις θέσεις \(1,3,6,9,13,18,24,25,27,30\), με τα πέντε πρώτα σχετικά (θέσεις \(1,3,6,9,13\)) βαθμού \(2\) και τα υπόλοιπα βαθμού \(1\): [ DCG_1= \frac3{\log_2 2}+\frac3{\log_2 4}+\frac3{\log_2 7}+\frac3{\log_2 10}+\frac3{\log_2 14} +\frac1{\log_2 19}+\frac1{\log_2 25}+\frac1{\log_2 26}+\frac1{\log_2 28}+\frac1{\log_2 31} \approx 8.3330. ] Άρα [ NDCG_1=\frac{DCG_1}{IDCG@30}\approx \frac{8.3330}{10.4405}\approx 0.7981. ]
Μηχανή 2: σχετικά στις θέσεις \(1,2,3,7,10,19,22,26,27,30\), με τα πέντε πρώτα σχετικά (θέσεις \(1,2,3,7,10\)) βαθμού \(2\) και τα υπόλοιπα βαθμού \(1\): [ DCG_2= \frac3{\log_2 2}+\frac3{\log_2 3}+\frac3{\log_2 4}+\frac3{\log_2 8}+\frac3{\log_2 11} +\frac1{\log_2 20}+\frac1{\log_2 23}+\frac1{\log_2 27}+\frac1{\log_2 28}+\frac1{\log_2 31} \approx 9.3326. ] Άρα [ NDCG_2=\frac{DCG_2}{IDCG@30}\approx \frac{9.3326}{10.4405}\approx 0.8939. ] Επομένως η Μηχανή 2 είναι καλύτερη ως προς NDCG@30, γιατί τοποθετεί περισσότερα έγγραφα υψηλής βαρύτητας σε πρώιμες θέσεις.
β. Το PageRank μπορεί να επεκταθεί σε “weighted random surfer”: οι πιθανότητες μετάβασης \(P_{uv}\) από τη σελίδα \(u\) στη \(v\) δεν είναι ομοιόμορφες, αλλά ανάλογες με πραγματικά δεδομένα κίνησης/πλοήγησης (clicks, transitions από logs), με ομαλοποίηση ώστε να παραμένει στοχαστικός πίνακας. Η τηλεμεταφορά/διάνυσμα επανεκκίνησης \(e\) μπορεί να είναι ανάλογο της πραγματικής εισόδου χρηστών, της επισκεψιμότητας, των bookmarks και της προσπελασιμότητας των σελίδων, π.χ. [ r=(1-d)e+dP^{T}r, ] όπου \(P\) περιέχει και βάρη από logs και \(e\) ευνοεί προσβάσιμες/δημοφιλείς σελίδες. Σε HITS, τα authority/hub scores μπορούν να υπολογιστούν σε σταθμισμένο γράφημα, [ a(v)\propto\sum_{u\to v}w_{uv}h(u),\qquad h(u)\propto\sum_{u\to v}w_{uv}a(v), ] με τα \(w_{uv}\) να ενσωματώνουν συχνότητα πλοήγησης/κλικ, ενώ αρχικοποίηση ή κανονικοποίηση με βάση traffic/accessibility ευνοεί σελίδες που πραγματικά επισκέπτονται και προσεγγίζουν οι χρήστες.
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
α. Έστω \(N\) το πλήθος σελίδων και \(d_v\) το out-degree της \(v\). Για PageRank με απόσβεση \(d\), αρχικοποιούμε \(r_0(v)=1/N\). Σε κάθε επανάληψη: 1. Υπολογίζουμε τη μάζα των dangling κόμβων \(S=\sum_{v:d_v=0}r_t(v)\). 2. Διαβάζουμε από τον δίσκο τις adjacency lists. Για κάθε κόμβο \(v\) με \(d_v>0\), υπολογίζουμε τη συνεισφορά \(c=d\cdot r_t(v)/d_v\) και, για κάθε γείτονα \(u\) στη λίστα του \(v\), γράφουμε ένα ζεύγος \((u,c)\) σε προσωρινό αρχείο/partition. 3. Αθροίζουμε τις συνεισφορές ανά προορισμό \(u\), είτε με εξωτερική ταξινόμηση/merge είτε με hash partitioning και τοπική άθροιση. 4. Υπολογίζουμε [ r_{t+1}(u)=\frac{1-d}{N}+\frac{dS}{N}+\sum_{v\to u}\frac{d\,r_t(v)}{d_v}, ] γράφουμε το νέο διάνυσμα στον δίσκο και επαναλαμβάνουμε μέχρι \(\|r_{t+1}-r_t\|_1<\varepsilon\). Για ταχύτητα, το γράφημα τεμαχίζεται σε blocks/partitions, το διάνυσμα ranks κρατείται στη μνήμη αν χωράει, και αν είναι δυνατόν κατασκευάζονται και αντίστροφες λίστες εισερχόμενων ακμών ώστε κάθε κόμβος να υπολογίζει απευθείας το άθροισμα των εισερχόμενων συνεισφορών.
β. Αφού οι σελίδες αριθμούνται \(1,\dots,N\), αποθηκεύουμε κάθε adjacency list ταξινομημένη αύξουσα. Αντί για απόλυτα IDs, αποθηκεύουμε τις διαφορές (gaps) [ u_1,\quad u_2-u_1,\quad u_3-u_2,\dots ] και κωδικοποιούμε τις διαφορές με μεταβλητού μήκους κώδικες: unary για πολύ μικρά gaps, Elias \(\gamma/\delta\), Golomb/Rice, VByte ή byte/word-aligned μεθόδους. Για συνεχόμενες γειτονιές χρησιμοποιούμε intervals/run-length (π.χ. \([a,b]\) αντί για όλα τα IDs), και για παρόμοιες λίστες τεχνικές αναφοράς/αντιγραφής τμημάτων άλλων λιστών. Αποθηκεύεται χωριστά το out-degree κάθε κόμβου. Έτσι μειώνεται δραστικά το μέγεθος, επειδή πολλά gaps γίνονται μικρά.
γ. Η λεξικογραφική ταξινόμηση των URLs ομαδοποιεί σελίδες με κοινό πρόθεμα, δηλαδή ίδιο domain, κατάλογο ή παρόμοια διαδρομή, και η ανάθεση αύξοντων IDs τις τοποθετεί σε γειτονικές θέσεις. Επειδή οι σύνδεσμοι του Web είναι συχνά ενδο-τοπικοί (ίδιο site/domain ή σχετικές σελίδες), οι γειτονικές σελίδες ενός κόμβου τείνουν να έχουν κοντινά IDs. Τα ταξινομημένα neighbor lists έχουν τότε πολλά μικρά gaps ή συνεχόμενα διαστήματα, τα οποία συμπιέζονται πολύ καλά με delta/variable-length κώδικες και interval/reference μεθόδους. Γι’ αυτό η λεξικογραφική σειρά των URLs βελτιώνει την τοπικότητα και τη συμπίεση του γραφήματος.