ΚΕΦΑΛΑΙΟ 4 Ανάκτηση μουσικής πληροφορίας σε εξειδικευμένα περιβάλλοντα

Τα ομότιμα δίκτυα μπορούν να κατηγοριοποιηθούν βάσει του ελέγχου στην τοποθεσία των δεδομένων και την τοπολογία του δικτύου σε μη δομημένα, χαλαρά δομημένα και δομημένα [152]. Τα μη δομημένα δεν ακολουθούν κάποιο κανόνα για την τοποθεσία αποθήκευσης των δεδομένων, ενώ η τοπολογία του δικτύου είναι τυχαία (λ.χ., Gnutella). Τα χαλαρά δομημένα ομότιμα δίκτυα έχουν τόσο την τοποθεσία αποθήκευσης όσο και την τοπολογία δικτύου μη επακριβώς προσδιορισμένη (λ.χ., Freenet). Τέλος, στα δομημένα η τοποθεσία αποθήκευσης καθώς και η τοπολογία δικτύου είναι ρητά καθορισμένες (λ.χ., Chord) παράμετροι. Επιπλέον, τα ομότιμα δίκτυα μπορούν να κατηγοριοποιηθούν βάσει του πλήθους των κεντρικών καταλόγων των τοποθεσιών αποθήκευσης των δεδομένων σε συγκεντρωτικά, υβριδικά και αποκεντρωμένα. Ακολούθως, τα συγκεντρωτικά δίκτυα διατηρούν ένα κεντρικό κατάλογο σε μια και μόνο τοποθεσία (λ.χ., Napster), τα υβριδικά περιλαμβάνουν περισσότερους από ένα σε υπερ-κόμβους (λ.χ., Kazaa) με καταλόγους, ενώ στα αποκεντρωμένα (λ.χ., Chord) δεν υπάρχει κεντρικός κατάλογος. Τέλος τα ομότιμα δίκτυα μπορούν επίσης να κατηγοριοποιηθούν σε ιεραρχικά και μη, βάσει του βαθμού ιεράρχησης της υποκείμενης δομής. Είναι σύνηθες για τα αποκεντρωμένα συστήματα να μην παρουσιάζουν ιεραρχικότητα, ενώ για τα υβριδικά και τα περισσότερα συγκεντρωτικά να συμπεριλαμβάνουν κάποιου βαθμού ιεράρχηση. Τα ιεραρχικά συστήματα παρέχουν αυξημένη ικανότητα αντιμετώπισης κλιμάκωσης, ευκολία στην εκμετάλλευση της ανομοιογένειας των κόμβων και υψηλή αποδοτικότητα δρομολόγησης. Αντιδιαμετρικά, τα μη ιεραρχικά συστήματα προσφέρουν αυξημένη εξισορρόπηση φόρτου και προσαρμοστικότητα στη συμμετοχή/αποχή κόμβων.

Στην ενότητα αυτή το δίκτυο που εξετάζεται θεωρείται αποκεντρωμένο, μη δομημένο και μη ιεραρχικό. Επιπλέον, γίνεται η υπόθεση ότι το δίκτυο αποτελείται από N κόμβους, ενώ κάθε κόμβος έχει κατά προσέγγιση $\log \text{N}$ γειτνιάζοντες κόμβους. Η διάμετρος του δικτύου είναι το μέγιστο πλήθος κόμβων που απαιτούνται ως ενδιάμεσοι ώστε να εντοπιστεί ο κόμβος P${}_j$ από τον P${}_i$. Ορίζεται MaxHop (μέγιστο πλήθος αλμάτων) το πλήθος των κόμβων στους οποίους ένα επερώτημα προωθείται. Το MaxHop ενός επερωτήματος έχει μια αρχική τιμή και κάθε φορά που το επερώτημα προωθείται σε ένα κόμβο, μειώνεται κατά μια μονάδα μέχρι να γίνει μηδενικό, από το οποίο σημείο και μετά το επερώτημα δεν προωθείται σε κόμβους. Η παράμετρος MaxHop εξίσου αποκαλείται και Time-To-Leave (TTL).

Στην ενότητα αυτή συνοψίζονται μερικές από της ήδη διαθέσιμες προσεγγίσεις έρευνας σε αποκεντρωμένα μη δομημένα ομότιμα δίκτυα. Αρχικά εξετάζεται ο αλγόριθμος έρευνας με προτεραιότητα πλάτους (Breadth-First Search - BFS). Στην περίπτωση του BFS, ο κόμβος Q που θέτει το επερώτημα, διαβιβάζει το επερώτημα q σε όλους τους γειτονικούς κόμβους. Κάθε κόμβος P που λαμβάνει το q αρχικά ερευνά τον τοπικό χώρο αποθήκευσης για δεδομένα που ταιριάζουν με το q και στη συνέχεια το προωθεί σε όλους τους γειτονικούς του κόμβους. Στην περίπτωση που ο P έχει κάποιο ταίριασμα από τον τοπικό χώρο αποθήκευσης τότε ένα μήνυμα QueryMatch δημιουργείται περιέχοντας πληροφορίες για το ταίριασμα. Κατόπιν, τα μηνύματα QueryMatch μεταδίδονται χρησιμοποιώντας το αντίστροφο μονοπάτι που ακολούθησε το q, στον Q. Τέλος, καθώς περισσότερα από ένα μηνύματα τύπου QueryMatch παραλαμβάνονται από τον Q, μπορεί να διαλέξει τον κόμβο με τα καλύτερα χαρακτηριστικά σύνδεσης ώστε να προσκομίσει άμεσα το ταίριασμα. Είναι προφανές ότι ο η τακτική του BFS βασίζεται στη θυσία της απόδοσης και του φόρτου του δικτύου με αντίτιμο την απλότητα του αλγορίθμου και τα υψηλά ποσοστά αποτελεσμάτων. Προσπαθώντας να περιοριστεί ο φόρτος του δικτύου, εισάγεται η παράμετρος TTL (βλ. ενότητα 4.1.1). Σε μια τροποποιημένη έκδοση του αλγορίθμου αυτού, ο τυχαίος BFS (Random BFS - RBFS) [137], ο κόμβος που θέτει το επερώτημα, Q, το διαβιβάζει σε ένα ποσοστό των γειτονικών κόμβων.

Προσπαθώντας να διορθωθεί η αδυναμία του RBFS να επιλέξει το μονοπάτι του δικτύου που οδηγεί σε μεγάλα τμήματα του δικτύου, οι συγγραφείς της εργασίας [170] ανάπτυξαν τον αλγόριθμο $>$RES. Στην προσέγγιση αυτή, ο κόμβος Q που θέτει το επερώτημα διαβιβάζει το επερώτημα q σε ένα υποσύνολο των γειτονικών του κόμβων βάσει συνολικών στατιστικών δεδομένων. Έτσι, ο Q διαβιβάζει το q σε k γειτονικούς κόμβους, οι οποίοι επέστρεψαν τα υψηλότερα ποσοστά αποτελεσμάτων κατά τα τελευταία m επερωτήματα, με τα k και m να είναι παράμετροι. Ο $>$RES αποτελεί μια σημαντική βελτίωση σε σύγκριση με τον RBFS, ωστόσο η συμπεριφορά του είναι περισσότερο ποσοτική παρά ποιοτική, καθώς δεν επιλέγει τους γείτονες στους οποίους θα προωθήσει το επερώτημα βάσει της ομοιότητας του περιεχομένου του q των προηγουμένων επερωτημάτων.

Με στόχο την αντιμετώπιση της ποσοτικής προσέγγισης του $>$RES, ο αλγόριθμος ISM προτάθηκε [137]. Στον ISM, για κάθε επερώτημα, κάθε κόμβος το προωθεί στους κόμβους που είναι περισσότερο πιθανόν να απαντήσουν βάσει δυο παραμέτρων: ένα σύστημα κατατομής και μια βαθμολόγηση σχετικότητας. Η κατατομή δημιουργείται και συντηρείται σε κάθε κόμβο για τους γειτονικούς του κόμβους. Οι πληροφορίες που περιλαμβάνονται στην κατατομή αυτή είναι τα t πιο πρόσφατα επερωτήματα με ταιριάσματα, τα ταιριάσματα τους αλλά και το πλήθος των ταιριασμάτων που ο γειτονικός κόμβος επέστρεψε. Η συνάρτηση βαθμολόγησης βάσει σχετικότητας (RR) υπολογίζεται συγκρίνοντας το επερώτημα q με όλα τα επερωτήματα για τα οποία υπάρχει ταίριασμα σε κάθε κατατομή. Κατά συνέπεια, για τον κόμβο $P_Q$ που θέτει το επερώτημα, η συνάρτηση RR υπολογίζεται βάσει της ακόλουθης σχέσης:

όπου Qsim είναι η συνάρτηση ομοιότητας που χρησιμοποιείται μεταξύ των επερωτημάτων ενώ S(P${}_i$,q${}_j$) είναι το πλήθος των αποτελεσμάτων που επιστρέφει ο P${}_i$ για το επερώτημα q${}_j$. Ο ISM επιτρέπει υψηλότερη βαθμολόγηση των γειτονικών κόμβων που επιστρέφουν περισσότερα αποτελέσματα με τη ρύθμιση της παραμέτρου $\alpha$. Εμφανώς, η καλύτερη απόδοση του ISM εμφανίζεται σε περιβάλλοντα όπου υφίσταται αυξημένος βαθμός τοπικότητας των δεδομένων.

Ο χώρος συγκερασμού της ΑΜΠΒΠ και των ομότιμων δικτύων, είναι ιδιαίτερα νέος καθώς η πρώτη εργασία δημοσιεύτηκε το έτος 2002 [167]. Ωστόσο, οι λιγοστές εργασίες παρουσιάζουν ενδιαφέροντα αποτελέσματα, τα οποία σχολιάζονται στη συνέχεια.

Στην πρώτη αυτή προσέγγιση, οι συγγραφείς της εργασίας [167] παρουσίασαν τέσσερα πρότυπα ομότιμων δικτύων για ΑΜΠΒΠ. Τα πρότυπα αυτά περιλαμβάνουν όλες τις κατηγορίες βάσει του πλήθους των κεντρικών καταλόγων των αποθηκευτικών χώρων (αποκεντρωμένα, υβριδικά και συγκεντρωτικά). Η εργασία προτείνει έναν αλγόριθμο επιτάχυνσης της ανεύρεσης που βασίζεται στη διαφορά του τονικού ύψους μεταξύ δύο νοτών καθώς και μια μέθοδο διήθησης των αποτελεσμάτων βασιζόμενη σε τεχνικές αφαίρεσης των επαναλήψεων. Επιπλέον, οι συγγραφείς της [167] προτείνουν μια αρχιτεκτονική για ΑΜΠΒΠ σε ομότιμα δίκτυα, η οποία κατατάσσεται στα υβριδικά συστήματα.

Μια ακόμα έρευνα βασιζόμενη σε ένα υβριδικό σχεδιασμό παρουσιάζεται στην εργασία [166]. Στην εργασία αυτή οι συγγραφείς προτείνουν ένα σύστημα που χρησιμοποιεί μεταδεδομένα (τραγουδιστής, συλλογή, τίτλος, συνθέτης, κλπ.) αλλά και χαρακτηριστικά που εξάγονται ώστε να περιγραφεί το περιεχόμενο ενός μουσικού κομματιού. Η προτεινόμενη τοπολογία δικτύου στην εργασία [166], βασίζεται στα συστήματα DHT. Στα συστήματα αυτά, σε κάθε κόμβο ανατίθεται μια περιοχή ενός εικονικού χώρου διευθύνσεων, ενώ σε κάθε διαμοιραζόμενο δεδομένο ανατίθεται μια τιμή από το χώρο διευθύνσεων αυτό. Συνεπώς, ο εντοπισμός ενός δεδομένου απαιτεί μόνο την ανεύρεση ενός κλειδιού, του κόμβου που έχει αναλάβει το αντίστοιχο κλειδί.

Οι συγγραφείς της εργασίας [172] πρότειναν τη χρήση της μεθοδολογίας εξαγωγής χαρακτηριστικών που προτείνεται στην εργασία [190] για ΑΜΠΒΠ σε αποκεντρωμένα μη δομημένα ομότιμα δίκτυα. Η εργασία αυτή εξετάζει την περίπτωση η βάση να είναι αντιγραμμένη αλλά και τη γενικότερη περίπτωση των ομότιμων δικτύων, ενώ ειδική προσοχή δίνεται στον έλεγχο του φόρτου εργασίας που δημιουργείται στους κόμβους κατά τη διάρκεια της επερώτησης. Κάθε επερώτηση χωρίζεται σε δύο φάσεις, η πρώτη από τις οποίες περιλαμβάνει μόνο ένα μέρος του επερωτήματος, ώστε να εντοπιστούν οι κόμβοι υψηλής πιθανότητας απάντησης. Στη συνέχεια, οι κόμβοι βαθμολογούνται και το πλήρες επερώτημα διαβιβάζεται σε όλους τους κόμβους. Δεδομένου ότι ένας κόμβος διαθέτει ελεύθερους πόρους CPU, αποφασίζει εάν θα επεξεργαστεί το επερώτημα βάσει της βαθμολογίας που έλαβε για το συγκεκριμένο επερώτημα. Είναι προφανές ότι αυτή η προσέγγιση προκαλεί αυξημένο φόρτο δικτύου, καθώς το πλήρες επερώτημα διαβιβάζεται σε όλους τους κόμβους, αντί των περισσότερα υποσχόμενων.

