A comparison of multi-key file structures and associative retrieval algorithms for database applications
Dennis Albert Beckley · 1985
The advent of many applications requiring associative retrieval poses serious problems for a database designer trying to choose an appropriate multikey file structure for the multikey retrieval algorithms. This thesis attempts to supply the database designers with experimental observations for some of the best-known multikey structures: inverted lists, quad-trees, and K-d trees. A methodology for file structure comparison with experimentation is also provided. A series of experiments compare the retrieval performance of these structures with each other as well as with flat files for five query classes: exact match, partial match, range search, nearest neighbor, and best match. Algorithms for all of these query classes are given for each file structure; when not available in the literature, they were created. The experiments were run on a large commercial IBM mainframe using a database of half a million characters, the Michael Reese Hospital Stroke Registry. The strategy for the file structure comparison requires query class usage statistics and relative metric weights from the data base designer. For this experiment the metrics assumed were performance as measured by wall clock time and cost as measured by the CPU time and I/O counts. An analysis of variance rejected the null hypotheses for each metric and query class that stated file structures do not affect performance. To find the most appropriate file structure, the Student-Newman-Keuls (SNK) test was run to rank file structures into groups with significant differences. SNK group means and group normalized factors were then computed. A weighted sum of products was computed across each query class and finally a weighted sum of products across each metric was computed to get an overall ranking. The conclusions document the Michael Reese case study. Indeed no file structure dominated all metrics for all query classes, thus there was no optimal file structure. Assuming query usage and metric weights relevant for this application, the overall ranking from best to worst was unbalanced K-d tree, quad-tree, balanced K-d tree, two implementations of the inverted list, and finally the flat file.