System and method of determining and searching for patterns in a large database

• US 6,799,175 B2
• Filed: 04/23/2001
• Issued: 09/28/2004
• Est. Priority Date: 04/23/2001
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu C.
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): GODDARD, BRIAN D
• Application Number:
  US09/840,652
• Publication Number:
  US 20020169772A1
• Time in Patent Office: 1,254 Days
• Field of Search: 707/6, 707/5, 707/1, 707/2, 707/3, 707/4, 345/712, 345/440
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2425 Iterative querying; Query formulation based on the results of a preceding query
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Techniques are provided for finding query responses from database queries using an interactive process between a user (e.g., a person entering a query to a database) and a computer system (e.g., a computing system upon which the database resides or which has access to the database). The interactive process comprises providing the user with one or more visual perspectives as feedback on the distribution of points in the database. These visual perspectives may be considered by the user in order for the user to provide feedback to the computer system. The computer system may then use the user-provided feedback to determine the best response to the query.

Claims

1. A computer-based method of querying a database, the method comprising the steps of:

generating at least one visual representation of data associated with the database in response to a query entered by a user, the visual representation being density-based and including an indication of a location of at least one query point within the density-based visual representation;

presenting the at least one visual representation to the user; and

determining a result of the query based on at least one response received from the user, the at least one response being provided by the user in accordance with the user viewing the at least one visual representation including the location of the at least one query point and specifying at least one density value corresponding to a preference of the user.

2. The method of claim 1, wherein the steps of generating the visual representation, presenting the visual representation and receiving user response are iterated a number of times, based on a user'"'"'s criterion, to determine a result of the query.

3. The method of claim 1, wherein the query entered by the user specifies the at least one query point.

4. The method of claim 1, wherein the at least one visual representation comprises a density profile.

5. The method of claim 4, wherein the density profile is generated using kernel density estimation.

6. The method of claim 4, wherein the at least one user response comprises the user specifying a hyperplane in accordance with the at least one visual representation.

7. The method of claim 6, wherein the hyperplane specifies a region of the density profile which the user determines to most likely contain a match to the query.

8. The method of claim 1, wherein the at least one visual representation is generated randomly.

9. The method of claim 1, wherein the at least one visual representation is generated based on a distribution of the data in the locality of a query point associated with the user-entered query.

10. The method of claim 1, wherein the at least one visual representation is a density profile and the at least one user response comprises the user specifying a density value to determine a set of data points in the database which are most relevant to the user-entered query.

11. The method of claim 10, wherein the user specification of a density value represents user votes for data points identified by the specification, and further wherein user votes over two or more density value specifications are counted to determine the query result.

12. The method of claim 11, wherein the counts of the votes are used to determine the most suitable nearest neighbors to a query point associated with the user-entered query.

13. The method of claim 1, wherein the query result comprises one or more patterns in the data associated with the database.

14. The method of claim 1, wherein the query result comprises one or more clusters in the data associated with the database.

15. The method of claim 14, wherein the one or more clusters in the data are determined by finding the patterns most closely related to different target objects which are randomly sampled from the database.

16. An apparatus for querying a database, the apparatus comprising:

at least one processor operative to;

(i) generate at least one visual representation of data associated with the database in response to a query entered by a user, the visual representation being density-based and including an indication of a location of at least one query point within the density-based visual representation;

(ii) cause the presentation of the at least one visual representation to the user; and

(iii) determine a result of the query based on at least one response received from the user, the at least one response being provided by the user in accordance with the user viewing the at least one visual representation including the location of the at least one query point and specifying at least one density value corresponding to a preference of the user.

17. The apparatus of claim 16, wherein the operations of generating the visual representation, presenting the visual representation and receiving user response are iterated a number of times, based on a user'"'"'s criterion, to determine a result of the query.

18. The apparatus of claim 16, wherein the query entered by the user specifies the at least one query point.

19. The apparatus of claim 16, wherein the at least one visual representation comprises a density profile.

20. The apparatus of claim 19, wherein the density profile is generated using kernel density estimation.

