数值计算与计算机应用
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  联系我们 |  在线办公 | 
数值计算与计算机应用  2015, Vol. 36 Issue (1): 42-58    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |  Next Articles  
高维Hilbert曲线的编码与解码算法设计
刘辉, 冷伟, 崔涛
LSEC, 中国科学院数学与系统科学研究院, 计算数学研究所, 北京 100190
DEVELOPMENT OF ENCODING AND DECODING ALGORITHMS FOR HIGH DIMENSIONAL HILBERT CURVES
Liu Hui, Leng Wei, Cui Tao
LSEC, Institute of Computational Mathematics, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, Beijing 100190, China
 全文: PDF (528 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 本文设计了任意维空间中具有线性复杂度的希尔伯特序编码解码算法并提出了希尔伯特 空间填充曲线的一种变体. 本文同时对编码解码算法进行了改进, 设计了复杂度更低的算法, 降低了计算量. 文中给出的希尔伯特空间填 充曲线的变体保证曲线的编码顺序不随曲线阶数的改变而变化.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词Hilbert曲线   高维   解码   编码     
Abstract: We designed encoding and decoding algorithms for high dimensional Hilbert order. Hilbert order has good locality, and it has wide applications in various fields in computer science, such as memory management, database, and dynamic load balancing. We analyzed existing algorithms for computing 2D and 3D Hilbert order, and designed improved algorithms for computing Hilbert order in arbitrary space dimensions. We also proposed an alternate form of Hilbert space filling curve which has the advantage of preserving the ordering between different levels.
Key wordsHilbert curves   high dimension   encoding   decoding   
收稿日期: 2014-10-18;
基金资助:

本文由国家973项目(2011CB309703), 国家863项目 (2012AA01A309), 国家自然科学基金(11171334, 11321061, 11101417)和中国科学院国家数学与交叉科学中心资助.

引用本文:   
. 高维Hilbert曲线的编码与解码算法设计[J]. 数值计算与计算机应用, 2015, 36(1): 42-58.
. DEVELOPMENT OF ENCODING AND DECODING ALGORITHMS FOR HIGH DIMENSIONAL HILBERT CURVES[J]. Journal of Numerical Methods and Computer Applicat, 2015, 36(1): 42-58.
 
[1] Boman E, Devine K, Heaphy R, Hendrickson B, Leung V, Riesen L A, Vaughan C, Catalyurek U, Bozdag D, Mitchell W and Teresco J. Zoltan v3: Parallel Partitioning, Load Balancing and Data- Management Services, User's Guide, Sandia National Laboratories Tech. Rep. SAND2007-4748W, 2007.
[2] Boman E, Devine K, Heaphy R, Hendrickson B, Leung V, Riesen L A, Vaughan C, Catalyurek U, Bozdag D and Mitchell W. Zoltan v3: Parallel Partitioning, Load Balancing and Data- Management Services, Developer's Guide, Sandia National Laboratories Tech. Rep. SAND2007- 4749W, 2007.
[3] Campbell P M, Devine K D, Flaherty J E, Gervasio L G and Teresco J D. Dynamic octree load balancing using space-filling curves, Technical Report, CS-03-01, 2003.
[4] Zhang L . A Parallel Algorithm for Adaptive Local Refinement of Tetrahedral Meshes Using Bisection[J]. Numer. Math.: Theory, Methods and Applications, 2009, (2): 65-89.
[5] Liu H, Zhang L. Parallel implementation of commonly used marking strategies in the adaptive finite element toolbox PHG[J]. Journal on Numerical Methods and Computer Applications, 2009, 30(4): 315-312.
[6] Liu H. Dynamic load balancing on adaptive unstructured meshes[J]. High Performance Computing and Communications, 10th IEEE International Conference on, 2008, (0): 870-875.
[7] Hans Sagan, Space-Filling Curves, Springer-Veriag, New York, 1994.
[8] Velho L and J Gomes de Miranda. Digital halftoning with space-filling curves[J]. Computer Graphics, 1991, (25): 81-90.
[9] Liu H, Yu S and Chen Z. Development of Algebraic Multigrid Solvers Using GPUs. SPE Reservoir Simulation Symposium, Feb 2013, Houston, USA.
[10] Morton G M. A computer Oriented Geodetic DataBase and a New Technique in File Sequencing. Technical Report, Ottawa, Canada, 1966.
[11] Jin Guohua and Mellor-Crummey John. Using Space-filling Curves for Computation Reordering, In Proceedings of the Los Alamos Computer Science Institute Sixth Annual Symposium, 2005.
[12] Alpert C J and Kahng A B. Multi-way partitioning via spacefilling curves and dynamic programming. In Proceedings of the 31st Annual Conference on Design Automation Conference, 1994, 652-657.
[13] Liu H, Yu S, Chen Z, Hsieh B and Shao L. Parallel Preconditioners for Reservoir Simulation on GPU. LACPEC/ SPE-152811, SPE Latin America and Caribbean Petroleum Engineering Conference, 16-18 April, Mexico City, Mexico, 2012.
[14] Liu H, Yu S, Chen Z, Hsieh B and Shao L. Sparse Matrix-Vector Multiplication on NVIDIA GPU[J]. International Journal of Numerical Analysis & Modeling, Series B, 2012, 3(2): 185-191.
[15] Abel D and Mark D. A comparative analysis of some two-dimensional orderings[J]. International J. of Geographical Information and Systems, 1990, 4(1): 21-31.
[16] Bartholdi III J and Goldsman P. Vertex-labeling algorithms for the Hilbert spacefilling curve, Software: Practice and Experience, 2001(31): 395-408.
[17] Böhm C, Berchtold S and Keim D A. Seaching in hign-dimensional spaces: Index structures for improving the performance of multimedia databases[J]. ACM Computing Surveys, 2001, (33): 322-373.
[18] Butz A R. Space filling curves and mathematical programming[J]. Information and Control, 1968, (12): 314-330.
[19] Challacombe M. A general parallel sparse-blocked matrix multiply for linear scaling scf theory[J]. Computer Physics Communications, 2000, 128(1-2): 93-107.
[20] Chen Z, Liu H and Yang B. Parallel triangular solvers on GPU. Proceedings of International Workshop on Data-Intensive Scientific Discovery (DISD), Shanghai University, Shanghai, China, August 1-4, 2013.
[21] Liu Hui, Chen Zhangxin and Yang Bo. Accelerating preconditioned iterative linear solver on GPU[J]. International Journal of Numerical Analysis and Modelling: Series B, 2014, 5(1-2): 136- 146.
[22] Liu Hui, Chen Zhangxin, Yu Song, Ben Hsieh and Lei Shao. Development of a Restricted Additive Schwarz preconditioner for Sparse Linear Systems on NVIDIA GPU[J]. International Journal of Numerical Analysis and Modelling: Series B, 2014, 5(1-2): 13-20.
[23] Chen Zhangxin, Liu Hui and Yang Bo. Accelerating iterative linear solvers using multiple graphical processing units[J]. International Journal of Computer Mathematics, to appear.
[24] Hu Y C, Cox A and Zwaenepoel W. Improving fine-grained irregular shared-memory benchmarks by data reordering. In Proceedings of the 2000 ACM/IEEE Conference on Supercomputing, Dallas, TX, 2000.
[25] Jin G, Mellor-Crummey J and Fowler R. Increasing temporal locality with skewing and recursive blocking. In Proceedings of the 2001 ACM/IEEE Conference on Supercomputing, Denver, CO, Nov 2001.
[26] Matias Y and Shamir A. A video scrambling technique based on space filling curve. In Advances in Cryptology-CRYPTO'89, 1987, 398-416.
[27] Deng Hui, Chen Zhangxin, Bao Xia, Wei Yizheng, Liu Hui, Dong Chao Charlie. Geomechanical and Thermal Simulation of ES-SAGD Process. SPE-148847-MS, Canadian Unconventional Resources Conference, 15-17 November, Alberta, Canada, 2011.
[28] Bao Xia, Deng Hui, Zhong He, Liu Hui, Chen Zhangxin John, Dong Chao Charlie. Coupled Geomechanical and Thermal Simulation of SAGD Process. SPE-165423-MS, SPE Heavy Oil Conference-Canada, 11-13 June, Calgary, Alberta, Canada, 2013.
[29] Han Hwansoo and Tseng Chau-wen. Improving Locality For Adaptive Irregular Scientific Codes. In 13 th Int'l Workshop on Languages and Compilers for Parallel Computing, 1999.
[30] Mellor-Crummey J, Whalley D and Kennedy K. Improving memory hierarchy performance for irregular applications. In Proceedings of the 13th ACM International Conference on Supercomputing, Rhodes, Greece, June 1999, 425-433.
[31] Mellor-Crummey J, Whalley D and Kennedy K. Improving memory hierarchy performance for irregular applications using data and computation reorderings[J]. International Journal of Parallel Programming, 2001, 29(3): 217-247.
[32] Platzman L K and Bartholdi III J J. Spacefilling curves and the planar travelling salesman problem[ J]. J. of the ACM, 1989, (36): 719-737.
[33] Salmon J and Warren M. Parallel out-of-core methods for n-body simulation. In Proceedings of the 8th SIAM Conference on Parallel Processing for Scientific Computing, 1997.
[34] Zhang Y and Webber R E. Space diffusion: An improved parallel halftoning technique using spacefilling curves. In Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques, 1993, 305-312.
[35] Sierpiński Curve. http://mathworld.wolfram.com/SierpinskiCurve.html.
[36] Salomon David. Data Compression: The Complete Reference, Springer-Verlag, 2000.
[37] Jochen Alber and Rolf Niedermeier. On Multi-Dimensional Hilbert Indexings, Theory of Computing Systems, Springer, 1998, 329-338.
[38] Breinholt G and Schierz C. Algorithm 781: Generating Hilbert's space-filling curve by recursion[J]. ACM Trans. on Mathematical Software, 1998, 24(2): 184-189.
[39] Butz A R. Altrnative algorithm for Hilbert's space-filling curve[J]. IEEE Transactions on Computers, 1971, (20): 424-426.
[40] Goldschlager L M. Short algorithms for space-filling curves[J]. Software—Practice and Experience, 1981, (11): 99-100.
[41] Witten I H and Wyvill B. On the generation and use of space-filling curves[J]. Software—Practice and Experience, 1983, (13): 519-525.
[42] Cole A J. A note on space filling curve[J]. Software—Practice and Experience, 1983, (13): 1181- 1189.
[43] Fisher A J. A new algorithm for generation hilbert curves[J]. Software: Practice and Experience, 1986, (16): 5-12.
[44] Griffiths J G. Table-driven algorithms for generating space-filling curves[J]. Computer-Aided Design, 1985, 17(1): 37-41.
[45] Liu X and Schrack G F. Encoding and decoding the Hilbert order[J]. Software—Practice and Experience, 1996, 26(12): 1335-1346.
[46] Liu X and Schrack G F. An algorithm for encoding and decoding the 3-D Hilbert order[J]. IEEE transactions on image processing, 1997, (6): 1333-1337.
[47] Faloutsos C and Roseman S. Fractals for secondary key retrieval. In Pr oceedings of the 8th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Philadelphia, Pensylvania, USA, 1989, 247-252.
[48] Chen N, Wang N and Shi B. A new algorithm for encoding and decoding the Hilbert order[J]. Software—Practice and Experience, 2007, 37(8): 897-908.
[49] Lawder J K. Calculation of Mappings Between One and n-dimensional Values Using the Hilbert Space-filling Curve. Technical Report, 2000.
[50] Yu Song, Liu Hui, Chen Zhangxin, Hsieh Ben and Shao Lei. GPU-based Parallel Reservoir Simulation for Large-scale Simulation Problems. SPE Europec/EAGE Annual Conference (Copenhagen, Denmark, 2012).
[51] Chen Zhangxin, Liu Hui, Yu Song, Hsieh Ben, Shao Lei. Reservoir Simulation on NVIDIA Tesla GPUs. The Eighth International Conference on Scientific Computing and Applications, University of Nevada, Las Vegas, April, 2012.
[52] Chen Zhangxin, Liu Hui, Yu Song, Hsieh Ben and Shao Lei. GPU-based parallel reservoir simulators. 21st International Conference on Domain Decomposition Methods, 2012, Reene, France.
[53] Kamata S, Eason R O and Bandou Y. A new algorithm for N-dimensional Hilbert scanning[J]. IEEE Trans on Image Processing, 1999, 8(7): 964-973.
[54] Liu H, Wang K, Chen Z and Jordan K E. Efficient Multi-stage Preconditioners for Highly Heterogeneous Reservoir Simulations on Parallel Distributed Systems, SPE-173208-MS, SPE Reservoir Simulation Symposium held in Houston, Texas, USA, 23-25 February 2015.
[55] Li C and Feng Y. Algorithm for analyzing n-dimensional Hilbert curve. vol. 3739, Springer Berlin/Heidelberg, 2005, 657-662.
[56] Chen Z, Liu H, Yu S, Hsieh B and Shao L. GPU-based parallel reservoir simulators, Proc. of 21st International Conference on Domain Decomposition Methods, 2012, France.
[57] Doran Robert W. The Gray Code[J]. Journal of Universal Computer Science, 2007, 13(11): 1573- 1597.
[58] Cui Tao. Efficient parallel adaptive computation of 3D time-harmonic Maxwell's equations using the toolbox PHG, High Performance Computing and Communications, 2008, 876-881.
[59] Chen Zhiming, Chen Junqing, Cui Tao, Zhang Lin-bo. An Adaptive Finite Element Method for the Eddy Current Model with Circuit/Field Couplings[J]. SIAM J. of Scientifc Computing, 2010, 32(2): 1020-1042.
[60] Chen Zhiming, Cui Tao, Zhang Linbo. An adaptive anisotropic perfectly matched layer method for 3-D time harmonic electromagnetic scattering problems[J]. Numerische Mathematik, 2013, 125(4): 639-677.
[1] 赵志宁, 石全, 张军刚. 基于改进离散粒子群优化算法的作战弹药分配研究[J]. 数值计算与计算机应用, 2013, 34(3): 205-211.
[2] 郭稳涛, 何怡刚. 基于混合蚁群算法的DNA编码序列设计方法[J]. 数值计算与计算机应用, 2013, 34(2): 105-116.
[3] 杨小远,赵明,李波. 基于IFS系统的快速分形编码算法研究[J]. 数值计算与计算机应用, 2006, 27(2): 114-122.
[4] 赵明,杨小远,李波. 一种优选匹配的快速分形图像编码算法[J]. 数值计算与计算机应用, 2006, 27(1): 24-30.
[5] 张文,李祥. 基于优化组合的遗传算子的研究与应用[J]. 数值计算与计算机应用, 2005, 26(3): 208-214.
[6] 陈兆斗,申亚男,张丽静,张东霞. Cooley-Tukey FFT在高维的算法[J]. 数值计算与计算机应用, 2004, 26(2): 137-150.
[7] 王何宇. 经典分形集测度上估的计算机搜索Ⅰ──对典型例子Sierpinski垫片编码技术的剖析[J]. 数值计算与计算机应用, 1999, 21(1): 109-116.
Copyright © 2008 数值计算与计算机应用 版权所有
中国科学院数学与系统科学研究院 《数值计算与计算机应用》编辑部
北京2719信箱 (100190) Email: szjs@lsec.cc.ac.cn
Support by Beijing Magtech Co.ltd   E-mail:support@magtech.com.cn
京ICP备05002806号-10