Abstract-A fyllnadskurva (SFC) är en närhetsbevarande kartläggning från ett utrymme med hög dimension till ett rum med en enda dimension. SFC har i stor utsträckning använts för att hantera flerdimensionella data i parallell databehandling, vetenskaplig databehandling och databaser. Det allmänna målet för en SFC är att punkter som är nära varandra i högdimensionellt utrymme också är nära varandra i det endimensionella rummet. Även om SFC har använts i stor utsträckning, är det ännu inte klart i vilken utsträckning närheten kan bevaras av en SFC. Vi anser att naturliga mått, inklusive "nerest neighbor stretch" av en SFC, som mäter i vilken utsträckning en SFC bevarar närheten. Vi visar först ett kraftfullt negativt resultat, att det finns en inneboende lägre gräns på sträckan av alla SFC. Vi visar sedan att sträckan av den allmänt använda Z-kurvan ligger inom en faktor på 1,5 från den optimala, oberoende av antalet dimensioner. Vidare visar vi att en mycket enkel SFC också uppnår samma sträcka som Z-kurvan. Våra resultat gäller för SFC i alla dimensioner d sådana att d är en konstant.
Xu och Tirthapura REF visade sig vara en lägre gräns på "nerest-neighbor stretch" av alla SFC.
A Lower Bound on Proximity Preservation by Space Filling Curves
{'venue': '2012 IEEE 26th International Parallel and Distributed Processing Symposium', 'journal': '2012 IEEE 26th International Parallel and Distributed Processing Symposium', 'mag_field_of_study': ['Computer Science']}