Τέλος, παρότι προσανατολισμένο σε διαφορετικό κλάδο, η εργασία [164] αναφέρεται στην ανάκτηση ακουστικών μουσικών δεδομένων σε ομότιμα δίκτυα. Ο κεντρικός στόχος της εργασίας αυτής είναι η καταπολέμηση της μη εξουσιοδοτημένης διάθεσης μουσικών αρχείων σε ομότιμα δίκτυα. Για να επιτύχει το στόχο αυτό, οι κόμβοι χωρίζονται σε ιεραρχικές ομάδες βάσει των πόρων τους, ενώ κάθε εργασία ανατίθεται σε πολλούς κόμβους ώστε να αντιμετωπιστεί η δυναμικότητα της συμμετοχής/αποχής κόμβων.

Όπως ήδη αναφέρθηκε, οι αλγόριθμοι έρευνας σε ομότιμα δίκτυα βασίζονται στην ακόλουθη διαδικασία: ο κόμβος που θέτει το επερώτημα εξετάζει το δικό του περιεχόμενο και αναφέρει τα δεδομένα που ικανοποιούν το επερώτημα. Στη συνέχεια, επιλέγει ένα σύνολο των γειτονικών του κόμβων και διαδίδει το επερώτημα. Κάθε κόμβος που το λαμβάνει, με τη σειρά του εξετάζει τα τοπικά δεδομένα και προωθεί το επερώτημα σε ένα σύνολο των γειτονικών του κόμβων. Προς αποφυγή ανάμειξης απαγορευτικά μεγάλου αριθμού κόμβων, η διάδοση του επερωτήματος περιορίζεται από την παράμετρο MaxHop, η οποία καθορίζει το πλήθος των κόμβων στους οποίους το επερώτημα πρέπει να διαδοθεί.

Εξαιτίας του επιλεγμένου πρότυπου ομοιότητας, η πληροφορία που διαδίδεται μεταξύ των κόμβων αποτελείται από τις ακολουθίες $U$ και $L$ της ακολουθίας του επερωτήματος (δηλ., οι φάκελοι του επερωτήματος). Κάθε κόμβος που λαμβάνει τις ακολουθίες αυτές υπολογίζει την τιμή του LB μεταξύ των δεδομένων του και των φακέλων. Όταν η τιμή του LB είναι μικρότερη από το κατώφλι ομοιότητας που έχει θέσει ο χρήστης, τότε η πραγματική ακολουθία του επερωτήματος μεταδίδεται στον κόμβο αυτό²²Το επερώτημα μπορεί να μεταδοθεί κατευθείαν από τον κόμβο που το έθεσε, εφόσον, ο τρέχων κόμβος γνωρίζει τη διεύθυνση του αρχικού. και η πραγματική DTW απόσταση υπολογίζεται μεταξύ του επερωτήματος και του αντίστοιχου δεδομένου.

Τα επερωτήματα που εξετάζονται αποτελούνται από μουσικές φράσεις, δηλαδή, τμήματα μουσικών κομματιών τα οποία αποτελούν έναν τύπο μουσικής μονάδας³³Το ελάχιστου μήκους τμήμα ενός μουσικού κομματιού που είναι νοηματικά αυτόνομο και πλήρες στο μουσικό κομμάτι από το οποίο προήλθε.. Το γεγονός αυτό είναι εμφανέστερο στα επερωτήματα με σιγο-τραγούδισμα (QBH), όπου οι χρήστες τείνουν να σιγο-τραγουδούν κομμάτια τα οποία (i) είναι σχετικά μικρά, και (ii) είναι εμφανώς αναγνωρίσιμα και διαχωρισμένα σε ένα τραγούδι. Η εύρεση των μουσικών φράσεων μπορεί να γίνει χρησιμοποιώντας τη μεθοδολογία που παρουσιάζεται στην εργασία [175]. Ειδικότερα, στην [145] παρουσιάζεται ένας αλγόριθμος μετατροπής ακουστικών δεδομένων σε συμβολικά. Τα χρονικά διάκενα, τα οποία αντιστοιχούν σε φράσεις στην τονική πληροφορία, εντοπίζονται μεταξύ των στιγμών όπου εμφανίζεται σιωπή (τα αντίστοιχα διάκενα διαχωρίζουν τις φράσεις και στις ακουστικές ακολουθίες). Συνοπτικά, ενδιαφερόμαστε στην ανεύρεση μουσικών δεδομένων τα οποία περιέχουν φράσεις όμοιες με μια ακολουθία επερωτήματος. Η ομοιότητα βάσει της απόστασης DTW είναι κατάλληλη στο πλαίσιο αυτό, καθώς οι ιδιότητες της βοηθούν στην αναίρεση λαθών που το σιγο-τραγούδισμα προκαλεί.

Μια σημαντική παρατήρηση είναι ότι τα ακουστικά δεδομένα τείνουν να είναι αρκετά μεγάλα όσο αφορά τον όγκο τους σε σχέση με τα συνήθη δεδομένα των ομότιμων δικτύων. Παρότι τα επερωτήματα αποτελούνται από μουσικές φράσεις (δηλ, τμήματα των μουσικών ακολουθιών), το πλήθος των στοιχείων σε μια φράση λίγων δευτερολέπτων μπορεί να είναι της τάξης των εκατοντάδων χιλιάδων. Το μήκος των ακολουθιών $U$ και $L$ είναι ίσο με το μήκος του επερωτήματος. Κατά συνέπεια, η άμεση προσέγγιση, που απευθείας διαδίδει τις ακολουθίες $U$ και $L$ μεταξύ των κόμβων, οδηγεί σε υπερβολικά μεγάλο φόρτο δικτύου. Επιπλέον, όταν το μήκος των ακολουθιών φακέλου είναι μεγάλο, ο υπολογισμός του LB σε κάθε κόμβο μπορεί να αποβεί ιδιαίτερα δαπανηρός. Οι συνέπειες αυτές παραβιάζουν τους περιορισμούς των ομότιμων δικτύων για όσο το δυνατό λιγότερη επεξεργαστική επιβάρυνση των κόμβων. Εδώ πρέπει να σημειωθεί ότι οι προαναφερμένοι περιορισμοί δεν υφίστανται σε διαφορετικά πεδία, όπως η έρευνα όμοιων δεδομένων κειμένου σε ομότιμα δίκτυα όπου τα επερωτήματα αποτελούνται από μερικές δεκάδες στοιχεία.

Ακολούθως, παρουσιάζεται μια μέθοδος που αντιμετωπίζει τα δυο προβλήματα και επιτυγχάνει σημαντική μείωση του φόρτου του ομότιμου δικτύου κατά τη διάρκεια ενός μουσικού επερωτήματος βάσει περιεχομένου. Η μέθοδος λειτουργεί ως εξής:

• •

  Μειώνει το μήκος των ακολουθιών φακέλου εφαρμόζοντας σε αυτές δειγματοληψία. Ωστόσο, η απλή δειγματοληψία μπορεί να μην αποδειχθεί αποδοτική, καθώς οδηγεί σε υποτίμηση του LB. Κατά συνέπεια, παρουσιάζεται μια μέθοδος δειγματοληψίας με στόχο τη μείωση του μήκους των ακολουθιών χωρίς σημαντική επιρροή στον υπολογισμό του LB. Επιπλέον, η μέθοδος εστιάζει στην αποφυγή εισαγωγής ψευδών αρνητικών ταιριασμάτων εξαιτίας της χρήσης της δειγματοληψίας.

• •

  Χρησιμοποιεί (οποτεδήποτε είναι εφικτό) μια συμπιεσμένη αναπαράσταση των δειγματισμένων ακολουθιών του φακέλου. Η αναπαράσταση αυτή αποτελεί ένα είδος συμπίεσης για τις ακολουθίες, ωστόσο, δεν επιβάλλει επιπλέον εργασιακό φόρτο στους κόμβους του ομότιμου δικτύου απαιτώντας αποσυμπίεση. Όμως, εάν το φόρτος αποσυμπίεσης δεν αποτελεί κώλυμα, επιπλέον συμπίεση είναι δυνατή με τη χρήση ήδη υπαρκτών μεθόδων⁴⁴Η κατεύθυνση αυτή δεν εξετάζεται καθώς δεν επηρεάζει τη σχετική απόδοση των μεθοδολογιών..

Στη συνέχεια, περιγράφονται τα προαναφερθέντα πλήρη λεπτομερειών.

Έστω ότι το μήκος της εξεταζόμενης φράσης είναι $N$. Το μήκος κάθε επερωτήματος $Q$ και κατά συνέπεια των άνω ($U$) και κάτω ($L$) ακολουθιών θα είναι επίσης $N$. Πρέπει να δειγματιστούν οι $U$ και $L$ έτσι ώστε να καταλήξουν σε δυο ακολουθίες $U^{\prime }$ και $L^{\prime }$, κάθε μία από τις οποίες θα είναι μήκους $M\ll N$. Αρχικά, εξετάζεται η ομοιόμορφη δειγματοληψία. Στην περίπτωση αυτή, απλά επιλέγεται κάθε φορά το $(i\times N/M)$-στο στοιχείο της $U$ και $L$, όπου $1\le i\le M$. Όταν υπολογίζεται το LB_Keogh μεταξύ της ακολουθίας επερωτήματος $Q$ και μιας ακολουθίας δεδομένων, θεωρείται κάθε φράση $C$ μήκους $N$ στο $Q$. Κάθε φράση πρέπει να δειγματιστεί όμοια με τις $U$ και $L$, δίνοντας τη δειγματισμένη φράση $C^{\prime }$. Συνεπώς, το κάτω όριο $L{B}^{\prime }$ υπολογίζεται ως εξής:

Στην εξίσωση αυτή, η τρίτη περίπτωση (δηλ., όταν $L_i^{\prime }\le C_i\le U_i^{\prime }$) δεν συνεισφέρει στον υπολογισμό του $L{B}^{\prime }$. Το πρόβλημα που παρουσιάζει η ομοιόμορφη δειγματοληψία είναι ότι, καθώς επιλέγει στοιχεία χωρίς κάποιο ιδιαίτερο κριτήριο, επιλέγει πολλά στοιχεία των $U$ και $L$ τα οποία οδηγούν στην τρίτη αυτή περίπτωση. Συνεπώς, το $L{B}^{\prime }$ υπολογίζεται ιδιαίτερα υποτιμημένο σε σύγκριση με την περίπτωση δίχως δειγματοληψία. Η υποτίμηση της τιμής του κάτω ορίου έχει ως αποτέλεσμα την αύξηση των ψευδών ταιριασμάτων, οι οποίοι προκαλούν αυξημένο φόρτο δικτύου.

Για την αντιμετώπιση του προβλήματος αυτού, απαιτείται μια εναλλακτική μέθοδος δειγματοληψίας. Δειγματίζονται οι $U$ και $L$ ξεχωριστά. Αρχικά, ταξινομούνται τα στοιχεία της $U$ σε αύξουσα διάταξη. Για την $U^{\prime }$ επιλέγονται τα πρώτα $M$ στοιχεία της διάταξης αυτής. Αντίστοιχα, ταξινομείται η $L$ σε φθίνουσα διάταξη και επιλέγονται τα πρώτα $M$ στοιχεία της για την $L^{\prime }$. Διαισθητικά, η επιλογή των $M$ μικρότερων τιμών της $U$, οδηγεί στην αύξηση των εμφανίσεων της πρώτης περίπτωσης (δηλ., όταν $C_i^{\prime }>U_i^{\prime }$), εφόσον όσο μικρότερες είναι οι τιμές της $U_i^{\prime }$, τόσο περισσότερο είναι αναμενόμενο να υφίσταται ένα $C_i^{\prime }$ μεγαλύτερο. Χρησιμοποιώντας συμβατική φρασεολογία, στόχος είναι η αύξηση της δειγματοληψίας από τις "γκρίζες" περιοχές (βλ. Σχήμα 4.3 της ενότητας 4.1.2). Ανάλογη μέθοδος εφαρμόζεται και για τη δειγματοληψία της $L^{\prime }$.

Είναι, κατά συνέπεια, εμφανή τα εξής:

Απόδειξη. Υπολογίζοντας το $L{B}^{\prime }$, εξαιτίας της δειγματοληψίας, οι δυο πρώτες περιπτώσεις της Εξίσωσης 4.4 παρουσιάζονται σπανιότερα από ότι κατά τον υπολογισμό του $LB$ (δηλ., χωρίς δειγματοληψία). Συνεπώς, $L{B}^{\prime }\le LB$. Εφόσον $LB\le D$ (όπου $D$ είναι η αντικειμενική απόσταση, υπολογισμένη με τη χρήση της DTW), συνεπάγεται ότι $L{B}^{\prime }\le D$. Έτσι, δεν προκαλούνται ψευδή αρνητικά.

