High Dimensional Spatial Indexing using Space-Filling Curves

Ankush Chauhan, William Johnson, Anjuli Patel

• Publisher: GRIN Verlag
• Edition: 1
• Year: 2016
• Topic: Mathematics
• Subtopic: Mathematics General
• eBook ISBN:
  9783668260115
• Index: Mathematics

Representation of two dimensional objects into one dimensional space is simple and efficient when using a two coordinate system imposed upon a grid. However, when the two dimensions are expanded far beyond visual and sometimes mental understanding, techniques are used to quantify and simplify the representation of such objects. These techniques center around spatial interpretations by means of a space–filling curve. Since the late 1800's, mathematicians and computer scientists have succeeded with algorithms that express high dimensional geometries. However, very few implementations of the algorithms beyond three dimensions for computing these geometries exist. We propose using the basic spatial computations developed by pioneers in the field like G. Peano, D. Hilbert, E. H. Moore, and others in a working model. The algorithms in this paper are fully implemented in high-level programming languages utilizing a relation database management system. We show the execution speeds of the algorithms using a space–filling curve index for searching compared to brute force searching. Finally, we contrast three space–filling curve algorithms: Moore, Hilbert, and Morton, in execution time of searching for high dimensional data in point queries and range queries.

Table of contents

• INTRODUCTION and BACKGROUND
• IMPLEMENTATION
• RESULTS
• FUTURE WORK
• Appendix
• References