Data Sharing Through Query Translation in Autonomous Sources Anastasios Kementsietsidis and Marcelo Arenas   View Paper (PDF)   Return to RESEARCH SESSION 11:DISTRIBUTED SEARCH AND QUERY PROCESSING Abstract Given a point q, a reverse k nearest neighbor (RkNN) query retrieves all the data points that have q as one of their k nearest neighbors. Existing methods for processing such queries have at least one of the following deficiencies: (i) they do not support arbitrary values of k (ii) they cannot deal efficiently with database updates, (iii) they are applicable only to 2D data (but not to higher dimensionality), and (iv) they retrieve only approximate results. Motivated by these shortcomings, we develop algorithms for exact processing of RkNN with arbitrary values of k on dynamic datasets of any dimensionality. Our methods utilize a conventional multi-dimensional index on the dataset and do not require any pre-computation. In addition to their flexibility, we experimentally verify that the proposed algorithms outperform the existing ones even in their restricted focus. ©2005 Association for Computing Machinery