Reading 35: Enhancing KNN Search in Spatial Indexes

Citation:

Cheung, King Lum, and Ada Wai-Chee Fu. "Enhanced nearest neighbour search on the R-tree." ACM SIGMOD Record 27.3 (1998): 16-21.

Publication Link

Summary:

This paper gives an improves set of heuristics for the R* Tree, that makes indexing and retrieving neighbours of any spatial object, much more efficient.

Discussion:

We perform relative indexing primarily by extracting the nearest neighbours of a drawn feature, and checking how much the relative position of the two features match. However, this approach fails drastically when we have insufficient features indexed. In such a case, we have to resort to conventional algorithms that are translation independant.

Reading 34 : 2D Curve Similarity Algorithms

Citation:

Deriche, Rachid, and Olivier Faugeras. "2-D curve matching using high curvature points: application to stereo vision." Pattern Recognition, 1990. Proceedings., 10th International Conference on. Vol. 1. IEEE, 1990.

Publication Link 

Summary:

This paper deals with the high curvature points of curves, and uses derivatives to calculate curve maxima.

Discussion:

Our application requires us to be able to gauge the similarity between two freely drawn curves, and we expect a very optimistic approximation of correctness between a template and candidate curve in the case of rivers.

Although the curve detection methods presented here are for a computer vision domain, they can be easily translated to the sketch domain.