Gengdai Liu

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



Research Interests: Computer systems and computational processes, Computer Animation, Mixed Reality, Virtual Reality


Gengdai Liu was born in 1979, Xi’an, China. He received PhD in Computer Science at State Key Lab of CAD&CG from Zhejiang University in 2009. He received his Bachelor degree in Information Engineering and Master’s degree in Systems Engineering from Xi’an Jiaotong University in 2002 and 2005, respectively. His current research interests include virtual reality, character animation, and 3D user interface. He is currently a lecturer in school of Computer Science of Xidian University, China. He has published more than 10 papers in computer animation, virtual reality and HCI. He is also coauthor of several books. Dr. Gengdai Liu was a member of program committee of CASA2011 and a chair of ChinaVR2010.

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

By Jiangtao Cui Bin Xiao Gengdai Liu Lian Jiang

DOI:, 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