NDLI: Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances

Please wait, while we are loading the content...

Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances

Content Provider	Springer Nature Link
Author	Fu, Ada Wai chee Chan, Polly Mei shuen Cheung, Yin Ling Moon, Yiu Sang
Copyright Year	2000
Abstract	Abstract. For some multimedia applications, it has been found that domain objects cannot be represented as feature vectors in a multidimensional space. Instead, pair-wise distances between data objects are the only input. To support content-based retrieval, one approach maps each object to a k-dimensional (k-d) point and tries to preserve the distances among the points. Then, existing spatial access index methods such as the R-trees and KD-trees can support fast searching on the resulting k-d points. However, information loss is inevitable with such an approach since the distances between data objects can only be preserved to a certain extent. Here we investigate the use of a distance-based indexing method. In particular, we apply the vantage point tree (vp-tree) method. There are two important problems for the vp-tree method that warrant further investigation, the n-nearest neighbors search and the updating mechanisms. We study an n-nearest neighbors search algorithm for the vp-tree, which is shown by experiments to scale up well with the size of the dataset and the desired number of nearest neighbors, n. Experiments also show that the searching in the vp-tree is more efficient than that for the $R^*$ -tree and the M-tree. Next, we propose solutions for the update problem for the vp-tree, and show by experiments that the algorithms are efficient and effective. Finally, we investigate the problem of selecting vantage-point, propose a few alternative methods, and study their impact on the number of distance computation.
Starting Page	154
Ending Page	173
Page Count	20
File Format	PDF
ISSN	10668888
Journal	The VLDB Journal
Volume Number	9
Issue Number	2
e-ISSN	0949877X
Language	English
Publisher	Springer-Verlag
Publisher Date	2000-07-01
Publisher Place	Berlin Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Information Systems Hardware and Architecture

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

A new approach for maximizing bichromatic reverse nearest neighbor search

Hubness-aware shared neighbor distances for high-dimensional $$k$$ -nearest neighbor classification

Maximizing bichromatic reverse nearest neighbor for L p -norm in two- and three-dimensional spaces

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

Grid-partition index: a hybrid method for nearest-neighbor queries in wireless location-based services

Efficient k-nearest neighbor search on moving object trajectories

Multidimensional reverse kNN search

Multiple k nearest neighbor search

An efficient subspace sampling framework for high-dimensional data reduction, selectivity estimation, and nearest-neighbor search

Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances

Similar Documents

A new approach for maximizing bichromatic reverse nearest neighbor search

Hubness-aware shared neighbor distances for high-dimensional $$k$$ -nearest neighbor classification

Maximizing bichromatic reverse nearest neighbor for L p -norm in two- and three-dimensional spaces

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

Grid-partition index: a hybrid method for nearest-neighbor queries in wireless location-based services

Efficient k-nearest neighbor search on moving object trajectories

Multidimensional reverse kNN search

Multiple k nearest neighbor search

An efficient subspace sampling framework for high-dimensional data reduction, selectivity estimation, and nearest-neighbor search

Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances