Abstract In many applications, such as online dating or job hunting websites, users often need to search for potential matches based on the requirements or preferences imposed by both sides. We refer to this type of queries as matching queries. In spite of their wide applicabilities, there has been little attention devoted to improving their performance. As matching queries often appear in various forms even within a single application, we, in this paper, propose a general processing framework, which can efficiently process various forms of matching queries. Moreover, we illustrate the applicability of this framework by elaborating the detailed processing algorithms of one particular matching query and its extensions to two other forms of matching queries. We conduct an extensive experimental study with both synthetic and real datasets. The results indicate that, for various matching queries, our techniques can highly improve the query performance, especially when the dimensionality is high.