We consider the basic problem of querying an expert oracle for labeling a dataset in machine learning. This is typically an expensive and time consuming process and therefore, we seek ways to do so efficiently. The conventional approach involves comparing each sample with (the representative of) each class to find a match. In a setting with <inline-formula><tex-math notation="LaTeX">$N$</tex-math><alternatives><mml:math><mml:mi>N</mml:mi></mml:math><inline-graphic xlink:href="lahouti-ieq1-3118644.gif"/></alternatives></inline-formula> equally likely classes, this involves <inline-formula><tex-math notation="LaTeX">$N/2$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>N</mml:mi><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math><inline-graphic xlink:href="lahouti-ieq2-3118644.gif"/></alternatives></inline-formula> pairwise comparisons (queries per sample) on average. We consider a <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="lahouti-ieq3-3118644.gif"/></alternatives></inline-formula>-ary query scheme with <inline-formula><tex-math notation="LaTeX">$k\geq 2$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>k</mml:mi><mml:mo>≥</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math><inline-graphic xlink:href="lahouti-ieq4-3118644.gif"/></alternatives></inline-formula> samples in a query that identifies (dis)similar items in the set while effectively exploiting the associated transitive relations. We present a randomized batch algorithm that operates on a round-by-round basis to label the samples and achieves a query rate of <inline-formula><tex-math notation="LaTeX">$O(\frac{N}{k^2})$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:mfrac><mml:mi>N</mml:mi><mml:msup><mml:mi>k</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mfrac><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="lahouti-ieq5-3118644.gif"/></alternatives></inline-formula>. In addition, we present an adaptive greedy query scheme, which achieves an average rate of <inline-formula><tex-math notation="LaTeX">$\approx 0.2N$</tex-math><alternatives><mml:math><mml:mrow><mml:mo>≈</mml:mo><mml:mn>0</mml:mn><mml:mo>.</mml:mo><mml:mn>2</mml:mn><mml:mi>N</mml:mi></mml:mrow></mml:math><inline-graphic xlink:href="lahouti-ieq6-3118644.gif"/></alternatives></inline-formula> queries per sample with triplet queries. For the proposed algorithms, we investigate the query rate performance analytically and with simulations. Empirical studies suggest that each triplet query takes an expert at most 50% more time compared with a pairwise query, indicating the effectiveness of the proposed <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="lahouti-ieq7-3118644.gif"/></alternatives></inline-formula>-ary query schemes. We generalize the analyses to nonuniform class distributions when possible.