Jiangtao Cui

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

E-mail: cuijt@xidian.edu.cn

Website:

Research Interests: Computational Science and Engineering, Image Processing, Data Structures and Algorithms

Biography

Jiangtao Cui was born in 1975, TsingTao, China. He received PhD in Computer Science from Xidian University in 2005. He received his Bachelor degree in Computer Software and Master’s degree in Computer Science from Xidian University in 1998 and 2001, respectively. His Current research interests include image/video processing, data and knowledge engineering, and high-dimensional indexing. He is currently a associate professor in School of Computer Science of Xidian University, China. He has published more than 30 papers in image retrieval and high-dimensional indexing. Dr. Jiangtao Cui was a steering chair of DSDE 2011.

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