An estimating model for the number of node accesses in NN search

Yaokai Feng, Akifumi Makinouchi

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


Nearest Neighbor (NN) search has been widely used in spatial databases (e.g., find neighbor cities) and multimedia databases (e.g., similarity search). However, the theoretical analysis on its performance with m (the number of neighbor objects reported finally), n (the cardinality of database) and d (the dimensionality) as parameters has not been done yet. This paper presents an analytical model for estimating performance of the newest NN search algorithm using uniformly distributed objects, focusing on the number of node accesses. The theoretical analysis is verified by experiments.

Original languageEnglish
Pages (from-to)87-92
Number of pages6
JournalResearch Reports on Information Science and Electrical Engineering of Kyushu University
Issue number2
Publication statusPublished - Sept 2002
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'An estimating model for the number of node accesses in NN search'. Together they form a unique fingerprint.

Cite this