21. The apparatus of claim 19, wherein the at least one user response comprises the user specifying a hyperplane in accordance with the at least one visual representation.

22. The apparatus of claim 21, wherein the hyperplane specifies a region of the density profile which the user determines to most likely contain a match to the query.

23. The apparatus of claim 16, wherein the at least one visual representation is generated randomly.

24. The apparatus of claim 16, wherein the at least one visual representation is generated based on a distribution of the data in the locality of a query point associated with the user-entered query.

25. The apparatus of claim 16, wherein the at least one visual representation is a density profile and the at least one user response comprises the user specifying a density value to determine a set of data points in the database which are most relevant to the user-entered query.

26. The apparatus of claim 25, wherein the user specification of a density value represents user votes for data points identified by the specification, and further wherein user votes over two or more density value specifications are counted to determine the query result.

27. The apparatus of claim 26, wherein the counts of the votes are used to determine the most suitable nearest neighbors to a query point associated with the user-entered query.

28. The apparatus of claim 16, wherein the query result comprises one or more patterns in the data associated with the database.

29. The apparatus of claim 16, wherein the query result comprises one or more clusters in the data associated with the database.

30. The apparatus of claim 29, wherein the one or more clusters in the data are determined by finding the patterns most closely related to different target objects which are randomly sampled from the database.

31. An article of manufacture for querying a database, the article comprising a machine readable medium containing one or more programs which when executed implement the steps of:

generating at least one visual representation of data associated with the database in response to a query entered by a user, the visual representation being density-based and including an indication of a location of at least one query point within the density-based visual representation;

presenting the at least one visual representation to the user; and

determining a result of the query based on at least one response received from the user, the at least one response being provided by the user in accordance with the user viewing the at least one visual representation including the location of the at least one query point and specifying at least one density value corresponding to a preference of the user.

32. The article of claim 31, wherein the steps of generating the visual representation, presenting the visual representation and receiving user response are iterated a number of times, based on a user'"'"'s criterion, to determine a result of the query.

33. The article of claim 31, wherein the query entered by the user specifies at least one query point.

34. The article of claim 31, wherein the at least one visual representation comprises a density profile.

35. The article of claim 34, wherein the density profile is generated using kernel density estimation.

36. The article of claim 34, wherein the at least one user response comprises the user specifying a hyperplane in accordance with the at least one visual representation.

37. The article of claim 36, wherein the hyperplane specifies a region of the density profile which the user determines to most likely contain a match to the query.

38. The article of claim 31, wherein the at least one visual representation is generated randomly.

39. The article of claim 31, wherein the at least one visual representation is generated based on a distribution of the data in the locality of a query point associated with the user-entered query.

40. The article of claim 31, wherein the at least one visual representation is a density profile and the at least one user response comprises the user specifying a density value to determine a set of data points in the database which are most relevant to the user-entered query.

41. The article of claim 40, wherein the user specification of a density value represents user votes for data points identified by the specification, and further wherein user votes over two or more density value specifications are counted to determine the query result.

42. The article of claim 41, wherein the counts of the votes are used to determine the most suitable nearest neighbors to a query point associated with the user-entered query.

43. The article of claim 31, wherein the query result comprises one or more patterns in the data associated with the database.

44. The article of claim 31, wherein the query result comprises one or more clusters in the data associated with the database.

45. The article of claim 44, wherein the one or more clusters in the data are determined by finding the patterns most closely related to different target objects which are randomly sampled from the database.

46. An interactive feedback-based method of querying a database involving a user and a computer system, the method comprising the steps of:

the user entering a query;

the computer system generating at least one visual representation of data associated with the database in response to the query entered by a user, the visual representation being density-based and including an indication of a location of at least one query point within the density-based visual representation;

the computer system presenting the at least one visual representation to the user;

the user viewing the at least one visual representation;

the user providing at least one response to the computer system after viewing the at least one visual representation, the response including a specification of at least one density value corresponding to a preference of the user; and

the computer system determining a result of the query based on the at least one response provided by the user.