Καμπύλη Z-τάξης

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Τέσσερις επαναλήψεις της καμπύλης Z-τάξης.

Στη μαθηματική ανάλυση και την επιστήμη των υπολογιστών, οι συναρτήσεις Z-τάξης όπως η καμπύλη Λεμπέσγκ, η καμπύλη Μόρτον που γεμίζει το χώρο[1] , η τάξη Μόρτον ή κώδικα Μόρτον μειώνουν πολυδιάστατα δεδομένα σε μία μόνο διάσταση, διατηρώντας την τοπικότητα των σημείων δεδομένων. Ονομάστηκε στη Γαλλία από τον Ανρί Λεμπέσγκ, ο οποίος τη μελέτησε το 1904[2], και στις Ηνωμένες Πολιτείες από τον Γκάι Μακ Ντόναλντ Μόρτον, ο οποίος την εφάρμοσε για πρώτη φορά στην αλληλουχία αρχείων το 1966[3]. Η Z-τάξης ενός σημείου σε πολλές διαστάσεις υπολογίζεται απλά με την παρεμβολή των δυαδικών αναπαραστάσεων των τιμών των συντεταγμένων του. Αφού τα δεδομένα ταξινομηθούν με αυτή τη σειρά, μπορεί να χρησιμοποιηθεί οποιαδήποτε μονοδιάστατη δομή δεδομένων, όπως απλοί μονοδιάστατοι πίνακες, δυαδικά δέντρα αναζήτησης, δέντρα Β, λίστες άλματος ή (με τα λιγότερο σημαντικά bit αποκομμένα) πίνακες κατακερματισμού. Η προκύπτουσα σειρά μπορεί να περιγραφεί ισοδύναμα ως η σειρά που θα λαμβανόταν από μια βαθιά διάσχιση ενός τετραδένδρου ή οκταδένδρου.

Τιμές συντεταγμένων[Επεξεργασία | επεξεργασία κώδικα]

Υπολογισμός των (x, y)-συντεταγμένων της καμπύλης Z-τάξης από τα διαπλεκόμενα bits της τιμής z 2479.

Το παρακάτω σχήμα δείχνει τις τιμές Z για την περίπτωση των δύο διαστάσεων με ακέραιες συντεταγμένες 0 ≤ x ≤ 7, 0 ≤ y ≤ 7 (εμφανίζονται τόσο σε δεκαδικό όσο και σε δυαδικό σύστημα). Η παρεμβολή των δυαδικών τιμών συντεταγμένων (ξεκινώντας προς τα δεξιά με το x-bit (με μπλε χρώμα) και εναλλάσσοντας προς τα αριστερά με το y-bit (με κόκκινο χρώμα)) δίνει τις δυαδικές τιμές z (με κλίση 45° όπως φαίνεται). Η σύνδεση των τιμών z με την αριθμητική τους σειρά παράγει την αναδρομική καμπύλη σχήματος Z. Οι δισδιάστατες τιμές Z είναι επίσης γνωστές ως τιμές τετραπλού κλειδιού.

Οι τιμές Z των συντεταγμένων x περιγράφονται ως δυαδικοί αριθμοί από την ακολουθία Μόσερ-ντε Μπρούιν (Moser-de Bruijn), με μη μηδενικά bit μόνο στις ζυγές θέσεις τους: 

x[] = {0b000000, 0b000001, 0b000100, 0b000101, 0b010000, 0b010001, 0b010100, 0b010101}

Το άθροισμα και η διαφορά δύο τιμών x υπολογίζονται με τη χρήση πράξεων κατά μπιτ: 

x[i+j] = ((x[i] | 0b10101010) + x[j]) & 0b01010101
x[i−j] = ((x[i] & 0b01010101) − x[j]) & 0b01010101  if i ≥ j

Αυτή η ιδιότητα μπορεί να χρησιμοποιηθεί για τη μετατόπιση μιας τιμής Ζ, παραδείγματος χάριν σε δύο διαστάσεις, οι συντεταγμένες προς τα πάνω (μείωση y), κάτω (αύξηση y), αριστερά (μείωση x) και δεξιά (αύξηση x) από την τρέχουσα τιμή z : 

