Cantor空間填充曲線之演算法探討

SFC(Space-Filling Curve)爲於二維空間中，對網格內的節點進行一維排序，即二維空間一維編碼法。一般資料庫內的資料儲存皆爲一維形式的安排，若藉由二維方式適當處理，當可提昇資料存取的效率。 SFC有許多種，依性質可分爲「遞迴式」與「非遞迴式」兩大類。迄今已有不少文獻探討其路徑編碼的演算法，但大多敘述複雜且不易明瞭，少見細膩的說明步驟。於九種SFC的近鄰性(proximity)研究顯示，以非遞迴式的Cantor SFC爲最優，故選取該SFC加以闡述。關於SFC的評估，本研究採用四種指標：路徑全長、單位長度種類、平均四強鄰距離和與平均四弱鄰距離和，各評估指標並以多項式函數形式表示，引數爲網格大小(c)，其係數則以多項式迴歸求得之，其中部分的係數爲正合(exact)。至於SFC的演算法，其時問的複雜度與設計的方式有關。分析結果顯示，捷徑法的複雜度爲O(1)；逐步法則爲O(c^2)。

關鍵字

空間填充曲線；演算法；複雜度

並列摘要

A space-filling curve is a way of mapping the two-dimensional space into one-dimensional. Because of data arrangement in the database being in one-dimensional form, using an appropriate SFC may improve the query efficiency. There are a lot of SFCs in the literatures. Each SFC has its advantages and disadvantages. An evaluation index of a comprehensive study on some typical SFCs has shown that Cantor's SFC has the best proximity. This study focuses on the encoding algorithm and analysis of Cantor's SFC. An evaluation index has been made on Cantor's SFC, namely ”average sum of eight nearest neighbors distance”. The index is concluded as a linear function. The argument is the size of domain (c in short) while c is up to 4096. Both the coefficients are solved by means of regression analysis. As for the time complexity of algorithms for Cantor's SFC, it is obviously depends on the designing scheme. Results show that the complexities of the short-cut approach is O (1) while the stepwise approach is O (c^2).

並列關鍵字

space-filling curve ； algorithm ； complexity

參考文獻

Breinholt, G.,Schierz C.,ACM (Trans.)(1998).Algorithm 781: Generating Hilbert`s Space-Filling Curves by Recursion.On Mathematical Software.24(2),184-189.