In previous work, the notion of polyadic similarity query was introduced. Normally, similarity queries take a single argument and attempt to find those objects within a large collection which are most similar to that argument. The idea of polyadic queries is to generalise this notion, by taking a number of query arguments, and giving results based on some combination of their characteristics. It was previously shown how polyadic queries could be of use in various contexts. The initial work on polyadic queries provided a proof of concept but left many unanswered questions. In particular, it did not show a proper semantic basis for the polyadic query function used or how to achieve sub-linear query times for polyadic searches over large data. Here, we address these issues. This work demonstrates that the polyadic query mechanism can scale to large data, and gives results which are better than those obtained by executing simple queries over each of the arguments individually.