Method for proximity searching with range testing and range adjustment

• US 5,499,360 A
• Filed: 02/28/1994
• Issued: 03/12/1996
• Est. Priority Date: 02/28/1994
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Corporation Of America (Panasonic Holdings Corporation)
• Original Assignee: Panasonic Technologies, Inc. (Panasonic Holdings Corporation)
• Inventors: Mehrotra, Sharad, Aref, Walid, Johnson, Stephen, Barbara, Daniel
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/203,329
• Time in Patent Office: 743 Days
• Field of Search: 395/600
• US Class Current: 1/1
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method of searching a database having a plurality of objects is provided. Each object includes attributes and, for each attribute, a number of values. A query specifies two attributes and a maximum distance. A respective set of ranges is established for each object that has a value for the first attribute. Each set includes a range for each value of the first attribute. Each range is defined by minimum and maximum location values. A test range is established for one of the ranges. The test range has values equal to the minimum and maximum values of one of the ranges. The test range is adjusted, if necessary, so that it includes one of the values of the second attribute of the corresponding object. The test range is added to a group of ranges corresponding to the object if the minimum and maximum test values do not differ from one another by more than the maximum distance. The steps of (1) establishing a test range, (2) adjusting the test range and (3) adding the test range to the group are repeated for each range in the set of ranges corresponding to the one object. Steps (1) to (3) are repeated for each value of the second attribute of each respective object for which a set of ranges is established. Each object for which the group of ranges includes at least one range is identified as being found by the searching.

Claims

1. A method of searching for keywords in a database having a plurality of documents, each including a subset of a plurality of keywords and, for each keyword in the subset, a number of values stored in a storage medium, each value indicating a location of the keyword within the document, the method comprising the steps of:

(a) forming a query specifying first and second keywords and a maximum distance defining a relative range of keyword locations that satisfy the query;

(b) establishing a plurality of ranges, comprising a set of ranges and a group of ranges for each respective document in which the first keyword appears at least once, each set of ranges including a range for each respective location of the first keyword, each range being defined by respective minimum and maximum location values;

(c) repeating, for each respective value of the second keyword in each respective document for which a set of ranges is established, the step of;

(1) repeating, for each one of the set of ranges corresponding to the respective document, the steps of;

(i) establishing a test range having minimum and maximum test values equal to the respective minimum and maximum values of the one range,

(ii) adjusting the test range, so that the respective value is included in the test range, if the respective value is not between the minimum and maximum test values, and

(iii) adding the test range to the group of ranges corresponding to the respective document if the minimum and maximum test values do not differ from one another by more than the maximum distance after step (ii); and

(d) identifying each document for which the respective group of ranges includes at least one range as being found by the searching.

2. A method of searching a database having a plurality of objects, each including a subset of a plurality of attributes and, for each attribute in the subset, a number of values stored in a storage medium, the method comprising the steps of:

(a) forming a query specifying first and second attributes and a maximum difference value defining a relative range of attribute values that satisfy the query;

(b) establishing a plurality of ranges, comprising a set of ranges and a group of ranges for each respective object having at least one value for the first attribute, each set of ranges including a range for each respective value of the first attribute, each range being defined by respective minimum and maximum location values;

(c) repeating, for each respective value of the second attribute of each respective object for which a set of ranges is established, the step of;

(1) repeating, for each one of the set of ranges corresponding to the respective object, the steps of;

(i) establishing a test range having minimum and maximum test values equal to the respective minimum and maximum values of the one range,

(ii) adjusting the test range, so that the respective value is included in the test range, if the respective value is not between the minimum and maximum test values, and

(iii) adding the test range to the group of ranges corresponding to the respective object if the minimum and maximum test values do not differ from one another by more than the maximum difference value after step (ii); and

(d) identifying each object for which the respective group of ranges includes at least one range as being found by the searching.

3. A method according to claim 2, wherein the plurality of attributes includes N attributes designated first through N^th, where N is an integer, further comprising, between steps (c) and (d) the step of:

(2) repeating, for each respective attribute from the third attribute through the N^th attribute of each respective object for which the group of ranges includes at least one range, the steps of;

(A) substituting the group of ranges for the set of ranges,

(B) clearing the group of ranges, and,

(C) repeating step (c) (1), for the respective attribute.

4. A method according to claim 2, wherein the plurality of attributes includes three attributes, further comprising, between steps (c) and (d) the steps of:

(2) substituting the group of ranges for the set of ranges,

(3) clearing the group of ranges, and,

(4) repeating step (c) (1), for each respective value of the third attribute.

5. A method according to claim 2, wherein the step of adjusting the one range comprises the steps of:

(i) setting the minimum value equal to the respective value of the second attribute if the value of the second attribute is less than the minimum value and greater than the maximum value minus the maximum difference value, and

(ii) setting the maximum value equal to the respective value of the second attribute if the value of the second attribute is greater than the maximum value and less than the minimum value plus the maximum difference value.

6. A method according to claim 2, wherein:

each respective object is a respectively different document,

each respective attribute is a respective keyword, and

each attribute has a value which indicates a position at which the respective keyword is located within the respective document.

7. A method according to claim 6, wherein each object that satisfies the query includes a respective string of contiguous words, the string including all of the keywords in the plurality of attributes, none of the keywords in the string being separated from any other keyword in the string by a number of words greater than the maximum difference value.

