Given a query object q, reverse k -nearest neighbor (R k NN) search aims to locate those objects of the database that have q among their k -nearest neighbors. In this paper, we propose an approximation method for solving R k NN queries, where the pruning operations and termination tests are guided by a characterization of the intrinsic dimensionality of the data. The method can accommodate any index structure supporting incremental (forward) nearest-neighbor search for the generation and verification of candidates, while avoiding impractically-high preprocessing costs. We also provide experimental evidence that our method significantly outperforms its competitors in terms of the tradeoff between execution time and the quality of the approximation. Our approach thus addresses many of the scalability issues surrounding the use of previous methods in data mining.

Executing multi-agent missions requires managing the uncertainty about uncontrollable events. When communications are intermittent, it additionally requires for each agent to act only based on its local view of the problem, that is independently of events which are controlled or observed by the other agents. In this paper, we propose a new framework for dealing with such contexts, with a focus on mission plans involving temporal constraints. This framework, called Multi-agent Simple Temporal Network with Uncertainty (MaSTNU), is a combination between Multi-agent Simple Temporal Network (MaSTN) and Simple Temporal Network with Uncertainty (STNU). We define the dynamic controllability property for MaSTNU, and a method for computing offline valid execution strategies which are then dispatched between agents. This method is based on a mixed-integer linear programming formulation and can also be used to optimize criteria such as the temporal flexibility of multi-agent plans.