Efficient algorithms for constructing proper higher order spatial lag operators

This paper extends the work of Blommestein and Koper (1992)-BK-on the construction of higher-order spatial lag operators without redundant and circular paths. For the case most relevant in spatial econometrics and spatial statistics, i.e., when contiguity between two observations (locations) is defined in a simple binary fashion, some deficiencies of the BK algorithms are outlined, corrected and an improvement suggested. In addition, three new algorithms are introduced and compared in terms of performance for a number of empirical contiguity structures. Particular attention is paid to a graph theoretic perspective on spatial lag operators and to the most efficient data structures for the storage acid manipulation of spatial lags. The new forward iterative algorithm which uses a list form rather than a matrix to store the spatial lag information is shown to be several orders of magnitude faster than the BK solution. This allows the computation of proper higher-order spatial lags ''on the fly'' for even moderately large data sets such as 3,111 contiguous U.S. counties, which is not practical with the other algorithms.