Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/14423
Title: Efficient processing of KNN and skyjoin queries
Authors: HU JING
Keywords: high-dimensional indexing, k nearest neighbor, skyline
Issue Date: 20-Jan-2005
Source: 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.
URI: http://scholarbank.nus.edu.sg/handle/10635/14423
Appears in Collections:Master's Theses (Open)

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

OPEN

NoneView/Download

Page view(s)

143
checked on Dec 18, 2017

Download(s)

153
checked on Dec 18, 2017

Google ScholarTM

Check


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