Some Concepts That Underpin GIS - Introducing Geographic Information Systems with ArcGIS - page 30

However, if we sort the list alphabetically (carrying along the associated number) we would have:
ASD 3456
GHU 2343
OPR 8828
PRO 1234
QWA 9500
UCK 7765
ZYX 7876
Now we can apply a clever strategy. We look first at the middle of the list: PRO. It doesn't match QUA,
but we know that QUA is alphabetically “greater than” PRO, so we only need to be concerned with the
bottom half of the list. We pick the middle of that for the next comparison: UCK. Now we know we've
gone too far, so we go halfway back and find QWA. This process, called a binary search, took only three
comparisons.
This example, which we've kept very small, only hints at the power we have. If our list to be searched
consisted of two million strings, then the first searching method (sometimes called brute force) would,
on average have to do a million comparisons. In the worst case, it would have to do two million
comparisons. How many would a binary search have to do? In the worst case, about 22.
You may say that you realize the tremendous advantage of a binary search (in which you essentially
“throw out half the remaining list each time and, thus, reap the rewards of reducing the list in
an exponential fashion) but you point out that the list had to be alphabetized to begin with. Four
considerations come in to play here. First, computers are very good at sorting—lots of very fast
algorithms exist for the process. Second, the sorting can be done “in the background”—during
times when you aren't sitting in front of the machine waiting for a search to succeed. Third, once the
alphabetization has been done, innumerable sorts can be run—each highly efficient. Last, if a new
element is to be added to the list, it can be inserted in its proper place in the list, without resorting the
entire list.
Another Definition of GIS
Each record in a relational database references something: a person, object, idea, equation, feature,
subject—some unique entity. In a GIS, the entity is usually a spatial three-dimensional feature such as
a parking meter, lake, railroad, and so on. 25 These 3-D features are almost always reduced to abstract
objects of fewer dimensions. The parking meter is a point, the railroad is a set of lines, and the lake is an
area bounded by a sequence of lines.
Usually, a record in a relational database references a person or object without respect to its current
location. A subject of a record in a relational database frequently moves around—like cars or people.
However, when the subjects of a relational database are fixed in space, the position, or positions, of the
feature may be included in the description of the feature along with the attributes. In one sense, the
location of the object becomes one of its attributes.
25 In raster-based GIS, the entity is a set of (usually) square areas that share common values. This approach will be dis-
cussed extensively in Chapter 8.