Providing accurate predictions efficiently with privacy is imperative for both customers and e-commerce vendors. However, privacy, accuracy, and performance are conflicting goals. Although producing referrals with privacy is possible; however, online performance and accuracy degrade due to underlying privacy-preserving measures. We investigate how to improve both efficiency and accuracy of naïve Bayesian classifier-based private recommendations by utilizing preprocessing. We preprocess masked data by selecting the best similar items to each item off-line. Moreover, we fill some of the unrated items' cells to improve density. We perform real data-based experiments to investigate how preprocessing affects online performance and accuracy. Our experiment results show that efficiency and preciseness improve due to preprocessing. © 2010 IEEE.