Title page for etd-0523115-195758


[Back to Results | New Search]

URN etd-0523115-195758
Author Kai-ning Yang
Author's Email Address No Public.
Statistics This thesis had been viewed 5377 times. Download 0 times.
Department Computer Science and Engineering
Year 2014
Semester 2
Degree Master
Type of Document
Language English
Title A KSNA-Tree Algorithm for the Top-k Exact Keyword Search in Spatial Databases
Date of Defense 2015-06-05
Page Count 80
Keyword
  • Top-k
  • Spatial Index Structure
  • Spatial Database
  • Keyword Matching
  • Inverted Index
  • Abstract In recent years, the geographic information system (GIS) develops quickly and plays a significant role in many applications and websites. Many websites and applications allow users to find objects which match with all of the query keywords and are close to a specified location. For instance, a user wants to find the 'Snoopy hotel' near Kaohsiung. The 'Snoopy hotel' has two keywords in the keyword set and Kaohsiung is the specified location. In this case, we have to use the algorithm of finding top-k spatial keyword query. Tao et al: propose a data access structure called the SI-index which integrates the inverted index with R-tree. They use data compression approaches, gap-keeping and Z-value, for reducing the size of the SI-index. Besides, they provide two algorithms for solving the top-k spatial keyword query, including an R-tree browsing algorithm SI-b and an index merging algorithm SI-m. However, in their data structure, a large number of R-trees are built for storing data of objects. For n keywords, n R-trees must be constructed. It takes long time for dealing with data of objects and some extra time for data decompression. When data objects are updated/deleted/queried, their algorithm must traverse all the R-trees of the query keywords. They have to traverse k R-trees in an interleaved fashion for updating, deleting and querying data of objects, where k is the size of query keyword set and 1≤k≤n. Therefore, in this thesis, we propose a KSNA-tree algorithm. The KSNA-tree integrates a spatial index NA-tree with inverted index. The NA-tree is a tree structure based on locations of data objects and organized by the spatial numbers. The contributions of our approach are as follows. First, our approach only construct one KSNA-tree, instead of building n R-trees for n keywords in the database. Second, we organize the data of objects according to their spatial number. This will avoid random access in the query processing by directly accessing the spatial number of a node. Third, we enhance each node in the KSNA-tree with the inverted index. We can prune a node and all of its child nodes immediately once we know that one of the query keywords is definitely not in the node. From our simulation results, we show that our proposed approach is more efficient than the SI-index.
    (Keywords: Inverted Index, Keyword Matching, Spatial Database, Spatial Index
    Structure, Top-k)
    Advisory Committee
  • Gen-huey Chen - chair
  • Chien-i Lee - co-chair
  • Tei-Wei Kuo - co-chair
  • Ye-In Chang - advisor
  • Files
  • etd-0523115-195758.pdf
  • Indicate in-campus at 5 year and off-campus access at 5 year.
    Date of Submission 2015-06-23

    [Back to Results | New Search]


    Browse | Search All Available ETDs

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