Please use this identifier to cite or link to this item:
Title: Efficient processing of KNN and skyjoin queries
Authors: HU JING
Keywords: high-dimensional indexing, k nearest neighbor, skyline
Issue Date: 20-Jan-2005
Citation: HU JING (2005-01-20). Efficient processing of KNN and skyjoin queries. ScholarBank@NUS Repository.
Abstract: High-dimensional nearest neighbor search is a very important operation in many emerging database applications. We proposed two new indexing techniques, the Diagonal Ordering method and the SA-tree. Diagonal Ordering is based on data clustering and sorting each cluster along the diagonal direction. The KNN search is then performed as a sequence of one-dimensional range searches. The SA-tree utilizes the characteristics of each cluster to adaptively compress feature vectors into bit-strings. We also developed an efficient KNN search algorithm using MinMax Pruning or Partial MinDist Pruning method. Besides high-dimensional KNN query, we also extend the skyline operation to the Skyjoin query, which finds the skyline of each data point in the database. We proposed an efficient algorithm to speed up the processing of the Skyjoin query by ordering feature vectors lexicographically and computing the grid skyline first. We conducted extensive experiments to evaluate the effectiveness of the proposed techniques.
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
thesis.pdf436.52 kBAdobe PDF



Page view(s)

checked on Apr 20, 2019


checked on Apr 20, 2019

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.