Η ξεχωριστή δειγματοληψία των $U$ και $L$ παρουσιάζει την αναγκαιότητα για αποθήκευση των θέσεων από τις οποίες τα στοιχεία επιλέχθηκαν για τις $U^{\prime }$ και $L^{\prime }$. Εάν οι θέσεις αποθηκευτούν ρητά, τότε διπλασιάζεται ο όγκος της πληροφορίας που διατηρείται ($2M$ στοιχείων για την αποθήκευση των $U^{\prime }$ και $L^{\prime }$, και επιπλέον $2M$ στοιχεία για την αποθήκευση των θέσεων των επιλεγμένων στοιχείων). Καθώς οι πληροφορίες αυτές μεταδίδονται κατά το επερώτημα, αυξάνεται ο φόρτος του δικτύου, για την αποφυγή του οποίου προτείνεται μια εναλλακτική αναπαράσταση. Για την αναπαράσταση της $U^{\prime }$, χρησιμοποιείται ένα πίνακας bit μήκους $N$ (ίσο με το μήκος της φράσης). Κάθε bit αντιστοιχεί σε ένα στοιχείο της $U$. Για κάθε στοιχείο που επιλέγεται για το δειγματισμό στην $U^{\prime }$, το bit του γίνεται ίσο με τη μονάδα, ενώ εναλλακτικά έχει μηδενική τιμή. Κατά συνέπεια, για την αναπαράσταση της $U^{\prime }$ χρησιμοποιούνται ο συνδυασμός του πίνακα bit και οι $M$ τιμές που επιλέχθηκαν για την $U^{\prime }$. Όμοια μέθοδος χρησιμοποιείται και για την $L^{\prime }$. Η αποδοτικότητα της αναπαράστασης γίνεται εμφανής από το χώρο που απαιτεί για την $U^{\prime }$ ο οποίος είναι $M+\lceil N/8\rceil$ bytes.⁵⁵Κάθε στοιχείο μιας ακουστική μουσικής ακολουθίας, για την αναπαράσταση MIDI, έχει τιμή στο διάστημα 0-255, και συνεπώς απαιτεί μόνο ένα byte. Η απλοϊκή αναπαράσταση απαιτεί $5M$ bytes (καθώς χρειάζεται μόνο ένα ακέραιο, δηλ., 4 bytes, για την αποθήκευση τη θέση κάθε επιλεγμένου στοιχείου). Κατά συνέπεια, η μέθοδος αυτή πλεονεκτεί όταν , δηλ., για δείγματα μεγαλύτερα από 3%.

Όπως ήδη περιγράφθηκε, ο απλούστερος αλγόριθμος αναζήτησης είναι βάσει της έρευνας με προτεραιότητα πλάτους. Ο προσαρμοσμένος αλγόριθμος, που χρησιμοποιεί την προαναφερθείσα δειγματοληψία και μέθοδο αναπαράστασης, ονομάζεται BFSS (Breadth-First-Search with Sampling). Ο ψευδο-κώδικας του BFSS δίνεται στο Σχήμα 4.4. Κάθε φορά, εξετάζεται ο τρέχων κόμβος $n$. Η μεταβλητή TTL υποδηλώνει τις διαθέσιμες επανεκπομπές που διαθέτει ο $n$, ενώ, η $T_s$ είναι το κατώφλι ομοιότητας που έθεσε ο χρήστης. Θεωρούμε πως οι ακολουθίες $U^{\prime }$ και $L^{\prime }$ επίσης μεταφέρουν και τους αντίστοιχους πίνακες bit.

Προφανώς, η διάδοση της πραγματικής ακολουθίας επερωτήματος από τον κόμβο που ξεκίνησε το επερώτημα στον τρέχων κόμβο, αυξάνει το φόρτο του δικτύου (καθώς το επερώτημα δεν έχει υποστεί δειγματοληψία, η ακολουθία επερωτήματος έχει πολύ μεγάλο μήκος). Για το λόγο αυτό, είναι ιδιαίτερα σημαντικό να εμφανίζεται μικρός αριθμός ψευδών ταιριασμάτων.

Είναι πιθανό ότι η έκδοση του αλγορίθμου που δεν περιλαμβάνει δειγματοληψία (ονομασμένη ως BFS) θα προκαλέσει μικρότερο αριθμό ψευδών ταιριασμάτων, ωστόσο, μεταξύ κάθε ζευγαριού κόμβων πρέπει να διαβιβαστούν οι ακολουθίες $U$ και $L$, με μήκος ίσο της ακολουθίας επερωτήματος. Είναι λοιπόν εμφανές, ότι υφίσταται μια αντιστάθμιση μεταξύ του πλήθους των επιπλέον ψευδών ταιριασμάτων που προκαλούνται από τη δειγματοληψία και της μείωση του φόρτου δικτύου από τη μετάδοση των δειγματισμένων (δηλ., μικρότερων) φακέλων.

Ο αλγόριθμος $>$RESS προσπαθεί να μειώσει το πλήθος των μονοπατιών τα οποία εξετάζονται κατά τη διάρκεια της αναζήτησης. Αντί της τυχαίας επιλογής ενός υποσυνόλου των γειτονικών κόμβων του τρέχοντος κόμβου, διατηρεί μια κατατομή για κάθε τέτοιο κόμβο και βασίζει την επιλογή του στην κατατομή αυτή. Ειδικότερα, κάθε κόμβος διατηρεί για καθένα από τους γειτονικούς του κόμβους το πλήθος των θετικών αποτελεσμάτων που έδωσε. Στη συνέχεια, επιλέγει τους $k$ κόμβους που έδωσαν τις περισσότερες απαντήσεις κατά τη διάρκεια των τελευταίων $m$ επερωτημάτων. Οι μεταβλητές $k$ και $m$ ορίζονται από το χρήστη.

Είναι προφανές ότι ο αλγόριθμος $>$RES μπορεί εύκολα να προσαρμοστεί στο πλαίσιο αποτελεσματικής ανάκτησης. Η ακολουθία επερωτήματος θα δειγματιστεί και θα αναπαρασταθεί σύμφωνα με την προαναφερθείσα μέθοδο. Οι δυο μεταβολές αυτές δεν επηρεάζουν τις κατατομές που διατηρεί ο $>$RES. Η μέθοδος που προκύπτει ονομάζεται $>$RESS ($>$RES with sampling). Ο ψευδο-κώδικας της μεθόδου $>$RESS δίνεται στο Σχήμα 4.5.

Καθώς μόνο ένα υποσύνολο των κόμβων εμπλέκονται στη διαδικασία, ο $>$RESS προσπαθεί να μειώσει το φόρτο δικτύου αποφεύγοντας να χάσει μεγάλο αριθμό απαντήσεων. Ωστόσο, συγκρινόμενος με τον BFSS, ο $>$RESS αναμένεται να εντοπίσει λιγότερες απαντήσεις.

Ο αλγόριθμος ISM έχει τον ίδιο στόχο με τον $>$RES, δηλ., προσπαθεί να μειώσει το πλήθος των εξεταζόμενων μονοπατιών. Ωστόσο, η κατατομή που διατηρεί για κάθε κόμβο είναι διαφορετική. Ο ISM δεν βασίζει την απόφαση του μόνο στον αριθμό των απαντήσεων των προηγουμένων επερωτημάτων, αλλά επίσης εξετάζει την ομοιότητα μεταξύ των προηγούμενων επερωτημάτων και του τρέχοντος. Κατά συνέπεια, για κάθε γειτονικό κόμβο, κάθε κόμβος διατηρεί τα t πιο πρόσφατα επερωτήματα που απαντήθηκαν. Όταν ένα νέο επερώτημα $q$ διαβιβαστεί στον κόμβο, τότε υπολογίζεται η ομοιότητα του Qsim με όλα τα επερωτήματα που διατηρούνται στην κατατομή κάθε κόμβου. Ένα μέτρο βαθμολόγησης σχετικότητας δίνεται σε κάθε κόμβο $P_i$, χρησιμοποιώντας τον ακόλουθο τύπο:

όπου S(P${}_i$,q${}_j$) είναι το πλήθος των αποτελεσμάτων που επέστρεψε ο P${}_i$ για το επερώτημα q${}_j$. Συνεπώς, ο ISM βαθμολογεί υψηλότερα τους γειτονικούς κόμβους που επιστρέφουν περισσότερα αποτελέσματα με τη ρύθμιση της παραμέτρου $\alpha$. Για να γίνει η σύγκριση περισσότερο κατανοητή, ορίζεται η $\alpha$ ίση με τη μονάδα, και κατά συνέπεια το μέτρο εστιάζει μόνο στο κριτήριο της ομοιότητας. Πρέπει επίσης να επισημανθεί ότι ο ISM είναι πιθανό να παρουσιάσει μια προδιάθεση προς τους κόμβους οι οποίοι απάντησαν επερωτήματα περίπου όμοια, στο παρελθόν, μη δίνοντας έτσι την ευκαιρία σε νέους κόμβους να εξερευνηθούν. Για το λόγο αυτό, η ακόλουθη ευρεστική μέθοδος, όπως εφαρμόζεται και στην εργασία [137], ακολουθείται: εκτός των επιλεγμένων κόμβων βάσει των προαναφερθέντων κριτηρίων, ο ISM επίσης επιλέγει τυχαία ένα επιπλέον μικρό σύνολο κόμβων (λ.χ., ένα κόμβο). Συνολικά, $k$ κόμβοι επιλέγονται, όπου η παράμετρος $k$ ορίζεται από το χρήστη. Το μήκος κάθε κατατομής (ο αριθμός των επερωτημάτων που διατηρούνται στις κατατομές) ορίζεται επίσης από το χρήστη.

Για την προσαρμογή του ISM στο πλαίσιο αποτελεσματικής ανάκτησης, πρέπει να εξετάστεί το πώς θα διατηρηθούν τα προηγούμενα επερωτήματα. Στο πλαίσιο αυτό, οι ακολουθίες επερωτημάτων αναπαρίστανται από τις δειγματισμένες ακολουθίες τους. Συνεπώς, υπολογίζεται η ομοιότητα μεταξύ του δείγματος του τρέχοντος επερωτήματος και των δειγματισμένων ακολουθιών των προηγούμενων απαντημένων επερωτημάτων. Για το λόγο αυτό, στις κατατομές των κόμβων διατηρούνται οι δειγματισμένες ακολουθίες των απαντημένων επερωτημάτων. Για την εξοικονόμηση χρόνου κατά τη διάρκεια της βαθμολόγησης, αντί για τη μέτρηση της πραγματικής ομοιότητας (με τη χρήση του μέτρου DTW), υπολογίζεται το $LB\mathrm{\_}Keogh$. Ο αλγόριθμος που προκύπτει ονομάζεται ISMS (ISM with sampling), ενώ ο ψευδο-κώδικας του αλγορίθμου δίνεται στο Σχήμα 4.6.

Ο ISMS αναμένεται να έχει ελαφρά μεγαλύτερο φόρτο δικτύου από ότι ο $>$RESS εφόσον μεταδίδει τη δειγματισμένη ακολουθία των απαντημένων επερωτημάτων σε όλους τους κόμβους που συμμετέχουν στην έρευνα (ώστε να ενημερώσουν την κατατομή τους). Ωστόσο, ελέγχοντας το περιεχόμενο των επερωτημάτων, προσπαθεί να μειώσει τον αριθμό των χαμένων απαντήσεων.

Η έρευνα αυτή εστιάζει στην ανάπτυξη μεθόδων για αναζήτηση ακουστικής μουσικής βάσει περιεχομένου σε ΑΑΔ, όπου ο κόμβος που θέτει το επερώτημα λαμβάνει μουσικά αποσπάσματα τα οποία ταιριάζουν με το επερώτημα.

