On the Boundedness of Reverse Nearest Neighbors in Arbitrary Dimensions

Seal, Sudip (2004) On the Boundedness of Reverse Nearest Neighbors in Arbitrary Dimensions. Publisher UNSPECIFIED.

This is the latest version of this eprint.

Full text available as:

PDF - Registered users only - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

Run time analysis of algorithms involving reverse nearest neighbor (RNN) queries, particularly in higher dimensions, often become impossible for lack of hard upper bounds on the maximum size of the reverse nearest neighbor set. In this paper, we present a formulation of the RNN problem which enables calculation of such bounds in the static monochromatic case under the L2-norm in any dimension. We also show that there exists a lower bound on the maximum size of the RNN set and how the gap between the above bounds can be reduced. The results in lower dimensions are remarkably accurate while those in higher dimensions are very promising.

EPrint Type:	Technical Report
Uncontrolled Keywords:	Reverse nearest neighbors
Subjects:	Computer Engineering > SOFTWARE SYSTEMS > Computational Biology and Computational Science
ID Code:	80
Identification Number:	TR-2004-06-2
Deposited By:	Mr Sudip Seal
Deposited On:	08 July 2004

Available Versions of this Item

On the Boundedness of Reverse Nearest Neighbors in Arbitrary Dimensions (deposited 08 July 2004) [Currently Displayed]

Archive Staff Only: edit this record