Affiliations: [a] Department of Computer Information Systems, College of St. Scholastica, Duluth, MN 55811 | [b] Department of Computer Science, North Dakota State University, Fargo, ND 58105 | [c] Department of Computer Science, Concordia College, Moorhead, MN 56560 | [d] Department of Computer Science, Mankato State University, Mankato, MN
Correspondence:
[*]
To whom all correspondence should be addressed.
Abstract: This article presents a new data structure for multi way and general join query acceleration, the hit-list, and an algorithm for its use. The hit-list is a surrogate index providing the mapping between the values of two attributes in a relation participating in an equijoin or a selection. The results of an analytical model, simulation study, and an implementation are presented. The performance advantages of this approach are made clear, as well as the basis for these results in the attainment of full selectivity. Extensions of hit-lists are also examined.
