Near-optimal partial linear scan for nearest neighbor search in high-dimensional space

Cui, Jiangtao, Huang, Zi, Wang, Bo and Liu, Yingfan (2013). Near-optimal partial linear scan for nearest neighbor search in high-dimensional space. In: Weiyi Meng, Ling Feng, Stephane Bressan, Werner Winiwarter and Wei Song, Database Systems for Advanced Applications - 18th International Conference, DASFAA 2013, Proceedings. 18th International Conference on Database Systems for Advanced Applications, DASFAA 2013, Wuhan, (101-115). April 22, 2013-April 25, 2013. doi:10.1007/978-3-642-37487-6_10

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Cui, Jiangtao
Huang, Zi
Wang, Bo
Liu, Yingfan
Title of paper Near-optimal partial linear scan for nearest neighbor search in high-dimensional space
Conference name 18th International Conference on Database Systems for Advanced Applications, DASFAA 2013
Conference location Wuhan
Conference dates April 22, 2013-April 25, 2013
Proceedings title Database Systems for Advanced Applications - 18th International Conference, DASFAA 2013, Proceedings   Check publisher's open access policy
Journal name Lecture Notes in Computer Science   Check publisher's open access policy
Place of Publication Heidelberg, Germany
Publisher Springer
Publication Year 2013
Year available 2013
Sub-type Fully published paper
DOI 10.1007/978-3-642-37487-6_10
ISBN 9783642374869
9783642402708
9783642402692
ISSN 0302-9743
1611-3349
Editor Weiyi Meng
Ling Feng
Stephane Bressan
Werner Winiwarter
Wei Song
Volume 7825
Issue PART 1
Start page 101
End page 115
Total pages 15
Collection year 2014
Language eng
Abstract/Summary One-dimensional mapping has been playing an important role for nearest neighbor search in high-dimensional space. Two typical kinds of one-dimensional mapping method, direct projection and distance computation regarding to reference points, are discussed in this paper. An optimal combination of one-dimensional mappings is achieved for the best search performance. Furthermore, we propose a near-optimal partial linear scan algorithm by considering several one-dimensional mapping values. During the linear scan, the partial distance to the query point computed in the 1D space is used as the lower bound to filter the unqualified data points. A new indexing structure based on clustering with Gaussian Mixture is also designed to facilitate the partial linear scan, which can reduce both the I/O cost and distance computations dramatically. Comprehensive experiments are conducted on several real-life datasets with different dimensions. The experimental results show that the proposed indexing structure outperforms the existing well-known high-dimensional indexing methods.
Subjects 1700 Computer Science
2614 Theoretical Computer Science
Keyword Indexing methods
Nearest neighbor search
One dimensional mapping
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

 
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Tue, 18 Feb 2014, 11:37:37 EST by System User on behalf of School of Information Technol and Elec Engineering