This paper concerns a study of information content in postal address fields for automatic address interpretation. Information provided by a combination of address components and information interaction among components is characterized in terms of Shannon's entropy. The efficiency of assignment strategies for determining a delivery point code can be compared by the propagation of uncertainty in address components. The quantity of redundancy between components can be computed from the information provided by these components. This information is useful in developing a strategy for selecting a useful component for recovering the value of an uncertain component. The uncertainty of a component based on another known component can be measured by conditional entropy. By ranking the uncertainty quantity, the effective processing flow for determining the value of a candidate component can be constructed.

Providing a lexicon for all possible postal addresses can support decision making for handwritten address interpretation. The possibility of uncertainty can be reduced by choosing the highest confident record in the provided lexicon as the target postal address. For a large database with multi-attribute records, traditional access methods are not efficient enough to generate the lexicon. This paper proposes a hyperlinked embedded access structure (HEAS) which combines the features of inverted file structure and doubly-chained tree structure with unique data compression schemes. The raw United State Postal Service (USPS) database is organized according to the proposed access structure, and the organized database serves as a knowledge base for interpreting handwritten addresses. The organization cost, storage requirement, and query cost are analyzed and compared to conventional inverted file and doubly-chained tree structures.

A parallel architecture is proposed for a high speed query server to process postal addresses with several fields. For a given component in a field, the offset addresses of records which contain the component in a postal address database are coded into a Compressed Bit Vector (CBV). Finding the appropriate CBVs and performing intersections to get matching offset addresses are key bottleneck for the performance in the query server. They are accomplished by a specialized hardware embedded in a general purpose computer for a cost effective solution. This hardware directly operates on the CBVs using parallel schemes. The architecture and algorithms for expanding a CBV, for synchronizing the parallel processing of the processing units, and for balancing the load in the pipelined stages are presented with simulation results.