locality

We say an algorithm or problem to be solved has locality, when the date requred for each step is close to one another in memory. This depends on the way in whch data is stored in memory, so that a good choice of knowledge representation can make algoritms more efficient.

Some problems, particularly those involving complex graph processing, are intrinsically non-local – no representation can entirely avoid distant memory accesses. This is particularly important when dealing with big data distributed over many storage devices or even, in cloud computing multiple data centres, as non-local data access may involve substantial network traffic and delays waiting for it. However, it can also be important in parallel processing on GPU chips, or improving cache performance on single computers.