CARTAM : the Cartesian Access Method for Data Structures with n-Dimensional Keys

[摘要] The Cartesian Access Method (CARTAM) is a datastructure and its attendant access program designed toprovide rapid retrievals from a data file based uponmulti-dimensional keys: for example, using earth surface pointsdefined by latitude and longitude, retrieve all pointswithin x nautical miles. This thesis describes that datastructure and program in detail and provides the actualroutines as implemented on the International BusinessMachine (IBM) System/370 series of computers. The searchtechnique is analogous to the binary search for a linearsorted file and seems to run in O(log(N)) time. Anindication of the performance is the extraction, in lessthan 25 milliseconds CPU time on an IBM 370, Model 3033, ofall points within a 10,000-foot circle from a geographicdata base containing approximately 100,000 basic records.

[发布机构] University:California Institute of Technology;Department:Engineering and Applied Science

[关键词] Computer Science