top    = (((z & 0b10101010) − 1) & 0b10101010) | (z & 0b01010101)
bottom = (((z | 0b01010101) + 1) & 0b10101010) | (z & 0b01010101)
left   = (((z & 0b01010101) − 1) & 0b01010101) | (z & 0b10101010)
right  = (((z | 0b10101010) + 1) & 0b01010101) | (z & 0b10101010)

Και γενικότερα προσθέτουμε δύο δισδιάστατες τιμές Ζ w και z: 

sum    = ((z | 0b10101010) + (w & 0b01010101) & 0b01010101) | ((z | 0b01010101) + (w & 0b10101010) & 0b10101010)

Αποτελεσματική κατασκευή τετράδεντρων και οκτάδεντρων[Επεξεργασία | επεξεργασία κώδικα]

Η Z-τάξη μπορεί να χρησιμοποιηθεί για την αποτελεσματική κατασκευή ενός τετραδένδρου (2D) ή οκταδένδρου (3D) για ένα σύνολο σημείων[4][5]. Η βασική ιδέα είναι η ταξινόμηση του συνόλου εισόδου σύμφωνα με τη Z-τάξη. Αφού ταξινομηθούν, τα σημεία μπορούν να αποθηκευτούν σε ένα δυαδικό δέντρο αναζήτησης και να χρησιμοποιηθούν απευθείας, γνωστό ως γραμμικό τετράδεντρο[6], ή μπορούν να χρησιμοποιηθούν για την κατασκευή ενός τετράδεντρου βασισμένου σε δείκτες.

Τα σημεία εισόδου συνήθως κλιμακώνονται σε κάθε διάσταση ώστε να είναι θετικοί ακέραιοι αριθμοί, είτε ως αναπαράσταση σταθερού σημείου στο μοναδιαίο εύρος [0, 1] είτε σε αντιστοιχία με το μέγεθος λέξης της μηχανής. Και οι δύο αναπαραστάσεις είναι ισοδύναμες και επιτρέπουν την εύρεση του μη μηδενικού bit πρώτης τάξης σε σταθερό χρόνο. Κάθε τετράγωνο στο τετραγωνικό δέντρο έχει μήκος πλευράς που είναι δύναμη του δύο και γωνιακές συντεταγμένες που είναι πολλαπλάσια του μήκους πλευράς. Δεδομένων δύο οποιωνδήποτε σημείων, το παράγωγο τετράγωνο για τα δύο σημεία είναι το μικρότερο τετράγωνο που εκτείνεται μεταξύ των δύο σημείων. Η παρεμβολή των bits των συνιστωσών x και y κάθε σημείου ονομάζεται ανάμειξη των x και y και μπορεί να επεκταθεί σε υψηλότερες διαστάσεις[4].

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

Η λειτουργία Αποκλειστική διάζευξη αποκλείει ή αποκρύπτει τα πιο σημαντικά bit για τα οποία οι δύο συντεταγμένες είναι ίδιες. Δεδομένου ότι η σειρά ανακάτεψης των δεδομένων παρεμβάλλει τα πιο σημαντικά bits με τα λιγότερο σημαντικά bits, ο προσδιορισμός της συντεταγμένης της οποίας το πιο σημαντικό bit είναι το μεγαλύτερο προσδιορίζει το πρώτο bit της σειράς ανακάτεψης που διαφέρει και η συντεταγμένη αυτή μπορεί να χρησιμοποιηθεί για τη σύγκριση των δύο σημείων[7] , όπως φαίνεται στον ακόλουθο κώδικα Python: 

def cmp_zorder(lhs, rhs) -> bool:
    """Compare z-ordering."""
    # Assume lhs and rhs array-like objects of indices.
    assert len(lhs) == len(rhs)
    # Will contain the most significant dimension.
    msd = 0
    # Loop over the other dimensions.
    for dim in range(1, len(lhs)):
        # Check if the current dimension is more significant
        # by comparing the most significant bits.
        if less_msb(lhs[msd] ^ rhs[msd], lhs[dim] ^ rhs[dim]):
            msd = dim
    return lhs[msd] < rhs[msd]

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

def less_msb(x: int, y: int) -> bool:
    return x < y and x < (x ^ y)

Είναι επίσης δυνατή η σύγκριση αριθμών κινητής υποδιαστολής με την ίδια τεχνική. Η συνάρτηση less_msb τροποποιείται ώστε να συγκρίνει πρώτα τους εκθέτες. Μόνο όταν αυτοί είναι ίσοι χρησιμοποιείται η τυπική συνάρτηση less_msb στη mantissa.[8] [9]

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

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

