Title page for etd-0618112-141752


[Back to Results | New Search]

URN etd-0618112-141752
Author Chen-Chang Wu
Author's Email Address wucc5501@gmail.com
Statistics This thesis had been viewed 5350 times. Download 1082 times.
Department Computer Science and Engineering
Year 2011
Semester 2
Degree Ph.D.
Type of Document
Language English
Title Efficient Access Methods on the Hilbert Curve
Date of Defense 2012-05-18
Page Count 110
Keyword
  • Image Processing
  • Hilbert Curve
  • Space Filling Curve
  • Window Query
  • Image Compression
  • Abstract The design of multi-dimensional access methods is difficult as compared to those of one-dimensional case because of no total ordering that preserves spatial locality. One way is to look for the total order that preserves spatial proximity at least to some extent. A space-filling curve is a continuous path which passes through every point in a space once so giving a one-to-one correspondence between the coordinates of the points and the 1D-sequence numbers of points on the curve. The Hilbert curve is a famous space filling curve, since it has been shown to have strong locality preserving properties; that is, it is the best space-filling curve in minimizing the number of clusters. Hence, it has been extensively used to maintain spatial locality of multidimensional data in a wide variety of applications. A window query is an important query operation in spatial (image) databases. Given a Hilbert curve, a window query reports its corresponding orders without the need to decode all the points inside this window into the corresponding Hilbert orders. Chung et al. have proposed an algorithm for decomposing a window into the corresponding Hilbert orders. However, the Hilbert curve requires that the region is of size 2^k x 2^k, where k∈N. The intuitive method such as Chung et al.’s algorithm is to directly use Hilbert curves in the decomposed areas and then connect them. They must generate a sequence of the scanned quadrants additionally before encoding and decoding the Hilbert order of one pixel and scan this sequence one time while encoding and decoding one pixel. In this dissertation, on the design of methods for window queries on a Hilbert curve, we propose an efficient algorithm, named as Quad-Splitting, for decomposing a window into the corresponding Hilbert orders on a Hilbert curve without individual sorting and merging steps. The proposed algorithm does not perform individual sorting and merging steps which are needed in Chung et al.’s algorithm. From our experimental results, we show that the Quad-Splitting algorithm outperforms Chung et al.’s algorithm. On the design of the methods for generating the Hilbert curve of an arbitrary-sized image, we propose approximately even partition approach to generate a pseudo Hilbert curve of an arbitrary-sized image. From our experimental results, we show that our proposed pseudo Hilbert curve preserves the similar strong locality property to the Hilbert curve. On the design of the methods for coding Hilbert curve of an arbitrary-sized image, we propose encoding and decoding algorithms. From our experimental results, we show that our encoding and decoding algorithms outperform the Chung et al.’s algorithms.
    Advisory Committee
  • Suh-Yin Lee - chair
  • Vincent Shin-Mu Tseng - co-chair
  • Chiang Lee - co-chair
  • Chang-Biau Yang - co-chair
  • San-Yih Hwang - co-chair
  • Ye-In Chang - advisor
  • Files
  • etd-0618112-141752.pdf
  • Indicate in-campus at 1 year and off-campus access at 1 year.
    Date of Submission 2012-06-18

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys