Minimum spanning trees

[sweinand]

See

• CPI Manual (2020, p. 449), https://www.ilo.org/wcmsp5/groups/public/---dgreports/---stat/documents/publication/wcms_761444.pdf
• Hill (1999), Comparing Price Levels Across Countries Using Minimum-Spanning Trees (https://www.jstor.org/stable/2646792)
• Hill (1999b), International Comparisons Using Spanning Trees (https://www.nber.org/system/files/chapters/c8386/c8386.pdf)
• Hajargasht et al. (2017), Spatial Chaining in International Comparisons of Prices and Real Incomes (https://thedocs.worldbank.org/en/doc/637701510177729968-0050022017/original/ICPTFPCC01DocSpatialchainingHilletal2017.pdf)

See also this R example, which explains quite good the idea of minimum spanning trees (https://stackoverflow.com/questions/59624905/how-to-calculate-minimum-spanning-tree-in-r). Applied to spatial price comparisons, the Paasche-Laspeyres spread is calculated for the R*(R-1)/2 region pairs and then the minimum spanning tree is derived. The resulting bilateral indices are chained together.

[sweinand]

Deriving the minimum spanning tree following Kruskal's algorithm is quite fast, but the spatial chaining is very slow.

hill_mst.txt