CARTAM. The Cartesian Access Method for Data Structures with n-dimensional Keys

摘要

The Cartesian Access Method (CARTAM) is a data structure and its attendant access program designed to provide rapid retrievals from a data file based upon multi-dimensional keys; for example, using earth surface points defined by latitude and longitude, retrieve all points within x nautical miles. This thesis describes that data structure and program in detail and provides the actual routines as implemented on the International Business Machine (IBM) System/370 series of computers. The search technique is analogous to the binary search for a linear sorted file and seems to run in O(log(N)) time. An indication of the performance is the extraction, in less than 25 milliseconds CPU time on an IBM 370, Model 3033, of all points within a 10,000-foot circle from a geographic data base containing approximately 100,000 basic records. (Author)