基于狀態(tài)視圖的高效Hilbert編碼和解碼算法

賈連印; 陳明鮮; 李孟娟; 游進(jìn)國(guó); 丁家滿

doi:10.11999/JEIT190501

基于狀態(tài)視圖的高效Hilbert編碼和解碼算法

doi: 10.11999/JEIT190501

1.
昆明理工大學(xué)信息與自動(dòng)化學(xué)院昆明 650500
2.
云南省計(jì)算機(jī)應(yīng)用重點(diǎn)實(shí)驗(yàn)室昆明 650500
3.
云南師范大學(xué)圖書館技術(shù)部昆明 650500

基金項(xiàng)目: 國(guó)家自然科學(xué)基金(61562054)，國(guó)家留學(xué)基金委公派留學(xué)項(xiàng)目(201908530036)

詳細(xì)信息

作者簡(jiǎn)介:
賈連?。耗校?978年生，副教授，研究方向?yàn)閿?shù)據(jù)庫(kù)、信息檢索、并行計(jì)算

陳明鮮：男，1994年生，碩士生，研究方向?yàn)閳D像處理、信息檢索和自然語(yǔ)言處理

李孟娟：女，1983年生，館員，研究方向?yàn)椴⑿杏?jì)算和信息檢索

游進(jìn)國(guó)：男，1978年生，副教授，研究方向?yàn)閿?shù)據(jù)庫(kù)和數(shù)據(jù)倉(cāng)庫(kù)

丁家滿：男，1974年生，副教授，研究方向?yàn)閿?shù)據(jù)庫(kù)和數(shù)據(jù)挖掘

通訊作者:
丁家滿　tjom2008@126.com

¹⁾對(duì)數(shù)據(jù)不向原點(diǎn)偏斜的情形，可通過(guò)適當(dāng)?shù)淖鴺?biāo)變換，如旋轉(zhuǎn)、平移等，使其盡可能地向原點(diǎn)偏斜。
中圖分類號(hào): TN919.81
計(jì)量
- 文章訪問(wèn)數(shù): 2482
- HTML全文瀏覽量: 1049
- PDF下載量: 79
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2019-07-05
- 修回日期: 2020-02-03
- 網(wǎng)絡(luò)出版日期: 2020-02-27
- 刊出日期: 2020-06-22

State View Based Efficient Hilbert Encoding and Decoding Algorithms

1.
Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
2.
Key Laboratory of Computer Technologies Application of Yunnan Province, Kunming 650500, China
3.
Library of Yunnan Normal University, Kunming 650500, China

Funds: The National Natural Science Foundation of China (61562054), Fund of China Scholarship Council (201908530036)

摘要

