Finding Aggregate Nearest Neighbor Efficiently without Indexing

Yanmin Luo; Kazutaka Furuse; Hanxiong Chen; Nobuo Ohbo

2nd International ICST Conference on Scalable Information Systems

Research Article

Finding Aggregate Nearest Neighbor Efficiently without Indexing

Download551 downloads

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.4108/infoscale.2007.900,
    author={Yanmin Luo and Kazutaka Furuse and Hanxiong Chen and Nobuo Ohbo},
    title={Finding Aggregate Nearest Neighbor Efficiently without Indexing},
    proceedings={2nd International ICST Conference on Scalable Information Systems},
    proceedings_a={INFOSCALE},
    year={2010},
    month={5},
    keywords={Spatial database Aggregate Nearest Neighbor Search Region.},
    doi={10.4108/infoscale.2007.900}
}

Yanmin Luo
Kazutaka Furuse
Hanxiong Chen
Nobuo Ohbo
Year: 2010
Finding Aggregate Nearest Neighbor Efficiently without Indexing
INFOSCALE
ICST
DOI: 10.4108/infoscale.2007.900

Yanmin Luo^1,2^,*, Kazutaka Furuse²^,*, Hanxiong Chen²^,*, Nobuo Ohbo²^,*

1: Dept. Computer Science, HuaQiao University, QuanZhou, FuJian, China, 362021
2: Dept. Computer Science, University of Tsukuba, Tennoudai 1-1-1, Tsukuba, Ibaraki 305, Japan

*Contact email: lym@hqu.edu.cn, furuse@dblab.is.tsukuba.ac.jp, chx@dblab.is.tsukuba.ac.jp, ohbo@dblab.is.tsukuba.ac.jp

Abstract

Aggregate Nearest Neighbor Queries are much more complex than Nearest Neighbor queries, and pruning strategies are always utilized in ANN queries. Most of the pruning methods are based on the data index mechanisms, such as R-tree. But for the well-known curse of dimensionality, ANN search could be meaningless in high dimensional spaces. In this paper, we propose two non-index pruning strategies in ANN queries on metric space. Our methods utilize the r-NN query and projecting law, analyze the distributing of query points, find out the search region in data space, and get the result efficiently.

Keywords: Spatial database Aggregate Nearest Neighbor Search Region.

Published: 2010-05-16
Modified: 2011-09-11

: http://dx.doi.org/10.4108/infoscale.2007.900