Η διαδικασία έρευνας μπορεί να εκμεταλλευτεί τις πρόσφατες προσεγγίσεις για ΑΜΠΒΠ σε ενσύρματα ομότιμα δίκτυα (βλ. ενότητα 4.2.2. Ωστόσο, ο συνδυασμός των χαρακτηριστικών του ασύρματου δικτύου και των ακουστικών μουσικών δεδομένων θέτουν νέες προκλητικές απαιτήσεις, οι οποίες απαιτούν και αντίστοιχες λύσεις:

1. 1.

   Οι μέθοδοι ΑΜΠΒΠ για ενσύρματα ομότιμα δίκτυα δεν εξετάζουν τη διαρκή μεταβολή της τοπολογίας του δικτύου, η οποία είναι εγγενής στα ΑΑΔ καθώς οι ασύρματοι ξενιστές (Mobile Hosts - MH, οι όροι MH και κόμβος είναι όμοιοι στην παρούσα ενότητα και κατά συνέπεια εναλλασσόμενοι) κινούνται εντός και εκτός του πεδίου των άλλων διαρκώς. Μια συνέπεια της κινητικότητας αυτής είναι ότι η επιλεκτική διάδοση ενός επερωτήματος σε MH, λ.χ., χρησιμοποιώντας μια δομή δεικτοδότησης όπως η DHT⁷⁷Distributed Hash Tables. Στα συστήματα αυτά κάθε κόμβος αναλαμβάνει μια περιοχή σε ένα εικονικό χώρο διευθύνσεων, ενώ σε κάθε μοιραζόμενο δεδομένο ανατίθεται μια τιμή από το χώρο αυτό. [120] όπως προτείνεται από την εργασία [166] ή η διαδικασία caching⁸⁸Ο όρος caching δεν έχει δόκιμο αντίστοιχο στην Ελληνική γλώσσα και για το λόγο αυτό παραμένει στο κείμενο στην Αγγλική. Στο παρόν έχει σημασία "αποθήκευσης". προηγούμενων επερωτημάτων ([137] για δεδομένα κειμένου και [140] μουσικά δεδομένα), δεν είναι δυνατή. Επιπλέον, η ανάκληση της διαδικασίας έρευνας επηρεάζεται από την πιθανότητα ανεπιτυχούς δρομολόγησης του επερωτήματος, αλλά και των απαντήσεων, λόγω της μεταβαλλόμενης τοπολογίας. Συνεπώς, απαιτείται ανάπτυξη κατάλληλων μεθόδων μετάδοσης του επερωτήματος στα ΑΑΔ.

2. 2.

   Μείωση του φόρτου δικτύου που βασίζεται στο μέγεθος των ακουστικών μουσικών δεδομένων (περίπου 8 mebibytes για 3 λεπτά επερωτήματος). Η μείωση αυτή είναι εφικτή αντικαθιστώντας το αρχικό επερώτημα με μια νέα αναπαράσταση η οποία χρησιμοποιεί μια καινούργια κατάλληλη μέθοδο μεταβολής μήκους του επερωτήματος. Παρότι ο φόρτος δικτύου επηρεάζει την ΑΜΠΒΠ σε ενσύρματα ομότιμα δίκτυα επίσης, το αίτημα μείωσης του φόρτου δικτύου στα ΑΑΔ είναι ιδιαίτερα πιο έντονο, καθώς η επικοινωνιακή ικανότητα περιορίζεται λόγω της συνήθως μικρότερης διαμεταγωγής των ασύρματων συνδέσεων. Στο σημείο αυτό είναι σημαντικό να αναφερθεί ότι η μείωση του φόρτου του δικτύου μειώνει επίσης και την ανάμειξη των άλλων MH, εξαιτίας περιορισμών στη χρήση των πόρων τους (λ.χ. επεξεργαστική ισχύ, αυτονομία, διαμεταγωγή).

3. 3.

   Στην ΑΜΠΒΠ σε ενσύρματα ομότιμα δίκτυα, μετά τον εντοπισμό ενός ταιριάσματος, μπορεί να επιστραφεί στον κόμβο που έθεσε το επερώτημα απευθείας, καθώς ο ερωτών κόμβος είναι άμεσα προσβάσιμος (μέσω της διεύθυνσης IP του). Σε αντίθεση, στα ΑΑΔ οι απαντήσεις του επερωτήματος πρέπει να μεταδοθούν στον ερωτώντα ξενιστή μέσω του δικτύου (ο κόμβος που έθεσε το επερώτημα δεν είναι άμεσα προσβάσιμος). Το αίτημα αυτό επιβαρύνει επιπλέον το φόρτο του δικτύου, απαιτώντας βελτιστοποίηση.

Τα προαναφερθέντα θέματα αντιμετωπίζονται, έως ένα βαθμό, από αλγόριθμους που προτάθηκαν για το πρόβλημα δρομολόγησης σε ΑΑΔ, παρότι δεν αντιμετωπίζουν ούτε τις ιδιαιτερότητες της έρευνας για ΑΜΠΒΠ ούτε το μέγεθος των μεταδιδόμενων δεδομένων, καθώς τα μουσικά δεδομένα είναι σημαντικά μεγαλύτερα από ότι τα συνήθη πακέτα.

Για την αντιμετώπιση των αιτημάτων που θέτει το ασύρματο μέσο, παρουσιάζονται οι ακόλουθες τεχνικές:

1. 1.

   Για το πρώτο αίτημα, εκτελείται μια έρευνα με προτεραιότητα πλάτους στο ΑΑΔ χρησιμοποιώντας πληροφορίες για τους γειτονικούς MH (τις πληροφορίες για τους γειτονικούς κόμβους τις αποκτά κάθε κόμβος εξετάζοντας τους γείτονες του ανά χρονικά διαστήματα). Η προσέγγιση αυτή αντιμετωπίζει επιτυχώς την κινητικότητα, διατηρεί υψηλή τελική ανάκληση και περιορίζει τα μειονεκτήματα της μεθόδου πλημμυρίσματος, λ.χ., υπερβολικός φόρτος δικτύου εξαιτίας καθολικών εκπομπών⁹⁹Περιγράφεται στην ενότητα 4.2.2. (broadcast).

2. 2.

   Το δεύτερο αίτημα αντιμετωπίζεται με μια τεχνική που χρησιμοποιεί μια συνοπτική, βασισμένη σε χαρακτηριστικά αναπαράσταση του επερωτήματος με μειούμενο μέγεθος. Η Αναπαράσταση του Επερωτήματος με το Μειούμενο Μέγεθος (ΑΕΜΜ) μειώνει δραστικά το φόρτο του δικτύου, μειώνοντας επίσης και τον επεξεργαστικό φόρτο σε κάθε MH.

3. 3.

   Ο επιπλέον φόρτος δικτύου που προκαλεί το τρίτο αίτημα αντιμετωπίζεται με μια διπλή μέθοδο: (i) χρήση πολιτικών για τον περιορισμό του πλήθους των MH που αναμειγνύονται στην μετάδοση των απαντήσεων, εκμεταλλευόμενοι MH που συμμετείχαν στην διάδοση του επερωτήματος, (ii) επιτρέπεται σε τέτοιους MH να μειώσουν την μετάδοση των απαντήσεων, βασιζόμενοι σε μια ιδιότητα της προαναφερθείσας αναπαράστασης.

Όπως προαναφέρθηκε, ένα κινητό ΑΔΔ (MANET) είναι μια συλλογή ασύρματων MH οι οποίοι σχηματίζουν ένα προσωρινό δίκτυο χωρίς τη βοήθεια κεντρικής διαχείρισης ή δεδομένων υπηρεσιών υποστήριξη που να είναι τακτικά διαθέσιμες στο ευρύτερο δίκτυο, στο οποίο οι ξενιστές είναι συνήθως συνδεδεμένοι. Όταν ένας κόμβος πηγή επιθυμεί να στείλει ένα μήνυμα σε ένα κόμβο προορισμό και δεν έχει ένα ισχύοντα δρόμο/μονοπάτι προς στον κόμβο προορισμό, αρχίζει μια διαδικασία ανεύρεσης μονοπατιού ώστε να εντοπίσει τον προορισμό. Εκπέμπει καθολικά αίτημα ανεύρεσης δρόμου στους γειτονικούς του κόμβους, το οποίο εκείνοι το προωθούν στους γειτονικούς τους κ.ο.κ. μέχρι ο κόμβος προορισμός ή κάποιος ενδιάμεσος κόμβος με δρόμο στον προορισμό να εντοπιστεί. Οι κόμβοι εντοπίζονται από τη διεύθυνση τους και διατηρούν μια ταυτότητα εκπομπής η οποία αυξάνεται μετά από κάθε αίτημα ανεύρεσης δρόμου που ξεκινούν. Η ταυτότητα εκπομπής συνδυασμένη με τη διεύθυνση, προσδιορίζει μοναδικά μια αίτηση ανεύρεσης δρόμου. Παρόμοια, οι αιτήσεις δεδομένων που εκπέμφθηκαν μπορούν να προσδιοριστούν.

Στα δίκτυα τύπου MANET δεν υπάρχει εκτεταμένη προηγούμενη ερευνητική εργασία για ΑΜΠΒΠ, παρότι υφίσταται μια πληθώρα αλγορίθμων δρομολόγησης, εκτός των [138], [141] στις και οποίες βασίζεται η παρούσα ενότητα.

Οι αλγόριθμοι δρομολόγησης για τα δίκτυα MANET είναι ριζικά διαφορετικοί από ότι στα παραδοσιακά πρωτόκολλα δρομολόγησης (λ.χ., προτεραιότητα συντομότερου ανοικτού μονοπατιού) και τα πρωτόκολλα εύρεσης πληροφορίας (λ.χ., κατανεμημένους πίνακες κατακερματισμού) που χρησιμοποιούνται σε ενσύρματα δίκτυα, εξαιτίας της απουσίας σταθερής υποδομής (εξυπηρετητές, σημεία πρόσβασης, δρομολογητές και καλώδια) στα MANET αλλά και της κινητικότητας των κόμβων. Για τα ΑΑΔ, προτάθηκαν [116] αρκετά πρωτόκολλα δρομολόγησης/ανεύρεσης που κατά προσέγγιση εμπίπτουν στις ακόλουθες κατηγορίες: α) βάσει πίνακα, β) κατά απαίτηση που ξεκινούν από την πηγή και γ) υβριδικά. Εκτός των πρώτων, τα οποία απαιτούν συνεπή ενημέρωση των δρόμων από κάθε κόμβο σε κάθε άλλο κόμβο του δικτύου, συνεπώς, καθιστώντας τα μη πραγματοποιήσιμα για μεγάλης κλίμακας δυναμικά MANET, οι υπόλοιπες δύο οικογένειες πρωτοκόλλων βασίζονται σε κάποια μορφή καθολικής εκπομπής. Η καθολική εκπομπή είναι η βέλτιστη λύση σε περιπτώσεις όπου πακέτα πληροφορίας μεταδίδονται σε πολλαπλούς ξενιστές στο δίκτυο. Η μέθοδος πλημμυρίσματος είναι η απλούστερη μορφή καθολικής εκπομπής, όπου κάθε κόμβος στο δίκτυο προωθεί το πακέτο πληροφορίας μια φορά ακριβώς. Το πλημμύρισμα εξασφαλίζει την πλήρη κάλυψη του MANET, εφόσον δεν υφίστανται κατατμήσεις του δικτύου, παρότι προκαλεί πολλές πλεονάζουσες εκπομπές, προκαλώντας το πρόβλημα της καταιγίδας καθολικών εκπομπών [157].

Πολλοί αλγόριθμοι προτάθηκαν [153] για την αντιμετώπιση του προαναφερθέντος προβλήματος. Οι λύσεις αυτές κατηγοριοποιούνται ως εξής: α) πιθανολογικές προσεγγίσεις (βασισμένες σε μετρητές, απόσταση και τοποθεσία) και β) αιτιοκρατικές προσεγγίσεις (καθολικές, φαινομενικά καθολικές, φαινομενικά τοπικές, τοπικές). Οι πρώτες μέθοδοι δεν εγγυώνται την πλήρη κάλυψη του δικτύου, ενώ οι τελευταίες την εγγυώνται, και κατά συνέπεια είναι προτιμώμενες.

Οι αιτιοκρατικές προσεγγίσεις παρέχουν πλήρη κάλυψη του δικτύου για τη λειτουργία καθολικής εκπομπής, επιλέγοντας μόνο ένα υποσύνολο των κόμβων για την μετάδοση των πακέτων (κόμβοι προώθησης), ενώ οι υπόλοιποι κόμβοι παραμένουν γειτονικοί στους κόμβους που προωθούν το πακέτο. Η επιλογή των κόμβων γίνεται χρησιμοποιώντας πληροφορίες "κατάστασης", όπως την τοπολογία δικτύου και την κατάσταση καθολικής εκπομπής (δηλ., τον επόμενο κόμβο που επιλέχθηκε να μεταδώσει το πακέτο, τους κόμβους που δέχτηκαν επίσκεψη πρόσφατα και το σύνολο των γειτονικών τους κόμβων). Όλες οι κατηγορίες των αιτιοκρατικών αλγορίθμων, εκτός των τοπικών αλγορίθμων, απαιτούν (πλήρεις ή μερικές) πληροφορίες καθολικής κατάστασης, κατά συνέπεια είναι μη πρακτικοί. Οι τοπικοί ή καταδεικτικοί γειτόνων αλγόριθμοι διατηρούν μερικές πληροφορίες τοπικής κατάστασης, δηλ., πληροφορία για την πρώτου επιπέδου γειτονιά μέσω ανταλλαγής μηνυμάτων τύπου ‘HELLO’, μια μέθοδος που είναι εφικτή και μη δαπανηρή. Στις μεθόδους κατάδειξης γειτόνων, η κατάσταση προώθησης ενός κόμβου εξαρτάται από τους γείτονες του. Στην πραγματικότητα, ο κόμβος πηγή επιλέγει ένα υποσύνολο των γειτόνων των κόμβων πρώτου επιπέδου του ως κόμβους προώθησης ώστε να καλύψει τους γείτονες δεύτερου επιπέδου του. Ο κατάλογος κόμβων προώθησης αυτός ενσωματώνεται στο πακέτο που εκπέμπεται. Κάθε κόμβος προώθησης με τη σειρά του καταδεικνύει το δικό του κατάλογο κόμβων προώθησης.

Αμυδρά σχετικό με το θέμα της παρούσας ενότητας είναι το ζήτημα της multicasting ροής δεδομένων (ήχος/κινούμενη εικόνα) σε MANET (λ.χ., [129]) ή της unicasting ήχου σε συσκευές 3G UMTS [163]. Ωστόσο, οι εργασίες αυτές υποθέτουν την ύπαρξη ενός κεντρικού εξυπηρετητή (παροχέας), ο οποίος παρέχει τους κινητούς πελάτες με πολυμεσικά δεδομένα και κατά συνέπεια δεν εμπίπτουν στο πλαίσιο του σεναρίου που πραγματεύεται η παρούσα ενότητα.