摘要:
Hilbert曲線是高維降到1維的重要方法，具有較好的空間聚集和空間連續(xù)性，在地理信息系統(tǒng)、空間數(shù)據(jù)庫(kù)、信息檢索等方面有廣泛的應(yīng)用?，F(xiàn)有Hilbert編碼或解碼算法未考慮輸入數(shù)據(jù)對(duì)編碼或解碼效率的影響，因此將不同輸入數(shù)據(jù)同等對(duì)待。為此，該文通過(guò)設(shè)計(jì)高效的狀態(tài)視圖并結(jié)合快速置位檢測(cè)算法提出高效的免計(jì)前0的Hilbert編碼算法(FZF-HE)和免計(jì)前0的Hilbert解碼算法(FZF-HD)，可快速識(shí)別輸入數(shù)據(jù)前部為0而無(wú)需迭代計(jì)算的部分，從而降低迭代查詢次數(shù)及算法復(fù)雜度，提高編解碼效率。實(shí)驗(yàn)結(jié)果表明，F(xiàn)ZF-HE算法和FZF-HD算法在數(shù)據(jù)均勻分布時(shí)效率稍高于現(xiàn)有算法，而在數(shù)據(jù)偏斜分布時(shí)效率遠(yuǎn)高于現(xiàn)有算法。
- 狀態(tài)視圖 /
- 免計(jì)前0的Hilbert編碼算法 /
- 免計(jì)前0的Hilbert解碼算法 /
- Hilbert曲線
Abstract:
Hilbert curve is an important method for high-dimensional reduction to one-dimensional. It has good characteristics of spatial aggregation and spatial continuity and is widely used in geographic information system, spatial databases and information retrieval. Existing Hilbert encoding or decoding algorithms do not consider the differences between input data, thus treating them equally. To this end, an efficient Hilbert coding algorithm Front-Zero-Free Hilbert Encoding(FZF-HE) and an efficient decoding algorithm Front-Zero-Free Hilbert Decoding(FZF-HD) are proposed. FZF-HE and FZF-HD can quickly identify the 0 s of the front part of input data before iterative calculation by combining efficient state views and first bit-1 detection algorithm, thus reducing the number of iterations and the complexity of the algorithm, and improving the encoding and decoding efficiency. The experimental results show that efficiencies of these two algorithms are slightly higher than existing algorithms for uniform distributed data, and are much higher than existing algorithms for skew distributed data.
- State view /
- Front-Zero-Free Hilbert Encoding (FZF-HE) /
- Front-Zero-Free Hilbert Decoding (FZF-HD) /
- Hilbert curve
¹⁾對(duì)數(shù)據(jù)不向原點(diǎn)偏斜的情形，可通過(guò)適當(dāng)?shù)淖鴺?biāo)變換，如旋轉(zhuǎn)、平移等，使其盡可能地向原點(diǎn)偏斜。

HTML全文

圖 1 1階、2階和3階Hilbert曲線示意圖

下載: 全尺寸圖片幻燈片

圖 2 1階Hilbert曲線對(duì)應(yīng)的4種狀態(tài)

下載: 全尺寸圖片幻燈片

圖 3 均勻分布下編碼效率對(duì)比

下載: 全尺寸圖片幻燈片

圖 4 $\beta $對(duì)編碼效率的影響

下載: 全尺寸圖片幻燈片

圖 5 $\alpha $對(duì)編碼效率的影響

下載: 全尺寸圖片幻燈片

圖 6 均勻分布下解碼效率對(duì)比

下載: 全尺寸圖片幻燈片

圖 7 $\beta $對(duì)解碼效率的影響

下載: 全尺寸圖片幻燈片

圖 8 $\alpha $對(duì)解碼效率的影響

下載: 全尺寸圖片幻燈片

表 1 編碼狀態(tài)視圖

狀態(tài)	0	0	0	0	1	1	1	1	2	2	2	2	3	3	3	3
坐標(biāo)	00	01	10	11	00	01	10	11	00	01	10	11	00	01	10	11
編碼	00	01	11	10	00	11	01	10	10	11	01	00	10	01	11	00
下階狀態(tài)	1	0	3	0	0	2	1	1	2	1	2	3	3	3	0	2

下載: 導(dǎo)出CSV

表 2 解碼狀態(tài)視圖

狀態(tài)	0	0	0	0	1	1	1	1	2	2	2	2	3	3	3	3
編碼	00	01	10	11	00	01	10	11	00	01	10	11	00	01	10	11
坐標(biāo)	00	01	11	10	00	10	11	01	11	10	00	01	11	01	00	10
下階狀態(tài)	1	0	0	3	0	1	1	2	3	2	2	1	2	3	3	0

下載: 導(dǎo)出CSV

表 3 FZF-HE算法

