LSH-Based Algorithm for k Nearest Neighbor Search on Big Data

WANG Zhong-wei; CHEN Ye-fang; QIAN Jiang-bo; CHEN Hua-hui

doi:10.3969/j.issn.0372-2112.2016.04.022

您当前的位置：

首页 >

文章列表页 >

LSH-Based Algorithm for k Nearest Neighbor Search on Big Data

更新时间：2025-07-16

- LSH-Based Algorithm for k Nearest Neighbor Search on Big Data
- Acta Electronica Sinica Vol. 44, Issue 4, Pages: 906-912(2016)
- 作者机构：
  
  宁波大学信息科学与工程学院,浙江,宁波,315211
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2016.04.022
  CLC： TP311.13
- Published Online：25 April 2016，
  
  Published：2016
- 稿件说明：
移动端阅览
WANG Zhong-wei, CHEN Ye-fang, QIAN Jiang-bo, et al. LSH-Based Algorithm for k Nearest Neighbor Search on Big Data[J]. Acta Electronica Sinica, 2016, 44(4): 906-912.
DOI：

WANG Zhong-wei, CHEN Ye-fang, QIAN Jiang-bo, et al. LSH-Based Algorithm for k Nearest Neighbor Search on Big Data[J]. Acta Electronica Sinica, 2016, 44(4): 906-912. DOI： 10.3969/j.issn.0372-2112.2016.04.022.

摘要

局部敏感哈希(LSH)及其变体是解决高维数据k近邻(kNN)搜索的有效算法.但是

随着数据规模的日趋庞大

传统的集中式LSH算法结构已经不能够满足大数据时代的需求.本文分析传统LSH方案的不足之处

拓展AND-OR结构

提出通过索引而不比较原始数据直接实现高维大数据k近邻搜索算法C2SLSH.理论分析和实验证明

C2SLSH在分布式平台下具有稳定的可扩展性

在保证同等精确率的情况下

处理速度大约是现有方法的3倍.

Abstract

The locality sensitive hashing (LSH) and its variants are efficient algorithms to solve the k nearest neighbor (kNN) search problems on high-dimensional data.However

with the increase of large data size

the traditional centralized LSH algorithms cannot meet the challenge of the big data era.Based on a new AND-OR construction

this paper proposes an algorithm (called C2SLSH) for the k nearest neighbor search on big data.Different to the traditional algorithms

the C2SLSH can directly get the results from an index without having to compare the original data.The theoretical analysis and experimental results show that the algorithm has stable scalability on a distributed platform.Furthermore

it is faster than the conventional methods for about three times with the same accuracy rate.

关键词

Keywords

references

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Survey of MapReduce Parallel Programming Model

Augmented Dynamic Skyline Query Processing Method Based on MapReduce

Top-n Recommendation Algorithms for Cloud Data

Automatic Service Composition in Parallel with MapReduce

Optimized High-Dimensional Index and KNN Query in MapReduce

Related Author

HUANG Yi-shuang

YAN Lin

WANG Dan

CUI Jian

LI Jian-jiang

SONG Bao-yan

WANG Jun-lu

YIN Xian-kun

Related Institution

Research Institute of Exploration Southern Division CompanySINOPECChengduSichuan 610041China

Department of Computer Science and TechnologySchool of Computer and Communication EngineeringUniversity of Science and Technology BeijingBeijing 100083China

Research Institute of Exploration Southern Division Company,SINOPEC

Department of Computer Science and Technology,School of Computer and Communication Engineering,University of Science and Technology Beijing

School of Information, Liaoning University

⁰