Μια από τις κυριότερες προκλήσεις στην ΑΜΠ είναι η επιλογή της αναπαράστασης της μουσικής πληροφορίας εντός των υπολογιστικών συστημάτων. Καθώς τα ακουστικά μουσικά δεδομένα τείνουν να είναι πολύ μεγάλα σε μέγεθος, περιγράφονται, συνήθως, από ένα σύνολο χαρακτηριστικών τους. Μια πληθώρα απόψεων υφίστανται όσο αφορά τα χαρακτηριστικά που πρέπει να επιλεχθούν [188]. Η επιλογή των κατάλληλων χαρακτηριστικών θεωρείται πολύ σημαντική στην ΑΜΠ [134]. Τα σημασιολογικά πλούσια χαρακτηριστικά υποβοηθούν στην αποδοτική αναπαράσταση των δεδομένων και επιτρέπουν τη χρήση καταλόγων για την αποδοτική επεξεργασία των επερωτημάτων.

Τα συνήθη χρησιμοποιούμενα χαρακτηριστικά για την αναπαράσταση ακουστικών δεδομένων παράγονται από ανάλυση στο πεδίο του χρόνου [182], [183], φασματική ανάλυση [182], [183], [181] και ανάλυση wavelet [187].

Η παρούσα ενότητα δεν επικεντρώνεται στη δημιουργία νέων χαρακτηριστικών. Αντ’ αυτού, επιδεικνύωει ενδιαφέρον στη μεθοδολογία της διαδικασίας ανεύρεσης καθώς η μέθοδος που παρουσιάζεται είναι σε θέση να συμπεριλάβει κάθε διαδικασία εξαγωγής χαρακτηριστικών υψηλής απόδοσης. Κατά συνέπεια, εφαρμόζεται μια μέθοδος εξαγωγής χαρακτηριστικών που βασίζεται στο μετασχηματισμό wavelet. Ο μετασχηματισμός wavelet παρέχει μια απλή και ταυτόχρονα αποδοτική αναπαράσταση των ακουστικών δεδομένων χρησιμοποιώντας τόσο την μη ομοιόμορφη ανάλυση συχνότητας όσο και τα ωστικά χαρακτηριστικά των δεδομένων αυτών, όπως δείχνουν οι εργασίες [124], [150], [151].

Ο μετασχηματισμός wavelet έχει επιτυχώς χρησιμοποιηθεί σε επεξεργασία εικόνων και σήματος, ενώ η χρήση του στους τομείς ανάκτησης πληροφορίας και εξόρυξης δεδομένων υπήρξε εκτενέστατη [154]. Μια πλήρης έρευνα στην εφαρμογή του μετασχηματισμού wavelet στην εξόρυξη δεδομένων δίνεται στην εργασία [150]. Γενικότερα, ο μετασχηματισμός wavelet είναι ένα εργαλείο που παρέχει ποιοτική ανάλυση χρονική και συχνότητας, ενώ διαιρεί τα δεδομένα σε διαφορετικά μέρη βάσει της συχνότητάς τους και επιτρέπει τη μελέτη κάθε μέρους με ανάλυση που ταιριάζει στην κλίμακά του [150], [127], [136].

Τα wavelets (προϊόντα του ομώνυμου μετασχηματισμού) παρουσιάζουν μια πληθώρα επιθυμητών ιδιοτήτων σε σχέση με άλλους τύπους ανάλυσης. Μεταξύ αυτών βρίσκονται και η αποδοτική πολυπλοκότητα υπολογισμού, οι εξαφανιζόμενες στιγμές που υποστηρίζουν την αφαίρεση θορύβου και μείωση των διαστάσεων ενώ παράλληλα εστιάζουν στη σημαντικότερη πληροφορία, την υποστήριξη συμπίεσης που εγγυάται την τοπικότητα του wavelet, τους μη συσχετισμένους συντελεστές που επιτρέπουν τη μείωση των πολύπλοκων διαδικασιών του χρονικού πεδίου σε απλουστέρα και την υποστήριξη του θεωρήματος του Parseval. Επιπλέον, τα wavelets παρουσιάζουν την ιδιότητα της πολλαπλής ανάλυσης η οποία οδηγεί σε ιεραρχική αναπαράσταση και χειρισμό των αντικειμένων που εξετάζουν.

Τα προαναφερθέντα προτερήματα του μετασχηματισμού wavelet, ενισχύουν τη χρήση των wavelets σε μουσικά δεδομένα. Η μειωμένη υπολογιστική πολυπλοκότητα βοηθά την ήδη βεβαρημένη επεξεργασία λόγω του μεγάλου μεγέθους των ακουστικών μουσικών δεδομένων. Οι εξαφανιζόμενες στιγμές και η ιδιότητα τους να μειώνουν το θόρυβο αντιμετωπίζουν το θόρυβο που εισάγεται στις μουσικές καταγραφές από τους ήχους του περιβάλλοντος, κατά τη διάρκεια της ηχογράφησης. Η υποστήριξη συμπίεσης επιτρέπει στα τοπικά αλλοιωμένα κομμάτια να διατηρήσουν την συνολική τους ομοιότητα, ενώ οι πολλαπλές αναλύσεις ταιριάζουν με το πρότυπο ακοής, σύμφωνα με το οποίο, η αντίληψη μεγάλων ποσοτήτων μικρής κλίμακας βασίζεται στην ικανότητα πολλαπλής ανάλυσης του αυτιού [124].

Ειδικότερα, προτείνεται ο μετασχηματισμός Haar wavelet λόγω του απλού σταδιακού υπολογισμού του, την ικανότητα του όσο αφορά τη σύλληψη των χρονικά εξαρτώμενων χαρακτηριστικών των δεδομένων και την συνολική δυνατότητά του πολλαπλής ανάλυση σημάτων [144]. Ωστόσο, η μέθοδος μπορεί εύκολα να συμπεριλάβει και άλλους τύπους μετασχηματισμών wavelet.

Για την βελτιστοποίηση της έρευνας στους κόμβους, χρησιμοποιείται η ακόλουθη διαδικασία. Σε έναν κόμβο, κάθε αρχική μουσική ακολουθία μετασχηματίζεται σε πολυδιάστατα σημεία. Με ένα ολισθαίνον παράθυρο μήκους $n$ επί της ακολουθίας και εφαρμόζεται ο μετασχηματισμός wavelet (Discrete Wavelet Transform - DWT) στα περιεχόμενα του κάθε παραθύρου, παράγοντας $n$ συντελεστές ανά παράθυρο. Ένα παράδειγμα δίνεται στο Σχήμα  4.8a. Συνεπώς, κάθε ακουστική ακολουθία παράγει ένα σύνολο $n$-διάστατων σημείων στο χώρο μετασχηματισμού. Καθώς ο αριθμός $n$ εξαρτάται στο μήκος του επερωτήματος και κατά συνέπεια έχει σχετικά μεγάλες τιμές (λ.χ., 64 K) ώστε να τα δεικτοδοτήσει στο χώρο μετασχηματισμού, προτείνεται η χρήση μόνο των πρώτων $d$ διαστάσεων από κάθε σημείο (στα πειράματά της εργασίας [138] χρησιμοποιήθηκε $d=64$). Η διαδικασία αυτή μειώνει δραστικά τόσο το μέγεθος του καταλόγου όσο και το πλήθος των διαστάσεων χωρίς να επηρεάζει ιδιαίτερα την ποιότητα του καταλόγου. Το γεγονός αυτό οφείλεται στο προτέρημα του DWT να συγκεντρώνει την ενέργεια της ακολουθίας στους πρώτους μερικούς συντελεστές. Ωστόσο, τα ψευδή θετικά αποτελέσματα παραμένουν πιθανά, και κατά συνέπεια απαιτούν επίλυση.

Είναι ιδιαίτερης σημασίας ότι αποδείχτηκε στην εργασία [126] ότι δεν υπάρχει πιθανότητα λανθασμένης απόρριψης ορθών αποτελεσμάτων χρησιμοποιώντας μόνο τους $d$ συντελεστές (εξαιτίας του θεωρήματος του Parseval). Στο σημείο αυτό πρέπει να αναφερθεί ότι η ιδιότητα αυτή αποδεικνύεται στην [126] για την Ευκλείδεια απόσταση. Παρότι το μέτρο απόστασης αυτό είναι απλό, είναι γνωστό για διάφορα προτερήματα του, όπως παρουσιάζονται στην εργασία [142]. Ωστόσο, η παρούσα μεθοδολογία δεν στηρίζεται αποκλειστικά στα συγκεκριμένα χαρακτηριστικά και μέτρο απόστασης, τα οποία χρησιμοποιούνται εδώ χάριν απλότητας και περιορισμένων επεξεργαστικών απαιτήσεων.

Για την αύξηση της ταχύτητας της ανάκτησης, για κάθε ακολουθία, το σύνολο των $d$-διάστατων σημείων που προκύπτουν οργανώνονται σε ελάχιστα περικλείοντα ορθογώνια (Minimum Bounding Rectangles - MBR), τα οποία, στη συνέχεια, αποθηκεύονται σε ένα R${}^{*}$-δένδρο [176]. Για την απάντηση ενός επερωτήματος, αρχικά εντοπίζεται η ρίζα της δενδρικής δομής και μόνο οι καταχωρίσεις της που διασταυρώνονται με το επερώτημα εξετάζονται περαιτέρω επαναληπτικά μέχρι να φτάσει η έρευνα σε φύλλο. Όλοι οι κόμβοι που δεν διασταυρώνονται δεν συμπεριλαμβάνονται στην έρευνα. Ένα παράδειγμα δίνεται στο Σχήμα 4.8b. Ακολούθως, κατά την έρευνα για όμοιες υποακολουθίες, αρχικά εντοπίζονται υποψήφιες από το R${}^{*}$-δένδρο. Οι υποψήφιες κατατάσσονται ώστε να εξεταστούν οι περισσότερο υποσχόμενες πρώτες (με τη μέθοδο αυτή εξοικονομούμε πόρους και χρόνο επεξεργασίας) και στη συνέχεια, οι υποψήφιες υποακολουθίες εξετάζονται σε σχέση με τη δοθείσα αναπαράσταση του επερώτηματος. Όταν η αναπαράσταση αυτή μειωθεί (όπως στην περίπτωση της μειούμενης αναπαράστασης η οποία θα εξηγηθεί στην συνέχεια), τα ψευδή θετικά παραμένουν πιθανά. Ωστόσο, το πλήθος τους μειώνεται σημαντικά. Περισσότερες λεπτομέρειες σχετικά με τη δεικτοδότηση μπορούν να βρεθούν στην εργασία [180].

Μια απλοϊκή προσέγγιση για την αναπαράσταση $R$ αποτελεί το να είναι όμοια με την ακολουθία επερωτήματος. Το κύριο πλεονέκτημα της περίπτωσης αυτής είναι ότι δεν θα προκύπτουν ψευδή θετικά αποτελέσματα, εφόσον, όταν ένα πιθανό αποτέλεσμα βρεθεί ερευνώντας τον κατάλογο, μπορεί άμεσα να εξεταστεί σε σχέση με το επερώτημα (δηλ., $R$). Συνεπώς, δεν θα υπάρχουν ψευδή θετικά αποτελέσματα, τα οποία επηρεάζουν αρνητικά το φόρτο δικτύου της φάσης επιστροφής καθώς θα επιστρέφονταν στον κόμβο που έθεσε το επερώτημα μόνο για να εξακριβωθούν ότι δεν είναι αληθινά ταιριάσματα. Πρέπει να σημειωθεί ότι, για να κάνουμε έρευνα του καταλόγου (δηλ., να αποφευχθεί η σειριακή έρευνα σε κάθε MH), ένας μικρός αριθμός συντελεστών DWT πρέπει να επίσης περιλαμβάνονται στην $R$. Ωστόσο, το μέγεθός τους είναι αμελητέο σε σχέση με το μέγεθος της ακολουθίας επερωτήματος.

Ο αλγόριθμος με αυτά τα χαρακτηριστικά ονομάζεται ML (full Maximum representation with Local resolution at MHs - πλήρης αναπαράσταση με τοπική επίλυση στους κόμβους). Ο ML συνοψίζεται στο Σχήμα 4.9 σύμφωνα με το πώς δρα σε κάθε εμφανιζόμενο γεγονός όπως αυτά συνοψίστηκαν για τη διαδικασία ανεύρεσης, στην ενότητα 4.2.3.

