K-nearest neighbor search for fuzzy objects

Zheng, Kai, Fung, Pui Cheong and Zhou, Xiaofang (2010). K-nearest neighbor search for fuzzy objects. In: Proceedings of the 2010 International Conference on Management of Data, SIGMOD '10. 2010 ACM SIGMOD/PODS Conference, Indianapolis, IN, United States, (699-710). 6-11 June 2010. doi:10.1145/1807167.1807243

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
UQ239110_fulltext.pdf ERA evidence - not publicly available application/pdf 484.42KB 69

Author Zheng, Kai
Fung, Pui Cheong
Zhou, Xiaofang
Title of paper K-nearest neighbor search for fuzzy objects
Conference name 2010 ACM SIGMOD/PODS Conference
Conference location Indianapolis, IN, United States
Conference dates 6-11 June 2010
Proceedings title Proceedings of the 2010 International Conference on Management of Data, SIGMOD '10   Check publisher's open access policy
Journal name Association for Computing Machinery. Special Interest Group on Management of Data. International Conference Proceedings   Check publisher's open access policy
Place of Publication New York, United States
Publisher Association for Computing Machinery (ACM)
Publication Year 2010
Sub-type Fully published paper
DOI 10.1145/1807167.1807243
Open Access Status File (Author Post-print)
ISBN 9781450300322
ISSN 0730-8078
Start page 699
End page 710
Total pages 12
Language eng
Formatted Abstract/Summary
The K-Nearest Neighbor search (kNN) problem has been investigated extensively in the past due to its broad range of applications. In this paper we study this problem in the context of fuzzy objects that have indeterministic boundaries. Fuzzy objects play an important role in many areas, such as biomedical image databases and GIS. Existing research on fuzzy objects mainly focuses on modelling basic fuzzy object types and operations, leaving the processing of more advanced queries such as kNN query untouched. In this paper, we propose two new kinds of kNN queries for fuzzy objects, Ad-hoc kNN query (AKNN) and Range kNN query (RKNN), to find the k nearest objects qualifying at a probability threshold or within a probability range. For efficient AKNN query processing, we optimize the basic best-first search algorithm by deriving more accurate approximations for the distance function between fuzzy objects and the query object. To improve the performance of RKNN search, effective pruning rules are developed to significantly reduce the search space and further speed up the candidate refinement process. The efficiency of our proposed algorithms as well as the optimization techniques are verified with an extensive set of experiments using both synthetic and real datasets.
Keyword Nearest neighbor query
Fuzzy database
Probabilistic database
Q-Index Code E1
Q-Index Status Provisional Code
Institutional Status UQ

Version Filter Type
Citation counts: Scopus Citation Count Cited 9 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Fri, 25 Mar 2011, 18:19:17 EST by Mr Kevin Zheng on behalf of School of Information Technol and Elec Engineering