1. A method of processing queries in an application that involves an uncertain data set, comprising the steps of: creating a representation of records of the uncertain data set based on mean values and uncertainty values; and utilizing the representation for processing a query received on the uncertain data set; wherein the representation of records comprises a multi-level inverted index structure comprising one or more inverted lists; wherein some levels of the index structure are partitioned by mean values, and other levels are partitioned by uncertainty values; and wherein the steps are performed at least in part by a processor device.