Παρότι ο ML καταφέρνει να κρατήσει ελεγχόμενο το φόρτο δικτύου κατά τη φάση επιστροφής (εξαιτίας της απομάκρυνσης των ψευδών θετικών αποτελεσμάτων), ο έλεγχος αυτός επιβαρύνει υπερβολικά το φόρτο δικτύου κατά τη φάση προώθησης. Το γεγονός αυτό οφείλεται στο ότι η αναπαράσταση $R$, η οποία μεταδίδεται κατά την φάση προώθησης, είναι ίση με το πλήρες επερώτημα. Για μεγάλες ακολουθίες επερωτήματος αυτό προκαλεί απαγορευτικό φόρτο δικτύου. Προφανώς, προκύπτει ένα θέμα συμβιβασμού μεταξύ των δύο φάσεων. Ακολούθως, απαιτείται μια μέθοδος η οποία θα εξισορροπεί το φόρτο δικτύου μεταξύ των δύο φάσεων, στοχεύοντας στη συνολική βελτίωση.

Ένα ακόμα ζήτημα στο οποίο ο ML λαμβάνει απλοϊκή απόφαση είναι η επιλογή των γειτονικών κόμβων στους οποίους το σύνολο των απαντήσεων προωθείται κατά τη φάση της επιστροφής. Αντιμετωπίζοντας τα γεγονότα δεύτερου και τρίτου τύπου, ο ML επιλέγει όλους τους γειτονικούς κόμβους για το σκοπό αυτό, καταφεύγοντας σε μέθοδο "πλημμυρίσματος". Η απλοϊκή επιλογή αυτή μπορεί να επηρεάσει σημαντικά το φόρτο δικτύου της φάσης επιστροφής. Για την αντιμετώπιση του προβλήματος αυτού απαιτείται η ανάπτυξη πολιτικών για την επιλεκτική δρομολόγηση των συνόλων απαντήσεων. Δηλαδή, πρέπει να επιλεγούν μόνο οι κόμβοι εκείνοι που είναι περισσότερο υποσχόμενοι να ικανοποιήσουν τη λήψη αποτελεσμάτων, συνεπώς μειώνοντας σημαντικά το φόρτο δικτύου στη φάση επιστροφής, χωρίς να μειώνεται η πιθανότητα του συνόλου απαντήσεων να επιστραφεί στον κόμβο που έθεσε το επερώτημα.

Στην ενότητα 4.2.5 έγινε προφανές ότι δημιουργείται ένας συμβιβασμός όσο αφορά το φόρτο δικτύου μεταξύ της φάσης προώθησης και επιστροφής. Ο αλγόριθμος ML εστιάζει μόνο στη βελτίωση του φόρτου δικτύου της φάσης επιστροφής, προκαλώντας υψηλό φόρτο δικτύου στη φάση προώθησης. Στην ενότητα αυτή παρουσιάζεται ένας άλλος αλγόριθμος με δύο στόχους. Πρωτίστως, ο νέος αλγόριθμος παράγει μια αναπαράσταση $R$ η οποία επιτυγχάνει ισορροπία μεταξύ των δύο φάσεων και ελαχιστοποιεί το συνολικό φόρτο δικτύου. Ο δεύτερος στόχος είναι η ανάπτυξη μιας επιλεκτικής πολιτικής δρομολόγησης για την προώθηση των συνόλων απαντήσεων, οδηγώντας σε σημαντική μείωση το φόρτου δικτύου της φάσης επιστροφής.

Ο πρώτος στόχος αντιμετωπίζεται επιλέγοντας την αναπαράσταση $R$ μεταξύ των δύο ακρέων περιπτώσεων: (i) τη μικρότερη δυνατή αναπαράσταση με μόνο $d$ συντελεστές DWT που απατούνται για την τοπική έρευνα του καταλόγου (ελαχιστοποίηση του φόρτου δικτύου της φάσης προώθησης) και (ii) τη μέγιστη δυνατή αναπαράσταση με όλα τα $n$ στοιχεία της ακολουθίας επερωτήματος (εξαφανίζοντας την επιβάρυνση των ψευδών θετικών όσο αφορά το υπολογιστικό κόστος και το φόρτο δικτύου της φάσης επιστροφής). Συνεπώς, μεταξύ των δύο αυτών άκρων, η αναπαράσταση $R$ μπορεί να αποτελείται από τους $l$ μεγαλύτερους συντελεστές DWT, όπου $d\le l\le n$. Εδώ πρέπει να σημειωθεί ότι ο τύπος αναπαράστασης αυτός, γενικεύει τις δύο ακραίες περιπτώσεις: θέτοντας $l=d$, η $R$ γίνεται ίση με την πρώτη (i) περίπτωση, ενώ αντίθετα, θέτοντας $l=n$, η $R$ γίνεται ίση με τη δεύτερη (ii) περίπτωση, καθώς οι $n$ συντελεστές DWT είναι ισότιμοι με τα $n$ στοιχεία της ακολουθίας επερωτήματος (εξαιτίας του θεωρήματος του Parseval)¹⁰¹⁰Στην περίπτωση του ML μπορεί να γίνει η υπόθεση ότι η $R$ αποτελείται από όλους τους $n$ συντελεστές DWT. Ωστόσο, επιλέγονται τα $n$ στοιχεία της ακολουθίας στο πεδίο του χρόνου για να αποφευχθεί ο υπολογισμός του αντίστροφου μετασχηματισμού DWT, εφόσον, στην περίπτωση αυτή το πεδίο του χρόνου εμφανίζει μικρότερες απαιτήσεις αποθήκευσης μιας και οι τιμές των δεδομένων είναι στο διάστημα 0-255.. Όπως ήδη περιγράφτηκε στην ενότητα 4.2.4, ένα πλήθος $l$, των μεγαλύτερων συντελεστών DWT, μπορεί να συλλάβει την ενέργεια της μουσικής ακολουθίας αποδοτικά και να μειώσει τον αριθμό των ψευδών θετικών αποτελεσμάτων. Συμπερασματικά, σε σχέση με την δεύτερη (ii) περίπτωση, ο φόρτος δικτύου της φάσης προώθησης αναμένεται να είναι μικρότερος, εφόσον $l\le n$. Σε σχέση με την πρώτη (i) περίπτωση, ο φόρτος δικτύου της φάσης επιστροφής επίσης αναμένεται να είναι μικρότερος, καθώς το πλήθος των ψευδών θετικών αποτελεσμάτων θα έχει σημαντικά μειωθεί, εφόσον $d\le l$.

Ωστόσο, η ρύθμιση του $l$, είναι δύσκολη, καθώς εξαρτάται από πολλούς παράγοντες, όπως λ.χ. η τοπολογία του MANET, οι οποίοι είναι μεταβαλλόμενοι. Για το λόγο αυτό, προτείνεται μια διαφορετική προσέγγιση. Αρχικά, στο $l$ δίνεται μια αρκετά μεγάλη τιμή και η τιμή αυτή μειώνεται μονοτονικά κατά την διάδοση της $R$ στην φάση προώθησης. Η μεθοδολογία αυτή αποτελεί τη μειούμενη αναπαράσταση (transcoding), καθώς εμπλέκει ακολουθίες με μεταβλητό αριθμό συντελεστών DWT οι οποίες αντιστοιχούν σε διάφορες προσεγγίσεις της αρχικής ακολουθίας επερωτήματος. Η μεθοδολογία transcoding:

• •

  Διατηρεί το φόρτο δικτύου κατά τη φάση προώθησης χαμηλό, καθώς το μέγεθος της $R$ μειώνεται κατά τη διάδοσή της στην φάση προώθησης.

• •

  Μειώνει το φόρτο δικτύου κατά τη φάση επιστροφής επιτρέποντας στους MH που εμπλέκονται στη φάση προώθησης να αποθηκεύσουν την μειωμένη αναπαράσταση και κατά τη φάση επιστροφής, να τη χρησιμοποιήσουν για πρώιμη επίλυση των ψευδών θετικών αποτελεσμάτων, πριν αυτά φθάσουν στον κόμβο που έθεσε το επερώτημα. Το πρόβλημα της αποθήκευσης εξαρτάται από πολλές παραμέτρους του δικτύου και είναι ανεξάρτητο από τη μέθοδο αυτή, ενώ αποδοτικές λύσεις μπορούν να βρεθούν στην εργασία [131]. Στα πειράματα της εργασίας [141], εντοπίστηκε ότι αποθηκεύοντας τις αναπαραστάσεις για ένα μικρό, σταθερό χρονικό διάστημα είναι επαρκές για αυξημένη επίδοση.

• •

  Μειώνει το χρόνο επεξεργασίας σε κάθε MH, καθώς το κόστος επίλυσης των ψευδών θετικών αποτελεσμάτων σε κάθε MH εξαρτάται από το μέγεθος της $R$.

Η μείωση επιτυγχάνεται διατηρώντας $l$ τιμές σύμφωνα με μια αντίστροφη σιγμοειδή συνάρτηση  4.10b. Εξαιτίας του σχήματος της συνάρτησης αυτής, η άμεση γειτονιά του MH που έθεσε το επερώτημα, η οποία μπορεί να δώσει αποτελέσματα συντομότερα, λαμβάνει μεγαλύτερη $R$, ενώ το βάρος που τίθεται στους MH που είναι μακριά είναι σημαντικά μικρότερο. Επιπλέον, με τη μέθοδο αυτή, ελέγχεται η εκθετική αύξηση του φόρτου δικτύου που προκαλείται από την απλή καθολική εκπομπή της πλήρους αναπαράστασης. Ένα παράδειγμα δίνεται στο Σχήμα 4.10a. Ο $P_1$ είναι κόμβος που θέτει το επερώτημα και ο $P_4$ είναι κόμβος που ξεκινά την προώθηση του συνόλου αποτελεσμάτων. Οι MH στο μονοπάτι από τον $P_1$ στον $P_4$ δείχνονται σκιασμένοι και επισημειώνονται με το μέγεθος της $R$ το οποίο έλαβαν ($o{P}_1$ ξεκινά με 10 K συντελεστές DWT). Το Σχήμα 4.10b δείχνει πως τα μεγέθη αυτά μειώνονται ακολουθώντας την αντίστροφη σιγμοειδή συνάρτηση. Κατά την φάση επιστροφής, ξεκινώντας από τον $P_4$, οι MH $P_3$ και $P_5$ είναι προσβάσιμοι (δείχνονται με διακεκομμένα βέλη). Η αποθηκευμένη αναπαράσταση στον $P_3$ μπορεί να βοηθήσει στην επίλυση ψευδών θετικών αποτελεσμάτων στο σύνολο απαντήσεων. Το γεγονός αυτό οφείλεται στο ότι στον $P_4$ τα ψευδή θετικά εξετάστηκαν με μικρότερη $R$ από ότι στον $P_3$. Αντίθετα, ο $P_5$ δεν βρέθηκε στο μονοπάτι, και κατά συνέπεια δεν μπόρεσε να επιλύσει ψευδή θετικά αποτελέσματα.

Εφεξής, το μέγεθος της αρχικής αναπαράστασης επερωτήματος, $I$, δίνεται ως συντελεστής του μεγέθους του πλήρους επερωτήματος, ενώ η κλίση της αντίστροφης σιγμοειδούς συνάρτησης ελέγχεται από την παράμετρο $\alpha$ (μεγαλύτερες τιμές της $\alpha$ προκαλούν μεγαλύτερες κλίσεις).

Όσο αφορά το δεύτερο στόχο, δεν ακολουθείται η απλοϊκή προσέγγιση του αλγορίθμου ML, ο οποίος διαδίδει τα σύνολα απαντήσεων σε όλους του κόμβους. Αντίθετα, κατά την φάση προώθησης, όπως είναι σύνηθες σε όλα τα πρωτόκολλα δρομολόγησης δυναμικών πηγών [135], κάθε MH που λαμβάνει την $R$, επιπλέον λαμβάνει και το αναγνωριστικό όλων των MH στο μονοπάτι το οποίο ακολουθήθηκε από τον κόμβο που έθεσε το επερώτημα. Τα αναγνωριστικά αυτά μπορούν να συμπεριληφθούν στην $R$ με ελάχιστο κόστος (μόνο μερικά bytes). Όταν ένας MH ξεκινά την διάδοση των συνόλων απαντήσεων, επιλέγει τους γειτονικούς κόμβους στους οποίους θα μεταδώσει τα σύνολα απαντήσεων, και δεν τα μεταδίδει σε όλους. Για την επιλογή αυτή, εφαρμόζει μια πολιτική η οποία εστιάζει στους γείτονες που περιλαμβάνονται στο μονοπάτι από τον κόμβο επερώτησης. Καθώς αρκετές τέτοιες πολιτικές μπορούν να αναπτυχθούν, στην ακόλουθη ενότητα υπάρχει λεπτομερής αναφορά σε αυτές. Όλες οι πολιτικές, παρά τις διαφορές τους, στοχεύουν στην επιλογή γειτονικών MH οι οποίοι περιλαμβάνονται στο μονοπάτι, εξαιτίας της αποθηκευμένης αναπαράστασης που διατηρούν, με τη χρήση της οποίας μπορούν να επιλύσουν ψευδή θετικά αποτελέσματα. Περισσότερες λεπτομέρειες δίνονται στην ενότητα 4.2.6.

Ο αλγόριθμος που συνδυάζει όλα τα προαναφερθέντα χαρακτηριστικά ονομάζεται RT (querying by Reduced representation with Transcoding - επερώτηση με χρήση μειωμένης και μειούμενης αναπαράστασης) και παρουσιάζεται στο Σχήμα 4.11.

