Quantile-based KNN over multi-valued objects

Zhang, W; Lin, X; Cheema, MA; Zhang, Y; Wang, W

Quantile-based KNN over multi-valued objects

Zhang, W Lin, X Cheema, MA Zhang, Y

Wang, W

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings - International Conference on Data Engineering, 2010, pp. 16 - 27
Issue Date:: 2010-06-01

Closed Access

	Filename	Description	Size
	2013005466OK.pdf		268.64 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Zhang, W	en_US
dc.contributor.author	Lin, X	en_US
dc.contributor.author	Cheema, MA	en_US
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638	en_US
dc.contributor.author	Wang, W	en_US
dc.date.issued	2010-06-01	en_US
dc.identifier.citation	Proceedings - International Conference on Data Engineering, 2010, pp. 16 - 27	en_US
dc.identifier.isbn	9781424454440	en_US
dc.identifier.issn	1084-4627	en_US
dc.identifier.uri	http://hdl.handle.net/10453/28961
dc.description.abstract	K Nearest Neighbor search has many applications including data mining, multi-media, image processing, and monitoring moving objects. In this paper, we study the problem of KNN over multi-valued objects. We aim to provide effective and efficient techniques to identify KNN sensitive to relative distributions of objects. We propose to use quantiles to summarize relative-distribution- sensitive K nearest neighbors. Given a query Q and a quantile φ ε (0, 1], we firstly study the problem of efficiently computing K nearest objects based on a φ-quantile distance (e.g. median distance) from each object to Q. The second problem is to retrieve the K nearest objects to Q based on overall distances in the "best population" (with a given size specified by φ-quantile) for each object. While the first problem can be solved in polynomial time, we show that the 2nd problem is NP-hard. A set of efficient, novel algorithms have been proposed to give an exact solution for the first problem and an approximate solution for the second problem with the approximation ratio 2. Extensive experiment demonstrates that our techniques are very efficient and effective. © 2010 IEEE.	en_US
dc.relation.ispartof	Proceedings - International Conference on Data Engineering	en_US
dc.relation.isbasedon	10.1109/ICDE.2010.5447877	en_US
dc.title	Quantile-based KNN over multi-valued objects	en_US
dc.type	Conference Proceeding
utslib.for	0806 Information Systems	en_US
dc.location.activity	Long Beach, USA	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US

Abstract:

K Nearest Neighbor search has many applications including data mining, multi-media, image processing, and monitoring moving objects. In this paper, we study the problem of KNN over multi-valued objects. We aim to provide effective and efficient techniques to identify KNN sensitive to relative distributions of objects. We propose to use quantiles to summarize relative-distribution- sensitive K nearest neighbors. Given a query Q and a quantile φ ε (0, 1], we firstly study the problem of efficiently computing K nearest objects based on a φ-quantile distance (e.g. median distance) from each object to Q. The second problem is to retrieve the K nearest objects to Q based on overall distances in the "best population" (with a given size specified by φ-quantile) for each object. While the first problem can be solved in polynomial time, we show that the 2nd problem is NP-hard. A set of efficient, novel algorithms have been proposed to give an exact solution for the first problem and an approximate solution for the second problem with the approximation ratio 2. Extensive experiment demonstrates that our techniques are very efficient and effective. © 2010 IEEE.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/28961