%0 Journal Article
%T LBD:Exploring Local Bit-code Difference for KNN Search in High-dimensional Spaces<br>LBD：基于局部位码比较的高维空间KNN搜索算法
%A LIANG Jun-Jie
%A FENG Yu-Cai
%A <br>梁俊杰
%A 冯玉才
%J 计算机科学
%D 2007
%I 
%X Recent advances in research fields like multimedia and bioinformatics have brought about a new generation of high-dimensional databases. To support efficient querying and retrieval on such databases, we propose a methodology exploring Local Bit-code Difference (LBD)which can support k-nearest neighbors (KNN)queries on high-dimensional databases and yet co-exist with ubiquitous indices, such as B -trees. On clustering the data space into a number of partitions, LBD extracts a distance and a simple bitmap representation called Bit Code (BC)for each point in the database with respect to the corresponding reference point. Pruning during KNN search is performed by dynamically selecting only a subset of the bits from the BC based on which subsequent comparisons are performed. In doing so, expensive operations involved in computing L-norm distance functions between high-dimensional data can be avoided. Extensive experiments are conducted to show that our methodology offers significant performance advantages over other existing indexing methods on both real life and synthetic high-dimensional spaces.
%K High-dimensional index
%K KNN search
%K Bit code
%K Approximate vector<br>高维索引
%K KNN查询
%K 位码
%K 近似向量
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=28E92A3AF17715B3D25138E8CEFAEB2F&yid=A732AF04DDA03BB3&vid=339D79302DF62549&iid=B31275AF3241DB2D&sid=769BD58726D66E7D&eid=856C2E13D1000DB7&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=12