NDLI: Effective optimizations of cluster-based nearest neighbor search in high-dimensional space

Content Provider	Springer Nature Link
Author	Feng, Xiaokang Cui, Jiangtao Liu, Yingfan Li, Hui
Copyright Year	2014
Abstract	Nearest neighbor (NN) search in high-dimensional space plays a fundamental role in large-scale image retrieval. It seeks efficient indexing and search techniques, both of which are simultaneously essential for similarity search and semantic analysis. However, in recent years, there has been a rare breakthrough. Achievement of current techniques for NN search is far from satisfactory, especially for exact NN search. A recently proposed method, HB, addresses the exact NN search efficiently in high-dimensional space. It benefits from cluster-based techniques which can generate more compact representation of the data set than other techniques by exploiting interdimensional correlations. However, HB suffers from huge cost for lower bound computations and provides no further pruning scheme for points in candidate clusters. In this paper, we extend the HB method to address exact NN search in correlated, high-dimensional vector data sets extracted from large-scale image database by introducing two new pruning/selection techniques and we call it HB+. The first approach aims at selecting more quickly the subset of hyperplanes/clusters that must be considered. The second technique prunes irrelevant points in the selected subset of clusters. Performed experiments show the improvement of HB+ with respect to HB in terms of efficiency (I/O cost and CPU response time) and also demonstrate the superiority over other exact NN indexes.
Starting Page	139
Ending Page	153
Page Count	15
File Format	PDF
ISSN	09424962
Journal	Multimedia Systems
Volume Number	23
Issue Number	1
e-ISSN	14321882
Language	English
Publisher	Springer Berlin Heidelberg
Publisher Date	2014-12-24
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Image retrieval Nearest neighbor search High-dimensional indexing Hyperplane bounds Multimedia Information Systems Computer Communication Networks Operating Systems Data Storage Representation Data Encryption Computer Graphics
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Information Systems Media Technology Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Optimized residual vector quantization for efficient approximate nearest neighbor search

Systems and architectures for multimedia information retrieval

Learning high-dimensional multimedia data

Voronoi-based reverse nearest neighbor query processing on spatial networks

FAST: Toward more effective and efficient image retrieval

RELIEF-MM: effective modality weighting for multimedia information retrieval

Efficient kNN search in polyphonic music databases using a lower bounding mechanism

Fast retrieval of high-dimensional feature vectors in P2P networks using compact peer data summaries

Learning in high-dimensional multimedia data: the state of the art

Effective optimizations of cluster-based nearest neighbor search in high-dimensional space

Similar Documents

Optimized residual vector quantization for efficient approximate nearest neighbor search

Systems and architectures for multimedia information retrieval

Learning high-dimensional multimedia data

Voronoi-based reverse nearest neighbor query processing on spatial networks

FAST: Toward more effective and efficient image retrieval

RELIEF-MM: effective modality weighting for multimedia information retrieval

Efficient kNN search in polyphonic music databases using a lower bounding mechanism

Fast retrieval of high-dimensional feature vectors in P2P networks using compact peer data summaries

Learning in high-dimensional multimedia data: the state of the art

Effective optimizations of cluster-based nearest neighbor search in high-dimensional space