EFFICIENT ALGORITHMS FOR CONSTRUCTING PROPER HIGHER-ORDER SPATIAL LAGOPERATORS

This paper extends the work of Blommestein and Koper (1992)-BK-on the construction of higher-order spatial lag operators without redundant a nd 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 sugges ted. 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 spati al lag operators and to the most efficient data structures for the sto rage acid manipulation of spatial lags. The new forward iterative algo rithm which uses a list form rather than a matrix to store the spatial lag information is shown to be several orders of magnitude faster tha n the BK solution. This allows the computation of proper higher-order spatial lags ''on the fly'' for even moderately large data sets such a s 3,111 contiguous U.S. counties, which is not practical with the othe r algorithms.