2nd International ICST Conference on Scalable Information Systems

Research Article

Finding Aggregate Nearest Neighbor Efficiently without Indexing

Download525 downloads
  • @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 Luo1,2,*, Kazutaka Furuse2,*, Hanxiong Chen2,*, Nobuo Ohbo2,*
  • 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.