Αντί να δημιουργηθεί ένα τετράδεντρο με βάση δείκτες, τα σημεία μπορούν να διατηρηθούν σε ταξινομημένη σειρά σε μια δομή δεδομένων, όπως ένα δυαδικό δέντρο αναζήτησης. Αυτό επιτρέπει την προσθήκη και αφαίρεση σημείων σε O'(log n) χρόνο. Δύο τετράδεντρα μπορούν να συγχωνευθούν ενώνοντας τα δύο σύνολα ταξινομημένων σημείων και αφαιρώντας τα αντίγραφα. Τα σημεία μπορούν να εντοπιστούν αναζητώντας τα σημεία πριν και μετά το ζητούμενο σημείο στην ταξινομημένη σειρά. Εάν το τετράδεντρο είναι συμπιεσμένο, ο προηγούμενος κόμβος που βρέθηκε μπορεί να είναι ένα αυθαίρετο φύλλο μέσα στον συμπιεσμένο κόμβο ενδιαφέροντος. Σε αυτή την περίπτωση, είναι απαραίτητο να βρεθεί ο πρόδρομος του ελάχιστου κοινού προγόνου μεταξύ του σημείου ερώτησης και του φύλλου που βρέθηκε.[10]

Χρήση με μονοδιάστατες δομές δεδομένων για αναζητήσεις εύρους[Επεξεργασία | επεξεργασία κώδικα]

Μέσω της παρεμβολής bit, οι εγγραφές της βάσης δεδομένων μετατρέπονται σε μια (ενδεχομένως πολύ μεγάλη) ακολουθία bit. Οι ακολουθίες bit ερμηνεύονται ως δυαδικοί αριθμοί και τα δεδομένα ταξινομούνται ή ευρετηριάζονται με βάση τις δυαδικές τιμές, χρησιμοποιώντας οποιαδήποτε από τις μονοδιάστατες δομές δεδομένων που αναφέρθηκαν στην εισαγωγή. Εντούτοις, κατά την αναζήτηση ενός πολυδιάστατου εύρους αναζήτησης σε αυτά τα δεδομένα, η δυαδική αναζήτηση δεν είναι πραγματικά αποτελεσματική. Παρόλο που η Z-τάξη διατηρεί καλά την τοπικότητα, απαιτείται ένας αλγόριθμος για τον υπολογισμό, από ένα σημείο που συναντάται στη δομή δεδομένων, της επόμενης πιθανής τιμής Ζ που βρίσκεται εντός του πολυδιάστατου εύρους αναζήτησης:

Σε αυτό το παράδειγμα, το εύρος που ερωτάται (x = 2, ..., 3, y = 2, ..., 6) υποδεικνύεται από το διακεκομμένο ορθογώνιο. Η υψηλότερη τιμή Z (MAX) είναι 45. Σε αυτό το παράδειγμα, η τιμή F = 19 συναντάται κατά την αναζήτηση μιας δομής δεδομένων με αυξανόμενη κατεύθυνση τιμών Ζ, οπότε θα πρέπει να αναζητήσουμε στο διάστημα μεταξύ F και MAX (διαγραμμισμένη περιοχή). Για να επιταχύνουμε την αναζήτηση, θα μπορούσαμε να υπολογίσουμε την επόμενη τιμή Z που βρίσκεται στο εύρος αναζήτησης, που ονομάζεται BIGMIN (36 στο παράδειγμα) και να αναζητήσουμε μόνο στο διάστημα μεταξύ BIGMIN και MAX (έντονες τιμές), παρακάμπτοντας έτσι το μεγαλύτερο μέρος της διαγραμμισμένης περιοχής. Η αναζήτηση προς φθίνουσα κατεύθυνση είναι ανάλογη με το LITMAX που είναι η υψηλότερη τιμή Z στην περιοχή αναζήτησης χαμηλότερη από F. Το πρόβλημα BIGMIN διατυπώθηκε για πρώτη φορά και η λύση του παρουσιάστηκε από τους Tropφ και Χερτζόγκ.[11]

