Differences

This shows you the differences between two versions of the page.

--- graduation_projects [2018/12/20 12:35] – administrator
+++ graduation_projects [2021/06/06 14:26] – [Nearest-neighbour-preserving sets of space-filling curves (BM)] administrator
@@ Line 20: / Line 20: @@
 Similar to the project mentioned above, we would design an algorithm to search a space of possible designs guided by feedback solicited from the user. However, in this project, it is not building designs we want to explore, but schematizations of public transportation networks, in order to find a most appealing design for a schematized map.
-====Nearest-neighbour-preserving sets of space-filling curves (BM)====
-A space-filling curve is essentially a continuous, surjective function //f// from the unit interval to some two- or higher-dimensional volume. As //t// goes from 0 to 1, the image //f//(//t//) traces out a curve that eventually visits each point of the higher-dimensional volume. One way to build a data structure for approximate nearest-neighbour queries among //d//-dimensional points is the following: put all data points in each of //k// sorted lists corresponding to //k// well-chosen space-filling curves. In each list, the points are sorted by the order in which they appear along the corresponding space-filling curve. To find a nearest neighbour to a point //q//, one first finds the predecessor and successor of //q// in each of the //k// lists. Now report, from these 2//k// points, the point that is closest to //q//. Liao et al. describe how, with //k//=//d//+1 well-chosen curves, one can guarantee that the Euclidean distance from //q// to the reported point is at most a factor //O//(//d//²) worse than the distance from //q// to the true closest point in the complete data set.
-That guarantee is not as good as we would like it to be, and this may have something to do with the following fact: at many points of the space-filling curves used by Liao et al., 2<sup>//d//</sup> regions meet, and most of these are very far from each other along the curve. However, it is possible to construct space-filling curves where, at any point, at most only //d//+1 regions meet that may be far away from each other along the curve. Could we use such curves to get a better approximation ratio on the distance to the nearest neighbour? Or to achieve the same approximation ratio with fewer curves?
 ====Quantifying the roughness of space-filling curves (M)====

Herman Haverkort

User Tools

Site Tools

Differences

Page Tools