Για την ευκρινέστερη παρουσίαση των δυο πρώτων πολιτικών, δίνεται το παράδειγμα του Σχήματος 4.12a, όπου παρουσιάζεται το μονοπάτι από τον MH $P_1$ στον MH $P_6$, το οποίο ακολουθήθηκε κατά την φάση προώθησης. Το Σχήμα 4.12b δείχνει τη δρομολόγηση των συνόλων απαντήσεων από τον $P_6$ προς τον $P_1$. Συγκρίνοντας τις δυο φάσεις, αρκετοί MH άλλαξαν τη θέση τους, ενώ άλλοι απενεργοποιήθηκαν και τέλος μερικοί έγιναν μη προσβάσιμοι. Οι MH που παρουσιάζονται σκιασμένοι είναι αυτοί που περιλαμβάνονται και στο μονοπάτι της φάσης προώθησης, ενώ οι υπόλοιποι είναι νέοι κόμβοι που εμπλέκονται μόνο στη φάση επιστροφής.

Με την πολιτική καθολικού απαριθμητή (Global-Counter - GC), όταν ένας MH ($P_6$ στο προκείμενο) ξεκινά τη διάδοση ενός συνόλου απαντήσεων, αναθέτει σε κάθε διαθέσιμη τιμή άλματος (μετάδοσης), $h$, τιμή ίση με το μονοπάτι της φάσης προώθησης και επιπλέον μια τιμή $e$. Στο παράδειγμα, το μήκος (πλήθος ακμών) είναι ίσο με 5. Έστω $e=1$ και $h=6$. Ο GC προσπαθεί να βρει μεταξύ των γειτονικών κόμβων, εκείνον που ήταν ο προηγούμενος του στο μονοπάτι. Στο παράδειγμα, στον $P_6$, ο GC προσπαθεί να βρει τον $P_5$. Εάν ο MH αυτός είναι προσβάσιμος, τότε είναι και ο μόνος στον οποίο μεταδίδεται το σύνολο απαντήσεων, και το $h$ μειώνεται κατά μια μονάδα. Η ίδια διαδικασία ακολουθείται επαναλαμβανόμενα. Στον $P_5$, ο GC προσπαθεί να εντοπίσει τον $P_4$. Εάν ο $P_4$ δεν είναι προσβάσιμος, όπως στην περίπτωση του παραδείγματος, τότε ο GC μεταδίδει το σύνολο απαντήσεων σε όλους τους γειτονικούς MH (καθολική εκπομπή στους $P_7$ και $P_8$) και καθένας λαμβάνει τιμή του $h$ μειωμένη κατά μια μονάδα. Στην συνέχεια, εκτός εάν βρεθεί κόμβος που περιλαμβάνεται στο μονοπάτι προώθησης, ο GC συνεχίζει την καθολική εκπομπή σε όλους τους γείτονες. Σε κάθε εκπομπή του συνόλου απαντήσεων, το $h$ μειώνεται κατά μια μονάδα, και κατά συνέπεια δρα ως καθολικός απαριθμητής. Εάν ένας MH από το μονοπάτι προώθησης εντοπιστεί σε οποιοδήποτε σημείο, τότε, όπως και προηγουμένως, ο GC προσπαθεί να βρει τον προηγούμενο του στο μονοπάτι προώθησης. Στο παράδειγμα, ο $P_3$ είναι ένας κόμβος από το μονοπάτι προώθησης, ο οποίος προσεγγίστηκε με $h$ ίσο με 2. Ο προηγούμενος του είναι ο $P_2$, ο οποίος στη συνέχεια μεταδίδει (καθώς το $h$ είναι 1) το σύνολο απαντήσεων στον $P_1$ και η διαδικασία τερματίζεται.

Συνοψίζοντας, όταν επιλέγει MH για τη δρομολόγηση των συνόλων απαντήσεων, ο GC προσπαθεί να ακολουθήσει τους MH που περιλαμβάνονται στο μονοπάτι προώθησης. Ωστόσο, για να υπερνικήσει προβλήματα από τη μεταβολή του ΜΑΝΕΤ (όπως η απενεργοποίηση του $P_4$ στο παράδειγμα), επιτρέπει ένα ποσοστό ανακολουθίας της πολιτικής του, χρησιμοποιώντας καθολική εκπομπή. Για τον έλεγχο της ανακολουθίας, και κατά συνέπεια του φόρτου δικτύου της φάσης επιστροφής, χρησιμοποιεί την μεταβλητή $e$. Στο σημείο αυτό πρέπει να σημειωθεί ότι για πολύ μεγάλο $e$, ο GC καταφεύγει στην καθολική εκπομπή για πάρα πολλές φορές και συνεπώς γίνεται παρόμοιος με την απλοϊκή πολιτική του αλγορίθμου ML. Αντίθετα, για πολύ μικρό $e$, ο κόμβος επερώτησης ίσως να μη είναι δυνατό να προσεγγιστεί, ειδικότερα όταν το MANET μεταβάλλεται πολύ γρήγορα.

Μια παραλλαγή του GC έχει ως εξής. Κατόπιν μιας ανακολουθίας, όταν ένας MH από το μονοπάτι εντοπιστεί, το $h$ επαναφέρεται στην αρχική του τιμή. Στο προηγούμενο παράδειγμα, όταν ο $P_3$ προσεγγίζεται, το διαθέσιμο $h$ επαναφέρεται στην αρχική τιμή 6. Συνεπώς, το $h$ δρα ως μειούμενος τοπικός απαριθμητής, εφόσον, επαναφέρεται στην αρχική του τιμή σε διάφορους MH, ανεξάρτητα. Για το λόγο αυτό, η πολιτική αυτή ονομάζεται τοπικού απαριθμητή (Local-Counter - LC). Ο στόχος της είναι η αύξηση της πιθανότητας προσέγγισης του κόμβου επερώτησης, επιβραβεύοντας τον εντοπισμό κόμβων που περιλαμβάνονται στο μονοπάτι προώθησης. Ωστόσο, η πολιτική αυτή μπορεί να προκαλέσει αύξηση του φόρτου δικτύου στη φάση επιστροφής.

Στην πολιτική κρίσιμης μάζας (Critical-Mass - CM), εάν τουλάχιστο ένας αριθμός, ονομάζεται παράγοντας κρίσιμης μάζας (Critical-Mass Factor - CMF), των ισχύων γειτόνων ήταν στο μονοπάτι προώθησης, επιλέγονται μόνο αυτοί για τη μετάδοση του συνόλου απαντήσεων. Εάν το πλήθος τους είναι μικρότερο από τον CMF, τότε επιπλέον τυχαία επιλέγονται μερικοί από τους τρέχοντες κόμβους (παρότι δεν υπήρξαν στο μονοπάτι προώθησης) ώστε να μεταδοθεί σε τουλάχιστο CMF MH το σύνολο απαντήσεων. Αντίθετα, εάν ο αριθμός τους είναι μεγαλύτερος από τον CMF, τότε επιλέγονται όλοι. Για παράδειγμα, έστω η περίπτωση του Σχήματος 4.13. Το Σχήμα 4.13a δείχνει τη φάση προώθησης, ενώ το Σχήμα 4.13b παρουσιάζει τη φάση επιστροφής. Κατά τη φάση επιστροφής μερικοί MH άλλαξαν τη θέση τους. Έστω ότι ο CMF είναι 2. Όταν ο $P_4$ ξεκινήσει τη μετάδοση του συνόλου απαντήσεων, αρχικά επιλέγει τον $P_3$, καθώς ήταν στο μονοπάτι προώθησης. Εφόσον αυτός είναι και ο μόνος MH του μονοπατιού προώθησης και ο CMF είναι 2, επιπλέον επιλέγει τυχαία τον $P_5$ μεταξύ των άλλων προσβάσιμων MH.

Οι κόμβοι που επιλέχθηκαν τυχαία ώστε να ικανοποιήσουν τον παράγοντα CMF, λαμβάνουν το μονοπάτι του MH που εκκίνησε την επιστροφή του συνόλου αποτελεσμάτων (στο προηγούμενο παράδειγμα, ο $P_5$ που επιλέχθηκε από τον $P_4$, θα λάβει επίσης και το μονοπάτι από τον $P_1$ στον $P_4$). Με τη γνώση αυτή, εξαιτίας της κινητικότητας, είναι πιθανό ότι μερικοί κόμβοι κατά τη διάρκεια της φάσης επιστροφής θα εντοπίσουν γείτονες που υπάρχουν στο μονοπάτι προώθησης (στο ίδιο παράδειγμα, ο $P_5$ εντοπίζει τον $P_2$ ο οποίος περιλαμβάνεται στο μονοπάτι προώθησης). Συνεπώς, ο αντίκτυπος αυτών των τυχαία επιλεγμένων κόμβων στην προτεινόμενη πολιτική διατηρείται σε μέτρια επίπεδα.

Η πολιτική CM διαφέρει από τις GC και LC στα ακόλουθα ζητήματα: (i) Δεν ερευνά για τον προηγούμενο κόμβο του μονοπατιού, μόνο εντοπίζει MH που περιλαμβάνονται στο μονοπάτι προώθησης ανεξαρτήτως της σειράς τους. Η τακτική αυτή επιτρέπει στον CM περισσότερη προσαρμοστικότητα στις μεταβολές του MANET. (ii) Δεν καταφεύγει σε καμία περίπτωση σε καθολική εκπομπή στους γειτονικούς κόμβους. Στη χειρότερη περίπτωση, το πλήθος των τυχαία επιλεγμένων κόμβων είναι ίσο με τον παράγοντα CMF. Έτσι επιτυγχάνεται καλύτερος έλεγχος του φόρτου δικτύου επιστροφής. Εξαιτίας των προαναφερθέντων χαρακτηριστικών, ο CM αποδίδει καλύτερα από τους GC και LC.

Στην παρούσα ενότητα ενδιαφερόμαστε για την αυξητική εξαγωγή χαρακτηριστικών ώστε να πληρούνται οι περιορισμοί που θέτει η ροή πληροφορίας στο εξεταζόμενο σενάριο. Ακολούθως θα παρουσιαστεί μια διαδικασία εξαγωγής μουσικών χαρακτηριστικών με τρόπο αυξητικό βασισμένη στην μέθοδο Single Gaussian Combined (G1C) της εργασίας [158] που κατατέθηκε στο διαγωνισμό MIREX 2006 [155] και κατέλαβε την πρώτη θέση.

Αρχικά, για κάθε μουσικό κομμάτι υπολογίζονται οι συντελεστές Mel Frequency Cepstrum Coefficients (MFCC), η κατανομή των οποίων μπορεί να περιγραφεί συνοπτικά με μια κατανομή Gaussian (G1) και έναν πίνακα πλήρους συνδιακύμανσης (full covariance matrix). Η απόσταση μεταξύ δύο τέτοιων κατανομών υπολογίζεται με χρήση της συμμετρικής έκδοσης της απόκλισης (Kullback Leibler divergence). Στη συνέχεια, υπολογίζονται τα πρότυπα διακύμανσης (fluctuation patterns - FPs) για κάθε τραγούδι. Ένα FP περιγράφει τη διαμόρφωση του πλάτους της έντασης ανά ζώνες συχνοτήτων, ενώ σε κάποιο βαθμό μπορεί να περιγράψει και περιοδικούς παλμούς (beats) του τραγουδιού. Όλα τα FPs που υπολογίζονται για κάθε πλαίσιο συνδυάζονται υπολογίζοντας το μέσο (median) πρότυπο. Κατά συνέπεια, για κάθε τραγούδι εξάγονται δύο χαρακτηριστικά από το FP, η βαρύτητα (FP.G) που είναι το κέντρο βάρους του FP κατά μήκος της διάστασης διαμόρφωσης συχνότητας και το μπάσο (FP.B) που είναι η ένταση της διακύμανσης των χαμηλότερων ομάδων συχνότητας στις υψηλότερες συχνότητες διαμόρφωσης. Βάσει των τεσσάρων τιμών αυτών (G1, FP, FP.B and FP.G) υπολογίζεται η ομοιότητα 2 τραγουδιών ως γραμμικός συνδυασμός βαρών (κανονικοποιημένος στο εύρος [0,1]), όπως περιγράφεται λεπτομερώς στην εργασία [158].

Στις μέρες, μια πληθώρα εφαρμογών, όπως θα ήταν αναμενόμενο, δημιουργεί ροές πληροφορίας εν αντιθέσει με τα στατικά δεδομένα: οικονομικά στοιχεία, παρακολούθηση δικτύων, έξοδοι αισθητήτων, κλπ. Στα πλαίσια της τρέχουσας ενότητας διερευνώνται οι περιπτώσεις όπου υφίσταται ευκαιρία χρήσης συνεχόμενων επερωτήσεων. Σύνηθες παράδειγμα τέτοιας περίπτωσης είναι οι χρηματιστηριακές εφαρμογές όπου οι συνεχείς επερωτήσεις χρησιμοποιούνται για την παρακολούθηση της τιμής μετοχών αλλά και για τον εντοπισμό ομοιότητας σε μεταβολές και τάσεις τιμής μετοχών.

