Μείωση διάστασης για την αναζήτηση προσεγγιστικού κοντινού γείτονα στη μετρική Μανχάταν

Οι τυχαίες προβολές αποτελούν μια απο τις πιο διαδεδομένες μεθόδους για το χειρισμό δεδομένων μεγάλης διάστασης. Ξεκινώντας από το περίφημο Johnson-Lindenstrauss Lemma, τέτοιου είδους προβολές έχουν μελετηθεί αρκετά για την Ευκλείδια (L2) μετρική, και πολύ λιγότερο για τη μετρική Μανχάταν (L1). Σε αυτή την εργασία εστιάζουμε στο πρόβλημα του προσεγγιστικού κοντινότερου γείτονα στη μετρική Μανχάταν, εκμεταλλεύοντας την αποφαντική εκδοχή του προβλήματος, που λέγεται προσεγγιστικός κοντινός γείτονας και επιβάλει ένα (περίπου) λογαριθμικό κόστος.

Το 2007, οι Indyk και Naor εισήγαγαν την έννοια των εμβυθίσεων που διατηρούν τον κοντινότερο γείτονα (nearest neighbor-preserving embeddings). Οι εμβυθίσεις αυτές είναι τυχαιοκρατικές και εγγυόνται για την αλλοίωση μόνο N αποστάσεων (μεταξύ ενός σημείου-query και N σημείων), αντί για όλα τις δυνατές O(N^2). Τέτοιου είδους εμβυθίσεις υπάρχουν για τις μετρικές L2 και L1, καθώς και για διπλασιάζοντα (doubling) υποσύνολα της L2.

Σε αυτή την εργασία παρουσιάζουμε μια συνάρτηση εμβύθισης για την μείωση διάστασης, η οποία διατηρεί τον κοντινό γείτονα (near neighbor-preserving) για διπλασιάζοντα υποσύνολα της L1. Η τεχνική που εφαρμόζουμε είναι να προβάλουμε τυχαία όχι τα ίδια τα σημεία, αλλά ένα σύνολο αντιπροσώπων τους. Μελετούμε δύο είδη αντιπροσώπων, τα approximate nets και τα randomly shifted grids, και τα συγκρίνουμε ως προς την νέα διάσταση και το χρόνο υπολογισμού της συνάρτησης εμβύθισης.