US 5,499,360 A · Method for proximity searching with range testing and range adjustment

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.

Claims16

Dependent claims

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.

6 more elements

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.

6 more elements

(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.

7 more elements

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.sup.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.sup.th coordinate of the respective vector value is between the respective i.sup.th minimum and i.sup.th maximum values of the one range, where i is an integer between one and D,
(iii) adjusting an i.sup.th minimum value and an i.sup.th maximum value of the test range, such that the i.sup.th coordinate of the respective vector value is included in the test range and the i.sup.th coordinate of the respective vector value does not differ from either one of the i.sup.th minimum and i.sup.th maximum values of the one range by a number greater than the maximum difference value,
(iv) marking the test range if the i.sup.th coordinate of the respective vector value differs from either one of the i.sup.th minimum and i.sup.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.

8 more elements

Dependencies are inferred from the claim text.

Method for proximity searching with range testing and range adjustment

Life of this patent

Method for proximity searching with range testing and range adjustment

Life of this patent

Abstract

Claims16