Οι μέθοδοι που ήδη έχουν αναπτυχθεί για την ανάκτηση πληροφορίας βάσει περιεχομένου σε ροές πληροφορίας είναι κατά κανόνα εξειδικευμένες για τον τύπο των δεδομένων που διαχειρίζονται και κατά συνέπεια δεν είναι ιδιαίτερα χρήσιμες για γενικευμένη χρήση. Ένα βασικό χαρακτηριστικό είναι η χρήση μετρικών ομοιότητας που εκμεταλλεύονται την τριγωνική ανισότητα για τον έγκαιρο περιορισμό του χώρου αναζήτησης με άμεση συνέπεια τη μείωση των μη απαραίτητων μετρήσεων απόστασης δεδομένων [132], [133], [148]. Συνήθεις τέτοιες μετρικές είναι η Ευκλείδεια και η Manhattan απόσταση, που δεν είναι κατάλληλες για τον υπολογισμό ομοιότητας μουσικών δεδομένων [123].

Αναλύοντας περαιτέρω το προαναφερθέν σενάριο χρήσης της ενότητας 4.3.1, μετά τον ορισμό των προτιμήσεων του χρήστη βάσει των οποίων προσδιορίζεται η αρέσκειά του για κάθε ροή και τον υπολογισμό των χαρακτηριστικών του, η υπηρεσία πρέπει να εξάγει τους συντελεστές MFCCs για κάθε μια πηγή, να εντοπίσει τα μέρη της που περιέχουν μουσική πληροφορία, να εξάγει χαρακτηριστικά των μερών αυτών, να υπολογίσει την ομοιότητα με τα προτιμητέα τραγούδια και τέλος να βαθμολογήσει κάθε πηγή βάσει του τρέχοντος τραγουδιού. Οι βαθμολογία τότε παρουσιάζεται στον χρήστη ενώ μετά την αρχική βαθμολόγηση, η υπηρεσία πρέπει να συνεχίσει να παρακολουθεί τις πηγές και να εφαρμόσει όλα τα προαναφερθέντα βήματα ώστε να μπορεί να προσδιορίσει αν η βαθμολογία αλλάζει κατά τη διάρκεια μετάδοσης της κάθε πηγής. Ακολούθως, θα περιγραφεί η μέθοδος CQiSM - Continuous Querying in Streaming Music ή συνεχείς επερωτήσεις σε ροές μουσικής πληροφορίας, όπως παρουσιάζεται στην έργασία [147]. Η αρχιτεκτονική της μεθόδου CQiSM παρουσιάζεται στο Σχήμα 4.14.

Ακολούθως, η μέθοδος CQiSM μπορεί να τεμαχιστεί σε τρία μέρη: την αυξητική εξαγωγή χαρακτηριστικών, τον εντοπισμό ορίων των τραγουδιών και την συνολική αξιολόγηση των πηγών. Οι επόμενες ενότητες δίνουν λεπτομερή περιγραφή των τριών μερών αυτών.

Ένα από τα εκ των ων ουκ άνευ χαρακτηριστικά των δεδομένων ροών είναι πως για να είναι διαχειρίσιμος ο ρυθμός ροής της πληροφορίας της πηγής όλες οι διαδικασίες που εφαρμόζονται στα δεδομένα πρέπει να είναι όσο το δυνατό περισσότερο βελτιστοποιημένες. Με άλλα λόγια, τα αποτελέσματα των ήδη εκτελεσμένων υπολογισμών πρέπει να χρησιμοποιούνται για την αφαίρεση υπολογιστικού φόρτου από τους επόμενους υπολογισμούς. Ακολούθως, καθώς ένας από τους πιο χρονοβόρους υπολογισμούς της μεθόδου CQiSM είναι η εξαγωγή χαρακτηριστικών, η ενότητα αυτή περιγράφει μια αυξητική έκδοση της μεθόδου G1C του Pampalk [158]. Εδώ πρέπει να σημειωθεί πως η αυξητική έκδοση του G1C στο προκείμενο αναφέρεται μόνο για τον υπολογισμό των συντελεστών MFCC.

Κάθε τραγούδι τεμαχίζεται σε πλαίσια με $N$ στοιχεία καθένα, ενώ κάθε πλαίσιο τεμαχίζεται με τη σειρά του σε τμήματα μήκους $S$ στοιχεία με επικάλυψη (hop) $K$ στοιχείων μεταξύ τους (βλ. Σχήμα 4.15).

Κάθε $K$ τιμές που λαμβάνονται από μια πηγή ορίζονται ως ένα νέο τεμάχιο (το πρώτο τεμάχιο του κάθε πλαισίου δε συμμετέχει στους υπολογισμούς. Το τεμάχιο αυτό το ονομάζουμε χάριν ευκολίας εφεξής ως ενημέρωση. Για κάθε νέο τεμάχιο, εξάγονται οι συντελεστές MFCC του ώστε να είναι δυνατός ο υπολογισμός του ορίου του. Ο υπολογισμός των MFCC του νέου τεμαχίου απαιτεί την εφαρμογή ενός πλαισίου Hann στις τιμές του τεμαχίου, τον υπολογισμό του μετασχηματισμού Fast Fourier καθώς πλήθος άλλων στατικών υπολογισμών. Στη συνέχεια, τα αποτελέσματα των προαναφερθέντων υπολογισμών πολλαπλασιάζονται με τριγωνικά φίλτρα (Mel-filters) ώστε να μετασχηματιστεί η ενέργεια του φάσματος σε κλίμακα Melscale με χρήση 34 (Mel-spaced) τμημάτων συχνότητας.

Με δεδομένη την υπόθεση ότι η μέθοδος CQiSM εφαρμόζεται σε πλήρες πλαίσιο (μη αυξητική έκδοση), τα φίλτρα Mel-filters και τα προηγούμενα αποτελέσματα των υπολογισμών είναι διδιάστατοι πίνακες. Θυμίζοντας εδώ πως ο πολλαπλασιασμός πινάκων $A(m\times n)$ και $B(n\times z)$ δίνει ως αποτέλεσμα ένα πίνακα $C(m\times z)$, παρατηρείται πως κάθε στήλη $j$ του πίνακα $C$ είναι αποτέλεσμα συνδυασμού όλων των στοιχείων του πίνακα $A$ με τα στοιχεία της στήλης $j$ του πίνακα $B$. Στην αυξητική έκδοση, το αποτέλεσμα που λαμβάνεται είναι ένας μονοδιάστατος πίνακας καθώς προέρχεται από ένα τεμάχιο μόνο.

Τέλος, γίνονται και κάποιοι επιπλέον υπολογισμοί για την εξαγωγή των συντελεστών MFCC κάθε νέου τμήματος που στη συνέχεια συνδυάζονται με τους συντελεστές MFCC των προηγούμενων τεμαχίων του τρέχοντος πλαισίου για τον υπολογισμό των χαρακτηριστικών G1, FPs, FP.G και FP.B. Ακολούθως, όταν εμφανιστεί μια ενημέρωση τότε υπολογίζονται μόνο οι MFCC του και συνδυάζονται με τους MFCC των προηγούμενων τεμαχίων για να δώσουν τους MFCC του πλήρους πλαισίου κι έτσι να υλοποιηθεί η μέθοδος C1G με αυξητικό τρόπο.

Η θεώρηση των μουσικών δεδομένων ως συνεχή ροή πληροφορίας τα οποία επίσης εναλλάσσονται με μη μουσικό περιεχόμενο εισαγάγει ένα διπλό πρόβλημα προς αντιμετώπιση: τον προσδιορισμό των ορίων του κάθε τραγουδιού αλλά και τον διαχωρισμό μουσικής από ομιλία. Το δεύτερο πρόβλημα απαιτείται για τον περιορισμό των μη απαραίτητων και ιδιαίτερα κοστοβόρων υπολογισμών σε τμήματα της ροής που δε θα συνεισφέρουν στην αξιολόγηση της πηγής. Η έρευνα του διαχωρισμού μουσικής από ομιλία είναι μια ερευνητική κατεύθυνση αφ’ εαυτού της, με πλήθος εναλλακτικών προσεγγίσεων [119], η ανάλυση της οποίας υπερβαίνει το ενδιαφέρον της τρέχουσας ενότητας. Καθώς η αποδοτικότητα των μεθόδων διαχωρισμού μουσικής από ομιλία θα επηρεάσει παρόμοια όλες τις μεθόδους ανάκτησης πληροφορίας σε ροές δεδομένων, για απλοποίηση, στο προκείμενο ο διαχωρισμός θεωρείται εκ προοιμίου γνωστός.

Από την άλλη πλευρά, ο προσδιορισμός των ορίων ενός τραγουδιού αναφέρεται στον εντοπισμό του τέλους ενός τραγουδιού που ακολουθείται αμέσως από ένα άλλο χωρίς κάποια άλλη πληροφορία μεταξύ τους. Στις περιπτώσεις αυτές, όταν ένα νέο τραγούδι μιας πηγής εντοπιστεί, τότε συγκρίνεται με τις προτιμήσεις του χρήστη και καμία άλλη δραστηριότητα μέτρησης ομοιότητας δεν γίνεται εφόσον το όριο με το επόμενο τραγούδι είναι αναγνωρίσιμο. Ακολούθως, μόνο μια ελάχιστη εξαγωγή χαρακτηριστικών συνεχίζει ώστε να εντοπιστεί η αλλαγή του τραγουδιού ενώ τόσο η πλήρης εξαγωγή χαρακτηριστικών όσο και η μέτρηση ομοιότητας αποφεύγονται.

Για την απόφαση αλλαγής τραγουδιού, η μέθοδος CQiSM παρακολουθεί την πρόοδο των τιμών των συντελεστών MFCC και αναζητά μεγάλες αλλαγές. Καθώς τα τραγούδια τελειώνουν, η συνολική τους ενέργεια τείνει να μειώνεται. Το φαινόμενο αυτό είναι ιδιαίτερα προφανές στους πρώτους από τους συντελεστές MFCC που συσχετίζονται άμεσα με την ενέργεια του σήματος της ηχογράφησης. Συνεπώς, καθώς το επόμενο τραγούδι ξεκινά η ενέργεια του σήματός του είναι σημαντικά υψηλότερη και κατ’ αντιστοιχία οι πρώτοι συντελεστές MFCC του είναι ιδιαίτερα αυξημένοι. Για τον υπολογισμό λοιπόν της μεταβολής των MFCC μπορεί να χρησιμοποιηθεί οποιαδήποτε μετρική ομοιότητας. Στο προκείμενο χρησιμοποιείται η Ευκλείδεια απόσταση λόγω απλότητας και δημοφιλίας. Μετά τον υπολογισμό της αρχής ενός νέου τραγουδιού, η μέθοδος CQiSM εκτελεί μόνο μια ελαχιστοποιημένη εξαγωγή χαρακτηριστικών που βασίζεται στους συντελεστές MFCC και όχι τα χαρακτηριστικά G1, FPs & FP.G που εισαγάγουν αυξημένο υπολογιστικό φόρτο.

Καθώς οι μέθοδοι εξαγωγής χαρακτηριστικών και μέτρησης ομοιότητας που χρησιμοποιεί η μέθοδος CQiSM είναι σχεδιασμένες για δίνουν αποτελέσματα μονοσήμαντα (ένα αριθμό) για κάθε δύο τραγούδια χωρίς κάποια άλλη γνώση, για την αξιολόγηση της επιλογής των πηγών από τη μέθοδο CQiSM υπάρχουν δύο κύριες εναλλακτικές μεθοδολογίες. Αρχικά, ακολουθώντας μια ποσοτική αντιμετώπιση, αξιολογείται η διάχυση και το εύρος της ομοιότητας σε ένα πλήθος τραγουδιών ενώ δε δίνεται σημασία στην υπολογισμένη ομοιότητα. Ωστόσο, καθώς οι πηγές πιθανώς περιέχουν διαφορετικό πλήθος τραγουδιών ανά μονάδα χρόνου απαιτείται κανονικοποίηση όσο αφορά το πλήθος των τραγουδιών για το οποίο τα αποτελέσματα αναφέρονται. Η συνολική αξιολόγηση με την ποσοτική αντιμετώπιση δίνεται από την εξίσωση 4.5 στην οποία για κάθε νέο τραγούδι $i$ σε μια πηγή μπορούν να εντοπιστούν $j$ αποτελέσματα βάσει των προτιμήσεων των χρηστών με βαθμό ομοιότητας $T_{ij}$. Για κάθε $i$ και $j$ αθροίζεται η αντίστοιχη ομοιότητα $T_{ij}$ και διαιρείται με το πλήθος $L$ των τραγουδιών που περιέχει η πηγή.

Εναλλακτικά, η ποιοτική αντιμετώπιση ενδιαφέρεται για το βέλτιστο αποτέλεσμα κάθε προτίμησης ενός χρήση αδιαφορώντας για τα υπόλοιπα αποτελέσματα. Και πάλι, για να αντιμετωπιστεί το διαφορετικό πλήθος τραγουδιών ανά μονάδα χρονικής εξέτασης για το οποίο τα αποτελέσματα προέκυψαν μεταξύ πηγών, απαιτείται κανονικοποίηση (βλ. Εξίσωση 4.6). Στην περίπτωση αυτή για κάθε νέο τραγούδι $i$ μόνο το εγγύτερο αποτέλεσμα χρησιμοποιείται για την αξιολόγηση κάθε πηγής.