Advances in Network Positioning: Unsupervised Clustering and Supervised Hierarchical Ranking Algorithms

GPS provides high‑precision positioning but suffers from long cold‑start times, poor indoor or obstructed‑scene performance, and the need for continuous location updates. To overcome these limitations, network positioning leverages signals from base stations, Wi‑Fi, and Bluetooth, sending them to a server that matches them against a massive, continuously updated fingerprint database.

Gaode (Amap) network positioning processes billions of requests daily, serving both its own map users and over 300,000 third‑party apps. Over recent years the service has evolved from purely unsupervised fingerprint algorithms to supervised models, improving both accuracy and capability.

1. Unsupervised clustering algorithm

The classic fingerprint method computes similarity between a new signal vector and historical fingerprints (e.g., using K‑Nearest Neighbors with L2 distance or cosine similarity). This approach is computationally prohibitive because the number of APs reaches billions and historical locations reach trillions.

To reduce computation, historical data are pre‑processed to extract a universal fingerprint for each AP: its estimated location and coverage radius obtained via clustering of past observations. During positioning, the weighted average of multiple AP locations yields an initial estimate.

When multiple candidate clusters exist, a scoring strategy based on cluster features selects the most probable cluster.

Because fingerprint distribution is irregular (affected by buildings, terrain, roads), a grid‑based ranking method is introduced. The earth is divided into 25 × 25 grids; each grid stores statistical histograms of signal strengths for every AP. For a request, the algorithm computes a score for each grid using a Bayesian formulation:

P(l|S) ∝ P(l) × Π_i P(s_i|l)

where P(l) is the prior probability of a grid (derived from positioning PV) and P(s_i|l) assumes independence of signal dimensions. Grids are then sorted by the resulting probability, and the top grid is selected as the location.

2. Supervised hierarchical algorithm

Unsupervised methods cannot be easily iterated for bad cases, prompting a shift to supervised learning. Gaode now employs a two‑level hierarchy: a coarse‑grid layer for large areas and a fine‑grid layer for detailed refinement, reducing computation while preserving accuracy for >100k QPS workloads.

Each candidate grid is scored by a neural network trained with a Learning‑to‑Rank (LTR) loss. Three feature groups are used:

Dynamic AP features (e.g., signal strength)

Grid‑level features (PV, UV, AP count, neighboring grid count, etc.)

AP‑in‑grid features (signal distribution, PV, UV)

Historical positioning points are incorporated as an additional feature, allowing the model to weight grids closer to the predicted historical location higher, which reduces large‑error cases by about 20%.

3. Scenario‑specific positioning

Different user scenarios demand different accuracy levels. Gaode optimizes for indoor, high‑speed rail, and subway environments:

Indoor: A CNN transforms floor‑plan, POI, and ground‑truth data into 2‑D images, learning to map Wi‑Fi signals to real indoor locations. This improves indoor correct‑location ratio by 15%.

High‑speed rail: Mobile Wi‑Fi APs are detected and filtered using spatio‑temporal features, achieving >99% precision and recall, eliminating most rail‑related positioning errors.

Subway: When only mobile Wi‑Fi is available, Gaode infers base‑station positions via adjacent fixed stations or user trajectory analysis, reaching >90% positioning accuracy inside tunnels.

4. Future directions

Upcoming advances include image‑based positioning (e.g., Google’s AR street‑view solution), 5G‑based ranging with phase‑difference measurements, and IoT positioning using NB‑IoT or P2P techniques.