Lian Jiang

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

E-mail: jianglianzm@gmail.com

Website:

Research Interests: Natural Language Processing, Image Compression, Image Manipulation, Image Processing

Biography

Lian Jiang was born in 1989, Hu’bei, China. She received her B.S. degree in Computer Science from Xidian University in 2010. She is currently pursuing the M.S. degree in Computer Science at Xidian University. Her research interests include image processing, manifold learning.

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