ABSTRACT
Two important constraints that the index structures discussed in the previous chapters are that the data objects are available as vectors of some fixed dimensionality and the distances between the objects were measured using the L2 norm. In many applications, however, either the feature vectors are not available explicitly (e.g., text or graphs), or the feature vectors are not of uniform dimensionality (e.g., image keypoints), or the distance between the objects is not a regular Lp distance (e.g., distances in road networks). It is still extremely critical and useful to index such data to allow efficient range and kNN searches. This chapter discusses some of the important index structures that handle such cases where only a distance measure is available between any two data objects.
