Letter to the Editor. Algorithms for the Hilbert order

✍ Scribed by JP Linderman

• Book ID: 101239681
• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 33 KB
• Volume: 28
• Category: Article
• ISSN: 0038-0644
• DOI: 10.1002/(sici)1097-024x(199801)28:1<121::aid-spe144>3.0.co;2-s

✦ Synopsis

Algorithms for the Hilbert Order

In the introduction to their description of algorithms for encoding and decoding the Hilbert order, 1 Liu and Schrack note 'algorithms that do not depend on look-up tables are proposed. They are stated in terms of an explicit formulation, and, in addition, according to experimental evidence, they are faster than Fisher's.' 2 In an environment where memory is precious, perhaps in an on-chip implementation of the algorithm, the elimination of tables can be important. But in environments where memory is not scarce, including modern workstations and mainframes, tables can be used to further improve the efficiency of the algorithms.

We implemented encoding and decoding algorithms based on those in Faloutsos and Roseman, 3 but with heavy use of tables, in effect, to process data byte at a time rather than bit at a time. As with the Liu/Schrack 'orientation' or the Fisher ctab table, we keep track of the four possible 'stages' determined by the high-order bits of the coordinates or Hilbert order already processed.