A single neighborhood radius can fail on data with uneven density: a small radius fragments a sparse cluster, while a larger one merges nearby dense clusters. OPTICS instead orders points by how readily they can be reached from an expanding cluster. Reachability distance supplies the value used to choose the next point. section 12.4 section 12.4.2
For a core point p and a candidate q, reachabilityDistance(q from p) = max(coreDistance(p), distance(p, q)). The core distance is the smallest neighborhood radius that gives p enough neighbors under minPoints. Thus even a very close q cannot have a reachability distance below p’s core distance. Direction matters: reversing p and q may change the core distance used, so reachability distance is not symmetric. If p lacks enough neighbors within εMAX to be a core point, this distance from p is undefined. section 12.4.1 section 12.4.2
Updating the frontier
When processing a core point p, inspect its unprocessed neighbors within εMAX. Calculate max(coreDistance(p), distance(p, q)) for each neighbor q; record it if q has no value, or replace q’s value if the new one is smaller. A priority queue then makes the candidate with the smallest recorded reachability distance the next point processed. section 12.4.2
Listing 12.8 OPTICS updateQueue
function updateQueue(p, kdTree, queue, processed, rDists, eps, minPts) #1
neighbors ← kdTree.pointsInSphere(p, eps) #2
if |neighbors| < minPoints then #3
return queue, rDists
for q in neighbors do #4
if q in processed then #4
continue
newRDist = max(coreDistance(p, eps, minPts), distance(p, q)) #5
if rDists[q] == null then #6
rDists[q] ← newRDist #7
queue.insert(q, newRDist) #7
elsif newRDist < rDist[q] then #8
rDist[q] ← newRDist #9
queue.update(q, newRDist) #9
return queue, rDists #10
The updateQueue listing shows the directional formula, the core-point check, and how an unprocessed neighbor’s best recorded distance is updated. section 12.4.2
The resulting ordering and distances support a reachability plot and a later clustering step. Choose a cutoff ε no greater than εMAX to derive a flat clustering; this cutoff plays the role of DBSCAN’s neighborhood radius. Increasing εMAX can leave fewer distances undefined, but each processed point may then have more neighbors whose values need updating, making OPTICS slower. section 12.4.3 section 12.4.2
