Space

As explained in Advanced Algorithms and Data Structures

A k-dimensional space is a space in which each point is represented by k coordinates or independent dimensions.

A map needs two coordinates to locate a city. A dataset can use the same idea without being a physical map: an item might have a price and a rating. A k-dimensional space represents each point with k coordinates, so a dataset with d numeric features can store each point as a tuple of d values. To ask which item is closest to a target, first choose a distance measure appropriate to those coordinates; the nearest-neighbor structures considered here use Euclidean distance. section 9.2.1 section 8.3

Moving from one dimension to two changes how points can be indexed. A binary search tree can split a line into left and right ranges, but a point in a plane can divide its region into four quadrants. Splitting on every coordinate at once would give a node 2^k children: about a thousand with 10 dimensions and roughly 10^30 with 100. That branching factor makes the direct approach impractical for high-dimensional datasets. section 8.4 section 8.4.3

A k-d tree avoids that explosion by splitting on only one coordinate at each level. In two dimensions, a vertical split compares x coordinates; the next level uses a horizontal split and compares y coordinates. In k dimensions, level i compares coordinate i modulo k. Each pivot creates two subregions, represented by the left and right subtrees of a binary search tree. section 9.2 section 9.2.1

Figure 9.2 Partitioning points in the 2-D Cartesian space by cycling through the directions along which we split. For the first split (left) we choose point R and draw a vertical line (parallel to y axis, x coordinate is constant) passing through it. We have thus created two half-spaces, a lighter-shaded one on the left and a darker-shaded one on the right of this line, grouping points W, P, O, Q, U on one side, and S, T on the other. Point R is the pivot of this partitioning. Next, we choose point W in the lighter shade partition. This time, we draw a horizontal line (parallel to x axis, y coordinate is constant). It splits the lighter shade partition into two new partitions, one in the top-left area of the plane, containing P, O and U, and one in the bottom-left area, with just Q. If we further split the top-left area at point P, we again need to use a vertical line, as shown in the right-most part of the figure.

Follow the successive vertical, horizontal, and vertical splits to see how a two-dimensional region becomes binary-tree partitions. section 9.2

More coordinates also change the cost and meaning of proximity. Computing a distance between d-coordinate points takes O(d) operations; assigning n points to k centroids over m k-means iterations takes O(mknd) time. In sufficiently high-dimensional, near-uniform data, nearest and farthest distances can become similar, making nearest-neighbor distinctions less useful. K-d trees likewise perform best in low- to medium-dimensional spaces rather than high-dimensional ones. section 12.2.3 section 12.2.2 section 9.5

How Advanced Algorithms and Data Structures covers it

How deep it goes

Defines points as coordinate tuples and works through partitioning and dimensional costs, without developing a general theory of spaces.

Examples

Uses city-map partitions, price-and-rating tuples, and high-dimensional uniformly distributed points to illustrate coordinates and proximity.

What it assumes

Assumes familiarity with binary trees while defining k-dimensional points as tuples with comparable coordinates.

What you can do after

Evaluate/understand when coordinate-based indexing and nearest-neighbor comparisons become costly or less useful as dimensionality grows.

How it connects

Connects binary search trees and k-d trees to nearest-neighbor search, Euclidean distance, and k-means clustering.

liveBookmanning.com

Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Related concepts

• kernel methodused by · A kernel method is a machine-learning technique that uses a kernel function to model relationships in a feature space without explicitly computing the feature representations.
• vector spaceincludes · A vector space is a set equipped with vector addition and scalar multiplication over a field that satisfy the vector-space axioms.
• k-d treecontrasts with · A k-d tree is a binary space-partitioning tree that organizes points in multidimensional space by recursively comparing coordinate dimensions.
• treeconfigures · A tree is a connected, acyclic structure of nodes, commonly organized hierarchically through parent-child relationships and optionally around a designated root.

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.