The focus of this paper is on computing a top-k correlated-pairs query that returns the top k pairs of positively correlated items. As a motivating example, the top-k correlated-pairs query can reveal information about how the sales of a product are related to the sales of other products. This type of information can be useful for sales promotions, catalog design, and store layout. However, as the number of items and transactions in the data set increases, the computational cost of the top-k correlated-pairs query becomes prohibitively expensive.