Method and apparatus for query processing of uncertain data

• US 7,917,517 B2
• Filed: 02/28/2008
• Issued: 03/29/2011
• Est. Priority Date: 02/28/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu C., Yu, Philip Shi-Lung
• Primary Examiner(s): TO, BAOQUOC N
• Application Number:
  US12/039,091
• Publication Number:
  US 20090222410A1
• Time in Patent Office: 1,125 Days
• Field of Search: None
• US Class Current: 707/741
• CPC Class Codes: G06F 16/3331 Query processing

Abstract

Techniques are disclosed for indexing uncertain data in query processing systems. For example, a method for processing queries in an application that involves an uncertain data set includes the following steps. A representation of records of the uncertain data set is created based on mean values and uncertainty values. The representation is utilized for processing a query received on the uncertain data set.

Claims

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.

2. The method of claim 1, wherein at least a subset of the one or more inverted lists are ordered by mean values.

3. The method of claim 1, wherein at least a subset of the one or more inverted lists are ordered by uncertainty values.

4. The method of claim 1, wherein at least a subset of the one or more inverted lists are ordered by both mean values and uncertainty values.

5. The method of claim 1, wherein the query comprises a range query in which a user specifies a range and threshold probability.

6. The method of claim 5, wherein lists whose spans intersect with the user-specified range are isolated.

7. The method of claim 5, wherein probabilities across different dimensional ranges are multiplied together.

8. The method of claim 5, wherein those records are reported for which a computed probability is greater than a threshold delta.

9. The method of claim 1, wherein the query comprises a similarity query in which the user specifies a target record.

10. The method of claim 9, wherein lists whose spans intersect with a probability density function of the target record are isolated.

11. The method of claim 9, wherein a similarity value is computed over all isolated records.

12. The method of claim 9, wherein the record with the largest similarity value is reported.

13. An article of manufacture for processing queries in an application that involves an uncertain data set, comprising a computer readable storage medium including one or more programs which when executed by a computer perform 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; and

wherein some levels of the index structure are partitioned by mean values, and other levels are partitioned by uncertainty values.

14. Apparatus for processing queries in an application that involves an uncertain data set, comprising:

a memory; and

at least one processor coupled to the memory and operative to create a representation of records of the uncertain data set based on mean values and uncertainty values, and utilize 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; and

wherein some levels of the index structure are partitioned by mean values, and other levels are partitioned by uncertainty values.

15. The apparatus of claim 14, wherein at least a subset of the one or more inverted lists are ordered by mean values.

16. The apparatus of claim 14, wherein at least a subset of the one or more inverted lists are ordered by uncertainty values.

17. The apparatus of claim 14, wherein the query comprises a range query in which a user specifies a range and threshold probability.

18. The apparatus of claim 14, wherein the query comprises a similarity query in which the user specifies a target record.