Efficient Metric All-k-Nearest-Neighbor Search on Datasets Without Any Index

An all-k-nearest-neighbor （AkNN） query finds k nearest neighbors for each query object. This problem arises naturally in many areas, such as GIS （geographic information system）, multimedia retrieval, and recommender systems. To support various data types and flexible distance metrics involved in rea...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer science and technology 2016-11, Vol.31 (6), p.1194-1211
Main Authors: Zhang, Hai-Da, Xing, Zhi-Hao, Chen, Lu, Gao, Yun-Jun
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Artificial Intelligence
Clustering
Computer Science
Data mining
Data Structures and Information Theory
Datasets
Euclidean space
Geographic information systems
Information retrieval
Information Systems Applications (incl.Internet)
Metric space
Multimedia
Multimedia computer applications
Pruning
Queries
Query processing
Recommender systems
Satellite navigation systems
Searching
Software Engineering
Studies
Synthetic data
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An all-k-nearest-neighbor （AkNN） query finds k nearest neighbors for each query object. This problem arises naturally in many areas, such as GIS （geographic information system）, multimedia retrieval, and recommender systems. To support various data types and flexible distance metrics involved in real applications, we study AkNN retrieval in metric spaces, namely, metric AkNN （MAkNN） search. Consider that the underlying indexes on the query set and the object set may not exist, which is natural in many scenarios. For example, the query set and the object set could be the results of other queries, and thus, the underlying indexes cannot be built in advance. To support MAkNN search on datasets without any underlying index, we propose an efficient disk-based algorithm, termed as Partition-Based MAkNN Algorithm （PMA）, which follows a partition-search framework and employs a series of pruning rules for accelerating the search. In addition, we extend our techniques to tackle an interesting variant of MAkNN queries, i.e., metric self-AkNN （MSAkNN） search, where the query set is identical to the object set. Extensive experiments using both real and synthetic datasets demonstrate the effectiveness of our pruning rules and the efficiency of the proposed algorithms, compared with state-of-the-art MAkNN and MSAkNN algorithms.
ISSN:1000-9000
1860-4749
DOI:10.1007/s11390-016-1692-9