Method and system for searching documents with numbers

• US 7,010,520 B2
• Filed: 04/26/2002
• Issued: 03/07/2006
• Est. Priority Date: 04/26/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Agrawal, Rakesh, Srikant, Ramakrishnan
• Primary Examiner(s): Wong, Leslie
• Application Number:
  US10/134,406
• Publication Number:
  US 20030204494A1
• Time in Patent Office: 1,411 Days
• Field of Search: 707/3, 707/4, 707/5, 707/6, 707/1, 707/10, 707/104.1, 707/7, 709/203, 709/219
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A system and method for using numbers to query a corpus of documents, particularly but not exclusively for data spaces that have low reflectivity, i.e., for a point x_i described by one or more numbers, the data space does not contain very many permutations of the numbers. For each document to be searched, each query number is matched with one and only one document number preferably using a bipartite graph or heuristic rule such that a distance function is minimized. The distance function can, but not must, take into account attribute names and unit names. A limiting algorithm can be used to limit the number of documents that must be searched.

Claims

1. A computer-implemented method for searching documents comprising:

receiving a query having at least one query number q_i but not necessarily specifying an attribute name or unit for the query number the query number q_i being only an approximation of a desired attribute numeric value;

for at least one document, matching each number q_i with a document number n_m, each document number being a number contained in the document, such that a distance score is minimized; and

based on the distance scores, returning at least one document in response to the query wherein the documents are selected from a set of documents, and the method further comprises limiting the number of documents in the set that are processed in the matching act using at least one lower bound on at least one distance score.

2. The method of claim 1, wherein the documents are accessible on the Internet.

3. The method of claim 1, wherein the distance score is derived from a distance function.

4. The method of claim 3, wherein the distance function requires, as input, only numbers.

5. The method of claim 3, wherein the distance functions accounts for at least one attribute name associated with at least one query number.

6. The method of claim 3, wherein the distance function accounts for at least one unit name associated with at least one number.

7. The method of claim 5, wherein the distance function accounts for at least one unit name associated with at least one number.

8. The method of claim 3, wherein each document number matches at most one query number, and the distance score of a first document is infinity if more query numbers exist than document numbers in the first document.

9. The method of claim 1, comprising processing the documents in the set of documents to support database access and index access.

10. The method of claim 9, wherein the index access supports hint access.

11. The method of claim 9, comprising creating, for each query number q_i, an ordered list L_i of document numbers n, each list being ordered in ascending order of distance scores.

12. The method of claim 11, comprising performing round-robin access on the lists L_i and, when a document D is detected in a list, performing a database access for the document and undertaking the matching and returning acts.

13. The method of claim 12, comprising halting the act of performing a round-robin access when a number of documents have been detected having distance scores less than a threshold value τ

.

43. The method of claim 8, wherein at least the act of matching is undertaken using at least one bipartite graph.

14. A computer programmed with instructions for retrieving numbers from a corpus of documents, the instructions comprising:

in response to a numeric query containing at least one numeric query string not necessarily associated with an attribute name or unit name, accessing at least some documents in the corpus the string being only an approximation of a desired attribute numeric value;

comparing each numeric query string with one or more document strings;

associating each numeric query string with one and only one document string to optimize at least one distance function; and

returning at least a portion of at least one document based on the associating instruction wherein the documents are selected from a set of documents, and the computer further comprises instructions for limiting the number of documents in the set that are processed using lower bounds on the distance scores.

15. The computer of claim 14, wherein the documents are accessible on the Internet.

16. The computer of claim 15, wherein at least one distance score is derived from the distance function.

17. The computer of claim 16, wherein the distance function requires, as input, only numbers.

18. The computer of claim 16, wherein the distance functions accounts for at least one attribute name associated with at least one query number.

19. The computer of claim 16, wherein the distance function accounts for at least one unit name associated with at least one number.

20. The computer of claim 18, wherein the distance function accounts for at least one unit name associated with at least one number.

21. The computer of claim 16, wherein the comparing and associating instructions use at least one bipartite graph.

22. The computer of claim 14, wherein the instructions comprise processing the documents in the set of documents to support database access and index access.

23. The computer of claim 22, wherein the index access supports hint access.

24. The computer of claim 22, wherein the instructions comprise creating, for each query number q_i, an ordered list L_i of document numbers n, each list being ordered in ascending order of distance scores.

25. The computer of claim 24, wherein the instructions comprise performing round-robin access on the lists L_i and, when a document D is detected in a list, performing a database access for the document and invoking the comparing and associating instructions.

26. The computer of claim 25, wherein the instructions include halting the round-robin access when a number of documents have been detected having distance scores less than a threshold value τ

.

27. A computer program device having computer readable code thereon for searching a set of documents, the code comprising:

means for receiving a user query including at least one query number corresponding to respective desired attribute numeric values, the query not necessarily including attribute names or unit names, the query including at least one numeric value that is only an approximation of a desired attribute numeric value; and

means for returning documents with values close to the query number, wing only the query number wherein the means for returning includes means for returning a ranked list of documents, each document having a value associated with each query number, such that a distance function between the query numbers and corresponding values is minimized.

28. The computer program device of claim 27, wherein the means for returning uses bipartite graph matching.

29. The computer program device of claim 27, wherein the means for returning uses at least one heuristic rule.

30. The computer program device of claim 27, wherein the means for returning includes means for building a sorted index over all values in all documents to limit a set of matches between the document values and the query numbers.

31. A computer for searching a set of unstructured and/or semi-structured and/or structured documents, comprising:

instructions for receiving a user query consisting of a set of numbers corresponding to desired attribute values and being only approximations of desired attribute numeric values, the query also consisting of respective attribute names of the numbers; and

instructions for returning documents containing document values close to the set of numbers in the query using the query numbers and attribute names wherein the means for returning includes means for returning a ranked list of documents, each document having a value associated with each query number, such that a distance function between the query numbers and corresponding values is minimized.

32. The computer of claim 31, wherein the instructions for returning use bipartite graph matching.

33. The computer of claim 31, wherein the instructions for returning use at least one heuristic rule.

34. The computer of claim 31, wherein the instructions for returning include instructions for building a sorted index over all values in all documents to limit a set of matches between the document values and the query numbers.

35. A computer-implemented method for searching a set of documents in response to a user query including a set of query numbers corresponding to desired attribute values together with units of the values the query numbers being only approximations of desired attribute numeric values, comprising:

returning documents with values approximating the set of query numbers, using the query numbers and units wherein the act of returning Includes returning a ranked list of documents, each document having at least one value associated with each query number, such that a distance function between the query numbers and corresponding values is minimized.

36. The method of claim 35, wherein the act of returning uses bipartite graph matching.

37. The method of claim 35, wherein the act of returning uses at least one heuristic rule.

38. The method of claim 35, wherein the act of returning includes building a sorted index over all values in all documents to limit a set of matches between the document values and the query numbers.

39. A system for searching a set of documents, comprising:

means for receiving a query comprising at least one query number, at least one unit of the query number, and at least one attribute name associated with the query number the query number being an approximation of a desired attribute numeric value;

means for returning documents with at least one document value approximating but not necessarily equalling the query number, using the query number, the attribute name, and the unit wherein the means for returning includes means for returning a ranked list of documents, each document having a value associated with each query number, such that a distance function between the query numbers and corresponding values is minimized.

40. The system of claim 39, wherein the means for returning uses bipartite graph matching.

41. The system of claim 39, wherein the means for returning uses at least one heuristic rule.

42. The system of claim 39, wherein the means for returning includes means for building a sorted index over all values in all documents to limit a set of matches between the document values and the query numbers.