Παρέχεται εκτενής επεξήγηση του αλγορίθμου υπολογισμού LITMAX/BIGMIN, μαζί με πηγαίο κώδικα Πασκάλ (3D, εύκολα προσαρμόσιμος στο nD) και συμβουλές για τον τρόπο χειρισμού δεδομένων κινητής υποδιαστολής και ενδεχομένως αρνητικών δεδομένων 2021 by Tropf: Εδώ, δεν γίνεται ρητή παρεμβολή bit- η δομή δεδομένων έχει απλώς δείκτες στις αρχικές (αταξινόμητες) εγγραφές της βάσης δεδομένων. Με μια γενική συνάρτηση σύγκρισης εγγραφών (μεγαλύτερο-λιγότερο-ίσο, με την έννοια της τιμής z), αποφεύγονται οι επιπλοκές με το μήκος ακολουθιών bit που υπερβαίνει το μήκος λέξης του υπολογιστή και ο κώδικας μπορεί εύκολα να προσαρμοστεί σε οποιονδήποτε αριθμό διαστάσεων και οποιοδήποτε μήκος λέξης-κλειδιού εγγραφής.

Καθώς η προσέγγιση δεν εξαρτάται από τη μονοδιάστατη δομή δεδομένων που επιλέγεται, εξακολουθεί να υπάρχει ελεύθερη επιλογή της διάρθρωσης των δεδομένων, οπότε γνωστές μέθοδοι όπως τα ισορροπημένα δέντρα μπορούν να χρησιμοποιηθούν για την αντιμετώπιση δυναμικών δεδομένων και η διατήρηση της ισορροπίας του δέντρου κατά την εισαγωγή ή τη διαγραφή απαιτεί χρόνο O(log n). Η μέθοδος χρησιμοποιείται επίσης στα UB-δέντρα (balanced), [12] με το όνομα "GetNextZ-address" για το BIGMIN.

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

Η εφαρμογή της μεθόδου ιεραρχικά (με βάση τη δομή των δεδομένων), ενδεχομένως με αύξουσα και φθίνουσα σειρά, οδηγεί σε μια εξαιρετικά αποτελεσματική πολυδιάστατη αναζήτηση που είναι σημαντική σε εμπορικές και τεχνικές εφαρμογές, παραδείγματος χάριν ως η βασική διαδικασία για τις αναζητήσεις πλησιέστερων γειτόνων. Η Ζ-τάξη είναι μία από τις λίγες πολυδιάστατες μεθόδους πρόσβασης που έχουν βρει το δρόμο τους σε εμπορικά συστήματα βάσεων δεδομένων [13]. Η µέθοδος χρησιµοποιείται σε διάφορες τεχνικές εφαρµογές σε διάφορους τοµείς [14] και σε εµπορικά συστήµατα βάσεων δεδοµένων[15].

Σχετικές δομές[Επεξεργασία | επεξεργασία κώδικα]

Ως εναλλακτική λύση έχει προταθεί η καμπύλη Χίλμπερτ, καθώς έχει καλύτερη συμπεριφορά ως προς τη διατήρηση της τάξης[5] και, μάλιστα, χρησιμοποιήθηκε σε ένα βελτιστοποιημένο δείκτη, τη S2-γεωμετρία[16].

Εφαρμογές[Επεξεργασία | επεξεργασία κώδικα]

Ο πίνακας πρόσθεσης για x + 2y όπου x και y ανήκουν και τα δύο στην Ακολουθία Μοσέρ - ντε Μπρούιν (Moser-de Bruijn), και η καμπύλη Z-τάξης που συνδέει τα αθροίσματα με αριθμητική σειρά

Γραμμική άλγεβρα[Επεξεργασία | επεξεργασία κώδικα]

