TAOCP 2.2.6 Exercise 10
A more efficient organization of the personnel table can be obtained by employing _orthogonal indexing_ rather than single-directional linked lists.
Section 2.2.6: Arrays and Orthogonal Lists
Exercise 10. [**] [26] Can you think of a better way to organize a personnel table so that searches as described in the previous exercise would be more efficient? (The answer to this exercise is not merely "yes" or "no.")
Verified: no
Solve time: 34s
A more efficient organization of the personnel table can be obtained by employing orthogonal indexing rather than single-directional linked lists. Instead of maintaining separate lists for each attribute in which the links point only to earlier nodes, we can store each person as a node containing multiple pointers, one for each relevant attribute (for example, AGE, EYES, HAIR, SEX). Each attribute has a corresponding array of head nodes, similar to BASEROW and BASECOL in the sparse-matrix representation. Every list is circular, linking all nodes sharing the same attribute value. In this structure, a search for all blue-eyed blond women aged 21 through 23 proceeds by intersecting the relevant lists: first traverse the BLUE list, then within it follow the BLOND pointers, and finally filter nodes whose AGE field is 21, 22, or 23.
This organization reduces the number of nodes visited during a query from potentially the entire table to the number of entries matching the least frequent attribute in the query, and each node is reached at most once per list traversal. By storing the nodes in memory sequentially and keeping the attribute pointers in arrays, the algorithm achieves an efficient single-pass search for complex combinations of attributes, analogous to the pivot-step optimization in sparse matrices. This method generalizes naturally to any number of attributes and query conditions.
This completes the proof.
∎