Bin Xiao

Work place: School of Computer Science and Technology, Xidian University, Xi’an, China

E-mail: xiaobinic@gmail.com

Website:

Research Interests: Pattern Recognition, Image Compression, Image Manipulation, Image Processing

Biography

Xiao Bin was born in Chongqing China, 1982. He received his B.S. and M.S. degrees in Electrical Engineering from Shaanxi Normal University, Xi’an, China in 2004 and 2007.
He is currently now pursuing the Ph.D. degree at Xidian University, Xi’An, China. His research interests include image processing, pattern recognition and digital watermarking. He has published more than 10 papers in image processing, pattern recognition.

Author Articles
Speed up linear scan in high-dimensions by sorting one-dimensional projections

By Jiangtao Cui Bin Xiao Gengdai Liu Lian Jiang

DOI: https://doi.org/10.5815/ijisa.2011.04.06, Pub. Date: 8 Jun. 2011

High-dimensional indexing is a pervasive challenge faced in multimedia retrieval. Existing indexing methods applying linear scan strategy, such as VA-file and its variations, are still efficient when the dimensionality is high. In this paper, we propose a new access idea implemented on linear scan based methods to speed up the nearest-neighbor queries. The idea is to map high-dimensional points into two kinds of one-dimensional values using projection and distance computation. The projection values on the line determined by the first Principal Component are sorted and indexed using a B+-tree, and the distances of each point to a reference point are also embedded into leaf node of the B+-tree. When performing nearest neighbor search, the Partial Distortion Searching and triangular inequality are employed to prune search space. In the new search algorithm, only a small portion of data points need to be linearly accessed by computing the bounded distance on the one-dimensional line, which can reduce the I/O and processor time dramatically. Experiment results on large image databases show that the new access method provides a faster search speed than existing high-dimensional index methods.

[...] Read more.
Other Articles