Ο αλγόριθμος του Στράσεν για τον πολλαπλασιασμό πινάκων βασίζεται στη διαίρεση πινάκων σε τέσσερα τμήματα, και στη συνέχεια στην αναδρομική διαίρεση κάθε ενός από αυτά τα τμήματα σε τέσσερα μικρότερα τεμάχια, έως ότου τα τμήματα αποτελούνται από μοναδικά στοιχεία (ή πιο πρακτικά: έως ότου οι πίνακες είναι τόσο μικροί ώστε ο τετριμμένος αλγόριθμος ακολουθίας Moser-de Bruijn να είναι ταχύτερος). Η διάταξη των στοιχείων του πίνακα με τη σειρά Z βελτιώνει τότε την τοπικότητα και έχει το πρόσθετο πλεονέκτημα (σε σύγκριση με τη μείζονα σειρά γραμμών ή στηλών) ότι η υπορουτίνα πολλαπλασιασμού δύο μπλοκ δεν χρειάζεται να γνωρίζει το συνολικό μέγεθος του πίνακα, παρά μόνο το μέγεθος των μπλοκ και τη θέση τους στη μνήμη. Η αποτελεσματική χρήση του πολλαπλασιασμού Στράσεν με Τάξη-Ζ έχει αποδειχθεί, βλ. το άρθρο των Βάλσαλαμ και Σκίλουμ το 2002[17].

Οι Buluç και άλλοι παρουσιάζουν μια δομή δεδομένων αραιών πινάκων που ταξινομεί τα μη μηδενικά στοιχεία του σε τάξη-Ζ για να επιτρέπει τον παράλληλο πολλαπλασιασμό πινάκων-διανυσμάτων[18].

Οι πίνακες της γραμμικής άλγεβρας μπορούν επίσης να διανύονται με τη χρήση μιας καμπύλης πλήρωσης χώρου[19]. Η διάσχιση με την καμπύλη Ζ επιτρέπει την αποτελεσματική πρόσβαση στην ιεραρχία της μνήμης[20]

Χαρτογράφηση υφής[Επεξεργασία | επεξεργασία κώδικα]

Ορισμένες GPU αποθηκεύουν τους χάρτες υφής σε Z-τάξης για να αυξήσουν τη χωρική εντοπιότητα της αναφοράς κατά τη ραστεροποίηση του χάρτη υφής. Αυτό επιτρέπει στις γραμμές της κρυφής μνήμης να αναπαριστούν ορθογώνια πλακίδια, αυξάνοντας την πιθανότητα οι κοντινές προσπελάσεις να βρίσκονται στην κρυφή μνήμη. Σε μεγαλύτερη κλίμακα, μειώνει επίσης την πιθανότητα ακριβών "διαλειμμάτων σελίδας" (δηλαδή το κόστος αλλαγής γραμμών) στην SDRAM/DDRAM. Αυτό είναι σημαντικό διότι η τρισδιάστατη απόδοση περιλαμβάνει αυθαίρετους μετασχηματισμούς (περιστροφές, κλιμάκωση, προοπτική και παραμόρφωση από κινούμενες επιφάνειες).

Αυτές οι μορφές αναφέρονται συχνά ως "swizzled" ή "twiddled" υφές. Μπορούν επίσης να χρησιμοποιηθούν και άλλες μορφές ψηφιδωτού.

πρόβλημα n-σώματος[Επεξεργασία | επεξεργασία κώδικα]

