Surface k-NN query processing

A k-NN query finds the k nearest-neighbors of a given point from a point database. When it is sufficient to measure object distance using the Euclidian distance, the key to efficient k-NN query processing is to fetch and check the distances of a minimum number of points from the database. For many applications, such as vehicle movement along road networks or rover and animal movement along terrain surfaces, the distance is only meaningful when it is along a valid movement path. For this type of k-NN queries, the focus of efficient query processing is to minimize the cost of computing distances using the environment data (such as the road network data and the terrain data), which can be several orders of magnitude larger than that of the point data. Efficient processing of k-NN queries based on the Euclidian distance or the road network distance has been investigated extensively in the past. In this paper, we investigate the problem of surface k-NN query processing, where the distance is calculated from the shortest path along a terrain surface. This problem is very challenging, as the terrain data can be very large and the computational cost of finding shortest paths is very high. We propose an efficient solution based on multiresolution terrain models. Our approach eliminates the need of costly process of finding shortest paths by ranking objects using estimated lower and upper bounds of distance on multiresolution terrain models.

Animal migration: is there a common migratory syndrome?

Ornithologists, and especially northern hemisphere ornithologists, have traditionally thought of migration as an annual return movement of populations between regular breeding and non-breeding grounds. Problems arise because selection does not ordinarily act on populations and because organisms of many taxa (including birds) are clearly migrants, but fail to undertake movements of the kind described. There are also extensive return movements that are not migratory. I propose that it is more useful to think of migration as a syndrome of behavioral and other traits that function together within individuals, and that such a syndrome provides a common ground across taxa from aphids to albatrosses. Large-scale return movements of populations are one outcome of the syndrome. Similar behavioral and physiological traits serve both to define migration and to provide a test for it. I use two insect (Hemipteran) examples to illustrate migratory syndromes and to demonstrate that, in many migrants, behavior and physiology correlate with life history and morphological traits to form syndromes at two levels. I then compare the two Hemipterans with migration in birds, butterflies, and fish to assess the question of whether there are migratory syndromes in common between these diverse migrants. Syndromes are more similar at the level of behavior than when morphology and life history traits are included. Recognizing syndromes leads to important evolutionary questions concerning migration strategies, trade-offs, the maintenance of genetic variance and the responses of migratory syndromes to both similar and different selective regimes.