Title page for etd-0711112-191009


[Back to Results | New Search]

URN etd-0711112-191009
Author Fei-Chung Feng
Author's Email Address No Public.
Statistics This thesis had been viewed 5353 times. Download 536 times.
Department Computer Science and Engineering
Year 2011
Semester 2
Degree Master
Type of Document
Language English
Title A Hilbert Curve-Based Algorithm for Order-Sensitive Moving KNN Queries
Date of Defense 2012-06-29
Page Count 92
Keyword
  • Spatial database
  • Real-Time Systems
  • Hilbert curve
  • K nearest neighbor
  • Mobile service
  • Abstract   Due to wireless communication technologies, positioning technologies, and mobile computing develop quickly, mobile services are becoming practical and important on big spatiotemporal databases management. Mobile service users move only inside a spatial space, e:g: a country. They often issue the K Nearest Neighbor (kNN) query to obtain data objects reachable through the spatial database. The challenge problem of mobile services is how to efficiently answer the data objects which users interest to the corresponding mobile users. One type of kNN query problems is the order-sensitive moving kNN (order-sensitive MkNN) query problem. In the order-sensitive MkNN query problem, the query point is dynamic and unpredictable, the kNN answers should be responded in real time and sorted by the distance in the ascending order. Therefore, how to respond the kNN answers effectively, incrementally and correctly is an important issue. Nutanong et al: have proposed the V*-kNN algorithm to process the order-sensitive MkNN query. The V*-kNN algorithm uses their the V*-diagram algorithm to generate the safe region. It also uses the Incremental Rank Updates algorithm (IRU) to handle the events while the query point passing the bisectors or the boundary of the safe region. However, the V*-kNN algorithm uses the BF-kNN algorithm to retrieve NNs, which is non-incremental. This makes the search time increase while the density of the object increases. Moreover, they do not consider the situation that there are multiple objects at the same order, and the situation that there are multiple events happen in a single step. These situations may cause that the kNN answers are incorrect. Therefore, in this thesis, we propose the Hilbert curve-based kNN algorithm (HC-kNN) algorithm to process the ordersensitive MkNN query. The HC-kNN algorithm can handle the situation that there are multiple events happen in a single step. We also propose new data structure of the kNN answers. Next, we propose the Intersection of Perpendicular Bisectors algorithm (IPB) in order to handle order update events of the kNN answers. The IPB algorithm handles the situation which there are multiple objects at the same order. Finally, based on the Hilbert curve index, we propose the ONHC-kNN algorithm to get NNs incrementally and to generate the safe region. The safe region will not be affected while the density of the object increases. The safe region of our algorithm is larger than that of the V*-kNN algorithm. From our simulation result, we show that the HC-kNN algorithm provides better performance than the V*-kNN algorithm.
    Advisory Committee
  • Gen-Huey Chen - chair
  • Chien-I Lee - co-chair
  • Tei-Wei Kuo - co-chair
  • Ye-In Chang - advisor
  • Files
  • etd-0711112-191009.pdf
  • Indicate in-campus at 1 year and off-campus access at 1 year.
    Date of Submission 2012-07-11

    [Back to Results | New Search]


    Browse | Search All Available ETDs

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