Multidimensional search capabilities are enabled on a non-PC (personal computer) device being utilized by a user. An original query submitted by the user via the non-PC device is received. A structured data repository is accessed to extract structured data that is available for the original query, where the extracted structured data represents attributes of the original query. The extracted structured data is provided to the user in the form of a hierarchical menu which allows the user to interactively modify the original query, such modification resulting in a revised query.