To a GIS salesman, one of the most important features of their product
is how fast it can sift through the data and put the layers that
the user has selected onto the screen. Because users can select data
based on spatial location, attributes, and level of detail,
multidimensional access structures (B-trees, -D trees, quadtrees,
R-trees) are important and tuning these is a difficult task:
van Oosterom's book on reactive data structures [139]
is an example of what can be done.
Existing legacy data limits the applicability of new research. One cannot expect people to adopt a data structure if it involves expensive conversion. An emerging opportunity, however, is the partitioning of GIS tasks between server and clients. For various reasons (data management, resource needs, etc) it is natural to put spatial data on a large server and have clients request the regions and attributes for the problem that they are interested in. With this architecture, what information should be sent by the server to help clients build geometric structures for local analysis? If the input is line segments, then sending a trapezoidation helps a number of algorithms, but maintaining a trapezoidation on the server may increase the data structure size and involve data conversion. Sorting by first coordinate may be a less-costly improvement.