8. A method of searching a database having a plurality of objects, each including a subset of a plurality of attributes and, for each attribute in the subset, a number of values stored in a storage medium, the method comprising the steps of:

(a) forming a query specifying first and second attributes and a maximum difference value defining a relative range of attribute values that satisfy the query;

(b) establishing a plurality of ranges, comprising a set of ranges and a group of ranges for each respective object having at least one value for the first attribute, each set of ranges including a range for each respective value of the first attribute, each range being defined by respective minimum and maximum location values;

(c) repeating, for each respective value of the second attribute of each respective object for which a set of ranges is established, the step of;

(1) repeating, for each one range of the set of ranges corresponding to the respective object, the steps of;

(i) determining whether the respective value is between the respective minimum and maximum values of the one range,

(ii) determining whether the respective value differs from either one of the minimum and maximum values of the one range by a number greater than the maximum difference value, if the respective value is not between the respective minimum and maximum values,

(iii) establishing a test range such that the respective value is included in the test range, if the respective value is not between the minimum and maximum values of the one range and the respective values does not differ from either one of the minimum and maximum values of the one range by a number greater than the maximum difference value, and

(iv) adding the test range to the group of ranges corresponding to the respective object; and

(d) identifying each object for which the respective group of ranges includes at least one range as being found by the searching.

9. A method according to claim 8, wherein step (c) (1) (ii) includes:

(A) setting the minimum value of the test range equal to the respective value of the second attribute, if the value of the second attribute is less than the minimum value and greater than the maximum value minus the maximum difference value, and

(B) setting the maximum value of the test range equal to the respective value of the second attribute if the value of the second attribute is greater than the maximum value and less than the minimum value plus the maximum difference value.

10. A method of searching for objects in a database having a plurality of objects, each object having a plurality of attributes, each attribute having D dimensions, where D is an integer greater than one, and having a non-negative number of vector values that are stored in a storage medium, each vector value comprising D coordinates, the method comprising the steps of:

(a) forming a query specifying at least two of the plurality of attributes and a maximum difference value;

(b) establishing a plurality of ranges, comprising a set of ranges and a group of ranges for each respective object having at least one vector value for a first one of the plurality of attributes, each set of ranges including a respective range for each respective vector value of the first attribute, each respective range comprising a pair of values for each respective one of the D dimensions, each dimension being ordinately numbered first through D^th, each pair consisting of minimum and maximum values for the attribute in the respective dimension;

(c) repeating, for each respective vector value of a second one of the plurality of attributes, the step of;

(1) repeating, for each respective one of the set of ranges belonging to the respective object to which the respective vector value belongs, the steps of;

(i) establishing a respective test range having values equal to the minimum and maximum values of the range,

(ii) determining whether an i^th coordinate of the respective vector value is between the respective i^th minimum and i^th maximum values of the one range, where i is an integer between one and D,

(iii) adjusting an i^th minimum value and an i^th maximum value of the test range, such that the i^th coordinate of the respective vector value is included in the test range and the i^th coordinate of the respective vector value does not differ from either one of the i^th minimum and i^th maximum values of the one range by a number greater than the maximum difference value,

(iv) marking the test range if the i^th coordinate of the respective vector value differs from either one of the i^th minimum and i^th maximum values of the one range by a number greater than the maximum difference value,

(v) repeating steps (ii) through (iv) for each of the D dimensions;

(2) adding the test range to the respective group of ranges if the test range is not marked and

(d) identifying each respective object for which the respective group includes at least one range as a member of a subset of the plurality of objects, whereby all of the objects that satisfy the query are included in the subset.

11. A method according to claim 10, wherein said method further comprises the steps of:

(e) checking, for one of the objects in the subset, whether a combination of vector values exists, such that the combination includes a respective vector value for each respective attribute, and none of the vector values in the combination differs from any other vector value in the combination by a difference greater than the maximum difference value, the checking being performed after step (e); and

(f) identifying the one object as satisfying the query if the combination exists.

12. A method according to claim 11, further comprising the step of repeating steps (e) and (f) for each respective object, thereby determining all of the objects that satisfy the query.

13. A method according to claim 10, wherein the number D has a value of 2, each respective object is a respectively different building, each respective attribute is a type of a respective one of the buildings, and each respective vector value represents the location of the one building in two dimensions, wherein each building is at substantially the same altitude as every other building.

14. A method according to claim 10, wherein the number D has a value of 3, each respective object is a respectively different building, each respective attribute is a type of a respective one of the buildings, and each respective vector value represents the location of the one building in three dimensions.

15. A method according to claim 10, wherein the number D has a value of 3, each respective object is a respectively different person, each attribute is a respectively different part of the body of one of the persons, and each respective vector value represents the location of a respective part within the body of the one person.

16. A method according to claim 10, wherein step (c) (1) (iii) includes repeating, for each dimension from the first dimension to the D^th dimension, the steps of:

(A) setting the i^th maximum value of the test range equal to a minimum value selected from the group consisting of the i^th maximum value and the sum of the i^th coordinate of the vector value plus the maximum difference value, if the i^th coordinate of the vector value is less than the i^th minimum value plus the maximum difference value, and

(B) setting the i^th minimum value of the test range equal to a maximum value selected from the group consisting of the i^th minimum value and the i^th coordinate of the vector value minus the maximum difference value, if the i^th coordinate of the vector value is not less than the i^th minimum value plus the maximum difference value.