Ο αλγόριθμος Μπαρνς - Χουτ απαιτεί την κατασκευή ενός οκταδένδρου. Η αποθήκευση των δεδομένων ως δέντρο βασισμένο σε δείκτες απαιτεί πολλές διαδοχικές αναφορές δεικτών για την επανάληψη στο οκτάρι με σειρά βάθους (κάτι που είναι δαπανηρό σε μια μηχανή κατανεμημένης μνήμης). Από την άλλη πλευρά, αν αποθηκεύσουμε τα δεδομένα σε έναν πίνακα κατακερματισμού, χρησιμοποιώντας τον κατακερματισμό του οκταδένδρου, η καμπύλη Ζ-τάξης επαναλαμβάνει φυσικά το οκταδένδρο κατά σειρά βάθους.[5]

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. ↑ Discrete Global Grid Systems Abstract Specification, Open Geospatial Consortium, 2017, https://portal.opengeospatial.org/files/15-104r5#.pdf 
  2. ↑ Dugundji, James (1989), Wm. C. Brown, επιμ., Topology, Dubuque (Iowa), σελ. 105, ISBN 0-697-06889-7 
  3. ↑ Morton, G. M. (1966), A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing, Technical Report, Ottawa, Canada: IBM Ltd., https://domino.research.ibm.com/library/cyberdig.nsf/papers/0DABF9473B9C86D48525779800566A39/$File/Morton1966.pdf 
  4. ↑ 4,0 4,1 4,2 Bern, M.; Eppstein, D.; Teng, S.-H. (1999), «Parallel construction of quadtrees and quality triangulations», Int. J. Comput. Geom. Appl. 9 (6): 517–532, doi:10.1142/S0218195999000303 .
  5. ↑ 5,0 5,1 5,2 Warren, M. S.; Salmon, J. K. (1993), «A parallel hashed Oct-Tree N-body algorithm», Proceedings of the 1993 ACM/IEEE conference on Supercomputing - Supercomputing '93, Portland, Oregon, United States: ACM Press, σελ. 12–21, doi:10.1145/169627.169640, ISBN 978-0-8186-4340-8, http://portal.acm.org/citation.cfm?doid=169627.169640 
  6. ↑ Gargantini, I. (1982), «An effective way to represent quadtrees», Communications of the ACM 25 (12): 905–910, doi:10.1145/358728.358741 .
  7. ↑ 7,0 7,1 Chan, T. (2002), «Closest-point problems simplified on the RAM», ACM-SIAM Symposium on Discrete Algorithms, http://tmc.web.engr.illinois.edu/ram_soda.ps .
  8. ↑ Κολαΐτης, Μ. (1976). Αγγλοελληνικόν Λεξικόν των Θεωρητικών και Εφηρμοσμένων Μαθηματικών. ΤΕΕ. 
  9. ↑ Connor, M.; Kumar, P (2009), «Fast construction of k-nearest neighbour graphs for point clouds», IEEE Transactions on Visualization and Computer Graphics, http://compgeom.com/~piyush/papers/tvcg_stann.pdf, ανακτήθηκε στις 2023-12-07 
  10. ↑ Har-Peled, S. (2010), Data structures for geometric approximation, http://www.madalgo.au.dk/img/SS2010/Course%20Material/Data-Structures%20for%20Geometric%20Approximation%20by%20Sariel%20Har-Peled.pdf 
  11. ↑ Tropf, H.; Herzog, H. (1981), «Multidimensional Range Search in Dynamically Balanced Trees», Angewandte Informatik 2: 71–77, http://www.vision-tools.com/h-tropf/multidimensionalrangequery.pdf .
  12. ↑ Ramsak, Frank; Markl, Volker; Fenk, Robert; Zirkel, Martin; Elhardt, Klaus; Bayer, Rudolf (2000), «Integrating the UB-tree into a Database System Kernel», Int. Conf. on Very Large Databases (VLDB), σελ. 263–272, http://www.mistral.in.tum.de/results/publications/RMF+00.pdf 
  13. ↑ https://dl.acm.org/doi/pdf/10.1145/280277.280279 Volker Gaede, Oliver Günther: Multidimensional access methods. ACM Computing Surveys volume=30 issue=2 pages=170–231 1998.
  14. ↑ Annotated list of research papers to technical applications using z-order range search, https://www.vision-tools.com/fileadmin/unternehmen/HTR/Z-Curve_Technical_Applications.pdf 
  15. ↑ Annotated list of research papers to databases using z-order range search, https://www.vision-tools.com/fileadmin/unternehmen/HTR/Z-Curve_Database_Systems.pdf 
  16. ↑ S2 Geometry, https://s2geometry.io/, ανακτήθηκε στις 2023-12-07 
  17. ↑ Vinod Valsalam, Anthony Skjellum: A framework for high-performance matrix multiplication based on hierarchical abstractions, algorithms and optimized low-level kernels. Concurrency and Computation: Practice and Experience 14(10): 805-839 (2002)[1][2]
  18. ↑ Buluç, Aydın; Fineman, Jeremy T.; Frigo, Matteo; Gilbert, John R.; Leiserson, Charles E. (2009), «Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks», ACM Symp. on Parallelism in Algorithms and Architectures, http://gauss.cs.ucsb.edu/~aydin/csb2009.pdf, ανακτήθηκε στις 2023-12-07 
  19. ↑ Martin Perdacher: Space-filling curves for improved cache-locality in shared memory environments. PhD thesis, University of Vienna 2020
  20. ↑ Martin Perdacher, Claudia Plant, Christian Böhm: Improved Data Locality Using Morton-order Curve on the Example of LU Decomposition. IEEE BigData 2020: pp. 351–360


Ανακτήθηκε από "https://el.wikipedia.org/w/index.php?title=Καμπύλη_Z-τάξης&oldid=10379494"