輸入：X，橫坐標(biāo)
Y，縱坐標(biāo)
n，階
輸出：Hilbert編碼$Z$
(1) Z←0
(2) $p$←${\rm{msb}}(\max(X,Y))$//置位檢測(cè)
(3) $t$←($n$-$p$-1)%2//計(jì)算第$n$-$p$階狀態(tài)
(4) for $i$ from $n$-$p$ to $n$
(5) $Z{\rm{ = }}Z{{ < < 2 \| {\rm{Key}}[}}t{\rm{][}}{x_i}{\rm{][}}{y_i}{\rm{] }}$//查Key視圖
(6) $t{\rm{ = Type[}}t{\rm{][}}{x_i}{\rm{][}}{y_i}{\rm{]}}$//查Type視圖

下載: 導(dǎo)出CSV

表 4 FZF-HD算法

輸入：$Z$，Hilbert編碼
n，階
輸出：X，橫坐標(biāo)
Y，縱坐標(biāo)
(1) $X$, $Y$←0
(2) $p$←${\rm{msb}}(Z)$//置位檢測(cè)
(3) $t$←($n$-$p$/2-1)//計(jì)算第$n$-$p$/2階狀態(tài)
(4) for $i$ from $n$-$p$/2 to $n$
(5) ${\rm{coord}} = {\rm{InvKey}}[t][{z_{2i - 1}}{z_{2i}}]$ //查InvKey視圖
(6) $ Y = Y < < 1 \| {\rm{coord}} \& 0{\rm{x}}1 $
$ X = X < < 1 \| {\rm{coord}} > > 1\& 0{\rm{x}}1 $
(7) $t = {\rm{InvType}}[t][{z_{2i - 1}}{z_{2i}}]$//查InvType視圖

下載: 導(dǎo)出CSV

參考文獻(xiàn)(25)

GUNTHER S and STOCCO L. Generation of spatial orders and space-filling curves[J]. IEEE Transactions on Image Processing, 2015, 24(6): 1791–1800. doi: 10.1109/TIP.2015.2409571

周映虹, 馬爭(zhēng)鳴. 基于層次模型的重要性編碼算法[J]. 電子與信息學(xué)報(bào), 2009, 31(6): 1497–1500.

ZHOU Yinghong and MA Zhengming. A significance coding algorithm based on layer model[J]. Journal of Electronics &Information Technology, 2009, 31(6): 1497–1500.

