• KSII Transactions on Internet and Information Systems
    Monthly Online Journal (eISSN: 1976-7277)

Ordered Reverse k Nearest Neighbor Search via On-demand Broadcast


Abstract

The Reverse k Nearest Neighbor (RkNN) query is valuable for finding objects influenced by a specific object and is widely used in both scientific and commercial systems. However, the influence level of each object is unknown, information that is critical for some applications (e.g. target marketing). In this paper, we propose a new query type, Ordered Reverse k Nearest Neighbor (ORkNN), and make efforts to adapt it in an on-demand scenario. An Order-k Voronoi diagram based approach is used to answer ORkNN queries. In particular, for different values of k, we pre-construct only one Voronoi diagram. Algorithms on both the server and the clients are presented. We also present experimental results that suggest our proposed algorithms may have practical applications.


Statistics

Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2015)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article

[IEEE Style]
Li Li, Guohui Li, Quan Zhou and Yanhong Li, "Ordered Reverse k Nearest Neighbor Search via On-demand Broadcast," KSII Transactions on Internet and Information Systems, vol. 8, no. 11, pp. 3896-3915, 2014. DOI: 10.3837/tiis.2014.11.013

[ACM Style]
Li, L., Li, G., Zhou, Q., and Li, Y. 2014. Ordered Reverse k Nearest Neighbor Search via On-demand Broadcast. KSII Transactions on Internet and Information Systems, 8, 11, (2014), 3896-3915. DOI: 10.3837/tiis.2014.11.013