Exploring Large Textual Data Sets Via Interactive Aggregation

• US 20100121847A1
• Filed: 11/11/2008
• Published: 05/13/2010
• Est. Priority Date: 11/11/2008
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Olston, Christopher
• Granted Patent: US 8,732,160 B2
• Time in Patent Office: Days
• US Class Current: 707/736
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query

Abstract

A method and a system are provided for exploring a large textual data set via interactive aggregation. In one example, the method includes receiving the large textual data set and an original query template, building an index for the query template, wherein the building the index comprises ordering the index a particular way to optimize query time, receiving one or more bindings for the original query template, computing an answer to the original query template using the index and the one or more bindings, and anticipating one or more future queries that a user may submit and that are related to the original query template.

Claims

1. A method for exploring a large textual data set via interactive aggregation, the method comprising:

receiving the large textual data set and an original query template;

building an index for the query template, wherein the building the index comprises ordering the index a particular way to optimize query time;

receiving one or more bindings for the original query template;

computing an answer to the original query template using the index and the one or more bindings; and

anticipating one or more future queries that a user may submit and that are related to the original query template.

2. The method of claim 1, further comprising computing one or more answers to the one or more future queries using the index and the one or more bindings.

3. The method of claim 1, wherein the building the index further comprises semi-clustering the large textual data set according to the original query template.

4. The method of claim 3, wherein the semi-clustering does not involve random ordering of the index, and wherein a time to answer a particular user query with the semi-clustering is substantially less than a time to answer the particular user query without the semi-clustering.

5. The method of claim 1, further comprising at least one of:

precomputing a set of drill-down queries from the original query template;

determining that the set of drill-down queries is small; and

computing answers to the drill-down queries using an independent lookup strategy;

6. The method of claim 1, further comprising inserting forward bitmaps into the index.

7. The method of claim 6, further comprising at least one of:

precomputing drill-down queries from the original query template;

determining that the set of drill-down queries is large; and

computing answers to the drill-down queries simultaneously via a single index lookup.

8. The method of claim 1, further comprising at least one of:

determining that the original query template is a candidate for precomputing; and

precomputing an answer to the original query in an online fashion.

9. The method of claim 8, wherein the original query is a dense query, and wherein the precomputing occurs in a background in an interruptible process that terminates soon after a new query is received.

10. The method of claim 8, wherein the determining that the original query template is a candidate for precomputing comprises using a hashed counter technique.

11. A system for exploring a large textual data set via interactive aggregation, wherein the system is configured for:

receiving the large textual data set and an original query template;

building an index for the query template, wherein the building the index comprises ordering the index a particular way to optimize query time;

receiving one or more bindings for the original query template;

computing an answer to the original query template using the index and the one or more bindings; and

anticipating one or more future queries that a user may submit and that are related to the original query template.

12. The system of claim 11, wherein the system is further configured for computing one or more answers to the one or more future queries using the index and the one or more bindings.

13. The system of claim 11, wherein the system is further configured for semi-clustering the large textual data set according to the original query template.

14. The system of claim 13, wherein the semi-clustering does not involve random ordering of the index, and wherein a time to answer a particular user query with the semi-clustering is substantially less than a time to answer the particular user query without the semi-clustering.

15. The system of claim 11, wherein the system is further configured for at least one of:

precomputing a set of drill-down queries from the original query template;

determining that the set of drill-down queries is small; and

computing answers to the drill-down queries using an independent lookup strategy;

16. The system of claim 11, wherein the system is further configured for inserting forward bitmaps into the index.

17. The system of claim 16, wherein the system is further configured for at least one of:

precomputing drill-down queries from the original query template;

determining that the set of drill-down queries is large; and

computing answers to the drill-down queries simultaneously via a single index lookup.

18. The system of claim 11, wherein the system is further configured for at least one of:

determining that the original query template is a candidate for precomputing; and

precomputing an answer to the original query in an online fashion.

19. The system of claim 18, wherein the original query is a dense query, and wherein the precomputing occurs in a background in an interruptible process that terminates soon after a new query is received.

20. The system of claim 18, wherein the determining that the original query template is a candidate for precomputing comprises using a hashed counter technique.

21. A computer readable medium carrying one or more instructions for exploring a large textual data set via interactive aggregation, wherein the one or more instructions, when executed by one or more processors, cause the one or more processors to perform the steps of:

receiving the large textual data set and an original query template;

building an index for the query template, wherein the building the index comprises ordering the index a particular way to optimize query time;

receiving one or more bindings for the original query template;

computing an answer to the original query template using the index and the one or more bindings; and

anticipating one or more future queries that a user may submit and that are related to the original query template.