Ranked Reverse nearest Neighbor Search

Abstract:

Given a set of data points P and a query point q in a multidimensional space, Reverse Nearest Neighbor (RNN) query finds data points in P whose nearest neighbors (NNs) are q. Reverse k-NN ðRkNNÞ query (where k _ 1) generalizes RNN query to find data points whose kNNs include q. For RkNN query semantics, q is said to have an influence on all those answer data points. The degree of q’s influence on a data point p ð2 PÞ is denoted by _p, where q is the _pth NN of p. We introduce a new variant of RNN query, namely, Ranked RNN (RRNN) query, that retrieves t data points most influenced by q, i.e., the t data points having the smallest _s with respect to q. To answer this RRNN query efficiently, we propose two novel algorithms, _-Counting and _-Browsing that are applicable to both monochromatic and bichromatic scenarios and are able to deliver results progressively. Through an extensive performance evaluation, we validate that the two proposed RRNN algorithms are superior to solutions derived from algorithms designed for RkNN query.

Existing System:-

RkNN is not very informative about the influences of a query point on answer data points. It is hard to differentiate one answer data point from another upon influence received from the query point. Therefore, it is useful to determine an influence rank, a predetermined number of influenced data points (with their _s provided) ordered by their _s. This search has a wide application base. For example, a company has some limited quantity of product samples to send to potential customers for promotion. Assume that the promoted product, other competitors’ products, and customers’ preferences are all captured as data points in a multidimensional feature space. Supposethat customers are more likely to purchase a product if it is closer to their preferences in the feature space. Given the number of available samples t, kNN query with k ¼ t finds customers whose preferences match well with the product, but the product may not receive high ranks to those customers due to the existence of other products. RkNN can be adopted to find potential customers. Independent of t, it cannot find exact t potential customers to send the samples. Besides, both kNN and RkNN cannot tell which potential customers are the most (or least) suitable targets. This necessitates a new query that searches the t most influenced data points ranked based on the degree of influence.

Proposed System:-
We propose the Ranked RNN (RRNN) query, formally defined in Definition 3, to retrieve from P the t data points most influenced by a query point q, where t is a query parameter. When t is set to 1, RRNN query returns a data point p that q has the most influence on. Notice that _p may not necessarily be 1. When t ¼ jPj (i.e., the cardinality of the data set), RRNN renders a sorted list of all data points according to their degrees of influence. Since _s are not necessarily unique, the distance between the data points and the query point is used as the tiebreaker. Revisit our previous example. An RRNN query with t set to the number of available samples, say 100, one hundred customers best matched with the promoted product are retrieved


Hardware Requirements:

• Processor : Pentium Iv 2.6 Ghz
• Ram :512 Mb Dd Ram
• Monitor :15” Color
• Hard Disk :20 Gb

Software Requirements:

• Front End : Java, Swing
• Operating System : Window’s Xp