CHEN Lu, GAO Yunjun, LI Xinhan, et al. Efficient metric indexing for similarity search and similarity joins[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(3): 556–571. doi: 10.1109/TKDE.2015.2506556

SINGH H and BAWA S. A survey of traditional and mapReduceBased spatial query processing approaches[J]. ACM SIGMOD Record, 2017, 46(2): 18–29. doi: 10.1145/3137586.3137590

ABDULJABBAR M, MARKOMANOLIS G S, IBEID H, et al. Communication reducing algorithms for distributed hierarchical N-Body problems with boundary distributions[C]. The 32nd International Supercomputing Conference, Frankfurt, Germany, 2017: 79–96.

LIU Hui, WANG Kun, YANG Bo, et al. Dynamic load balancing using hilbert space-filling curves for parallel reservoir simulations[C]. The SPE Reservoir Simulation Conference, Montgomery, USA, 2017. doi: 10.2118/182613-MS.

HAN Guangjie, XUAN Xuan, LIU Li, et al. A disaster management-oriented path planning for mobile anchor node-based localization in wireless sensor networks[J]. IEEE Transactions on Emerging Topics in Computing, 2020, 8(1): 115–125. doi: 10.1109/TETC.2017.2687319

KONG Lingping, PAN J S, SUNG T W, et al. An energy balancing strategy based on hilbert curve and genetic algorithm for wireless sensor networks[J]. Wireless Communications and Mobile Computing, 2017, 2017: 5720659.

BOHM C, PERDACHER M, and PLANT C. A novel hilbert curve for cache-locality preserving loops[J]. IEEE Transactions on Big Data, To be published. doi: 10.1109/TBDATA.2018.2830378

MORTON G M. A computer oriented geodetic data base and a new technique in file sequencing[EB/OL]. https://domino.research.ibm.com/library/cyberdig.nsf/0/0dabf9473b9c86d48525779800566a39?OpenDocument, 1966.

BUTZ A R. Alternative algorithm for Hilbert's space-filling curve[J]. IEEE Transactions on Computers, 1971, C-20(4): 424–426. doi: 10.1109/T-C.1971.223258

MOON B, JAGADISH H V, FALOUTSOS C, et al. Analysis of the clustering properties of the hilbert space-filling curve[J]. IEEE Transactions on Knowledge and Data Engineering, 2001, 13(1): 124–141. doi: 10.1109/69.908985

NAGARKAR P, CANDAN K S, and BHAT A. Compressed spatial hierarchical bitmap (cSHB) indexes for efficiently processing spatial range query workloads[J]. Proceedings of The VLDB Endowment, 2015, 8(12): 1382–1393. doi: 10.14778/2824032.2824038

CHRISTOFORAKI M, HE Jinru, DIMOPOULOS C, et al. Text vs. space: Efficient geo-search query processing[C]. The 20th ACM International Conference on Information and Knowledge Management, Glasgow, UK, 2011: 423–432.

FISHER A J. A new algorithm for generating Hilbert curves[J]. Practice and Experience, 1986, 16(1): 5–12. doi: 10.1002/spe.4380160103

李紹俊, 鐘耳順, 王少華, 等. 基于狀態(tài)轉(zhuǎn)移矩陣的Hilbert碼快速生成算法[J]. 地球信息科學(xué)學(xué)報(bào), 2014, 16(6): 846–851.

LI Shaojun, ZHONG Ershun, WANG Shaohua, et al. An algorithm for Hilbert ordering code based on state-transition matrix[J]. Journal of Geo-Information Science, 2014, 16(6): 846–851.

XCTORRES. Hilbert_spatial_index[EB/OL]. https://github.com/xcTorres/hilbert_spatial_index, 2017.

BURKARDT J. HILBERT_CURVE convert between 1D and 2D coordinates of Hilbert curve[EB/OL]. http://people.math.sc.edu/Burkardt/c_src/hilbert_curve/hilbert_curve.html, 2015.

MOORE D. Fast Hilbert curve generation, sorting, and range queries[EB/OL]. https://github.com/Cheedoong/hilbert, 2016.

曹雪峰, 萬(wàn)剛, 張宗佩. 緊致的Hilbert曲線Gray碼索引算法[J]. 測(cè)繪學(xué)報(bào), 2016, 45(S1): 90–98. doi: 10.11947/j.AGCS.2016.F010

CAO Xuefeng, WAN Gang, and ZHANG Zongpei. Compact Hilbert curve index algorithm based on Gray code[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(S1): 90–98. doi: 10.11947/j.AGCS.2016.F010

LI R. Hilbert range query decomosition[EB/OL]. https://github.com/cloudray8580/Hilbert RangeQueryDecomosition, 2019.

ZHANG Jian and KAMATA S I. A generalized 3-D Hilbert scan using look-up tables[J]. Journal of Visual Communication and Image Representation, 2012, 23(3): 418–425. doi: 10.1016/j.jvcir.2011.12.005

LIU Hui, CUI Tao, LENG Wei, et al. Encoding and decoding algorithms for arbitrary dimensional Hilbert order[J]. 2016, arXiv: 1601.01274.

劉輝, 冷偉, 崔濤. 高維Hilbert曲線的編碼與解碼算法設(shè)計(jì)[J]. 數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用, 2015, 36(1): 42–58.

LIU Hui, LENG Wei, and CUI Tao. Development of encoding and decoding algorithms for high dimensional Hilbert curves[J]. Journal on Numerical Methods and Computer Applications, 2015, 36(1): 42–58.

ROSETTA. Find first and last set bit of a long integer[EB/OL]. http://rosettacode.org/wiki/Find_first_and_last_set_bit_of_a_long_integer, 2019.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問(wèn)統(tǒng)計(jì)