Patent US6282540B1 successfully refreshed from Google Patents.
US6282540B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for efficient proximity searching
Assignee: VICINTY Corp
•
Filing: 1999-02-26
•
Granted: 2001-08-28
•
Expires: 2019-02-26
Abstract
Abstract A method and apparatus to improve proximity searching. An area containing a population of points is subdivided into a plurality of regions at index time. The population of points and the regions are textual keyed. Attribute(s) are determined corresponding to at least a subset of points from the population. Each attribute or pair of attributes is assigned a bitmap, the bitmap having entries corresponding to the regions in the area. Each entry of the bitmap corresponding to a region having at least one point to which the attribute applies is set. The attribute is then stored in an index with its bitmap. At query time, scanning the bitmap for set bits identifies all potentially relevant regions. These regions may be searched in increasing distance from a spatial origin without incurring the cost of searching fruitless regions.
Inventors
- 👤 Charles Goldensher
- 👤 Martin W. Himmelstein
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 18:16
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/50; G06F16/58; G06F16/583; G06F16/5854; G06F16/20; G06F16/29; Y; Y10; Y10S; Y10S707/00; Y10S707/912; Y10S707/918; Y10S707/919; Y10S707/921; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99935; Y10S707/99936
Claims Analysis
Total Claims: 40
Claim 1
Independent Claim
89 words
A method for proximity searching comprising: receiving a spatial origin from a user, the spatial origin identifying a geographic location; receiving at least one non-spatial attribute from the user; selecting a bitmap corresponding to at least one non-spatial attribute from a plurality of bitmaps, each of the plurality of bitmaps being associated with one or more non-spatial attributes; and searching at least one quad, within a distance of the spatial origin, having at least one point to which at least one non-spatial attribute applies as reflected in the bitmap.
Claim 2
Independent Claim
89 words
A method for proximity searching comprising: receiving a spatial origin from a user, the spatial origin identifying a geographic location; receiving at least one non-spatial attribute from the user; selecting a bitmap corresponding to at least one non-spatial attribute from a plurality of bitmaps, each of the plurality of bitmaps being associated with one or more non-spatial attributes; and searching at least one quad, within a distance of the spatial origin, having at least one point to which at least one non-spatial attribute applies as reflected in the bitmap.
Claim 3
Dependent Claim
16 words
The method of claim 1 wherein the at least one non-spatial attribute comprises an attribute pair.
Claim 4
Dependent Claim
12 words
The method of claim 1 wherein the spatial origin comprises an address.
Claim 5
Dependent Claim
70 words
The method of claim 1 further comprising: receiving three or more non-spatial attributes from the user; determining which sets of attribute pairs to use to retrieve intermediate bitmaps; retrieving the intermediate bitmaps; combining the intermediate bitmaps into a combined bitmap; and searching at least one quad, within a distance from the spatial origin, having at least one point to which the non-spatial attributes apply as reflected in the combined bitmap.
Claim 6
Dependent Claim
23 words
The method of claim 1 further comprising: returning a distance ordered list of points to which the at least one non-spatial attribute applies.
Claim 7
Dependent Claim
55 words
The method of claim 1 wherein the at least one non-spatial attribute comprises at least three attributes and further comprising: forming a plurality of key word pairs; determining which of the plurality of key word pairs is a lowest frequency key word pair; and scanning a bitmap corresponding to the lowest frequency key word pair.
Claim 8
Independent Claim
97 words
An apparatus for proximity searching comprising: means for receiving a spatial origin from a user, the spatial origin identifying a geographic location; means for receiving at least one non-spatial attribute from the user; means for selecting a bitmap corresponding to at least one non-spatial attribute from a plurality of bitmaps, each of the plurality of bitmaps being associated with one or more non-spatial attributes; and means for searching at least one quad within a distance of the spatial origin, having at least one point to which at least one non-spatial attribute applies as reflected in the bitmap.
Claim 9
Independent Claim
97 words
An apparatus for proximity searching comprising: means for receiving a spatial origin from a user, the spatial origin identifying a geographic location; means for receiving at least one non-spatial attribute from the user; means for selecting a bitmap corresponding to at least one non-spatial attribute from a plurality of bitmaps, each of the plurality of bitmaps being associated with one or more non-spatial attributes; and means for searching at least one quad within a distance of the spatial origin, having at least one point to which at least one non-spatial attribute applies as reflected in the bitmap.
Claim 10
Dependent Claim
17 words
The apparatus defined in claim 7 wherein the at least one non-spatial attribute comprises an attribute pair.
Claim 11
Dependent Claim
13 words
The apparatus defined in claim 7 wherein the spatial origin comprises an address.
Claim 12
Dependent Claim
81 words
The apparatus defined in claim 7 further comprising: means for receiving three or more non-spatial attributes from the user; means for determining which sets of attribute pairs to use to retrieve intermediate bitmaps; means for retrieving the intermediate bitmaps; means for combining the intermediate bitmaps into a combined bitmap; and means for searching at least one quad, within a distance from the spatial origin, having at least one point to which the non-spatial attributes apply as reflected in the combined bitmap.
Claim 13
Dependent Claim
25 words
The apparatus defined in claim 7 further comprising means for returning a distance ordered list of points to which at least one non-spatial attribute applies.
Claim 14
Dependent Claim
61 words
The apparatus defined in claim 7 wherein the at least one non-spatial attribute comprises at least three attributes and further comprising: means for forming a plurality of key word pairs; means for determining which of the plurality key word pairs is a lowest frequency key word pair; and means for scanning a bitmap corresponding to the lowest frequency key word pair.
Claim 15
Dependent Claim
104 words
A recordable storage medium with executable instructions stored thereon, which, when executed by a processing device, cause the processing device to: receive a spatial origin from a user, the spatial origin identifying a geographic location; receive at least one non-spatial attribute from the user; select a bitmap corresponding to at least one non-spatial attribute from a plurality of bitmaps, each of the plurality of bitmaps being associated with one or more non-spatial attributes; and search at least one quad, within a distance of the spatial origin, having at least one point to which at least one non-spatial attribute applies as reflected in the bitmap.
Claim 16
Dependent Claim
104 words
A recordable storage medium with executable instructions stored thereon, which, when executed by a processing device, cause the processing device to: receive a spatial origin from a user, the spatial origin identifying a geographic location; receive at least one non-spatial attribute from the user; select a bitmap corresponding to at least one non-spatial attribute from a plurality of bitmaps, each of the plurality of bitmaps being associated with one or more non-spatial attributes; and search at least one quad, within a distance of the spatial origin, having at least one point to which at least one non-spatial attribute applies as reflected in the bitmap.
Claim 17
Dependent Claim
17 words
The recordable medium defined in claim 13 wherein the least one non-spatial attribute comprises an attribute pair.
Claim 18
Dependent Claim
14 words
The recordable medium defined in claim 13 wherein the spatial origin comprises an address.
Claim 19
Dependent Claim
84 words
The recordable medium defined in claim 13 wherein the instructions, when executed by a processing device, further cause the processing device to: receive three or more non-spatial attributes from the user; determine which sets of attribute pairs to use to retrieve intermediate bitmaps; retrieve the intermediate bitmaps; combine the intermediate bitmaps into a combined bitmap; and search at least one quad, within a distance from the spatial origin, having at least one point to which the attributes apply as reflected in the combined bitmap.
Claim 20
Dependent Claim
37 words
The recordable medium defined in claim 13 wherein the instructions, when executed by a processing device, further cause the processing device to: return a distance ordered list of points to which at least one non-spatial attribute applies.
Claim 21
Dependent Claim
69 words
The recordable medium defined in claim 13 wherein the at least one non-spatial attribute comprises at least three attributes and wherein the instructions, when executed by a processing device, further cause the processing device to: form a plurality of key word pairs; determine which of the plurality key word pairs is a lowest frequency key word pair; and scan a bitmap corresponding to the lowest frequency key word pair.
Claim 22
Independent Claim
66 words
A method of indexing to facilitate proximity searching, the method comprising: spatial keying a relevant population of points in an area; generating a set of non-spatial attributes; and generating a plurality of bitmaps to facilitate proximity searching, each of the plurality of bitmaps associating each non-spatial attribute with a subset of spatial keys corresponding to a subset of points to which said each non-spatial attribute applies.
Claim 23
Independent Claim
66 words
A method of indexing to facilitate proximity searching, the method comprising: spatial keying a relevant population of points in an area; generating a set of non-spatial attributes; and generating a plurality of bitmaps to facilitate proximity searching, each of the plurality of bitmaps associating each non-spatial attribute with a subset of spatial keys corresponding to a subset of points to which said each non-spatial attribute applies.
Claim 24
Dependent Claim
36 words
The method of claim 19 wherein associating each non-spatial attribute comprises: dividing the area into a plurality of regions; and generating a bitmap indicating which regions contain a point to which said each non-spatial attribute applies.
Claim 25
Dependent Claim
47 words
The method of claim 20 wherein generating the bitmap comprises: creating a bit string with each bit corresponding to a distinct region; and setting one bit in the bit string if a region corresponding to the one bit contains a point to which the non-spatial attribute applies.
Claim 26
Dependent Claim
11 words
The method of claim 21 further comprising: compressing the bitmap storage.
Claim 27
Dependent Claim
21 words
The method of claim 19 further comprising: maintaining a count of a frequency of points to which a non-spatial attribute applies.
Claim 28
Dependent Claim
11 words
The method of claim 19 wherein the spatial keys are quadkeys.
Claim 29
Independent Claim
84 words
A system comprising: a textual key generator to generate a textual key corresponding to each point of a relevant population of points in a database; an attribute identifier to identify one or more non-spatial attributes corresponding to individual points of the relevant population of points; and a bitmap generator to generate a bitmap for the one or more non-spatial attributes identifying a subset of regions within an area containing a point corresponding to the one or more non-spatial attributes, the bitmap facilitating proximity searching.
Claim 30
Independent Claim
84 words
A system comprising: a textual key generator to generate a textual key corresponding to each point of a relevant population of points in a database; an attribute identifier to identify one or more non-spatial attributes corresponding to individual points of the relevant population of points; and a bitmap generator to generate a bitmap for the one or more non-spatial attributes identifying a subset of regions within an area containing a point corresponding to the one or more non-spatial attributes, the bitmap facilitating proximity searching.
Claim 31
Dependent Claim
22 words
The system of claim 25 further comprising: a database storing a set of non-spatial attributes and bitmaps for the set of attributes.
Claim 32
Dependent Claim
19 words
The system of claim 25 further comprising a compression engine coupled to compress bitmap, generated by the bitmap generator.
Claim 33
Independent Claim
67 words
A method comprising: receiving a first non-spatial attribute and a spatial origin from a user, the spatial origin identifying a geographic location; selecting a bitmap for the non-spatial attribute from a plurality of bitmaps, each of the plurality of bitmaps being associated with a particular non-spatial attribute; and identifying from the bitmap a subset of regions containing at least one point to which the non-spatial attribute applies.
Claim 34
Independent Claim
67 words
A method comprising: receiving a first non-spatial attribute and a spatial origin from a user, the spatial origin identifying a geographic location; selecting a bitmap for the non-spatial attribute from a plurality of bitmaps, each of the plurality of bitmaps being associated with a particular non-spatial attribute; and identifying from the bitmap a subset of regions containing at least one point to which the non-spatial attribute applies.
Claim 35
Dependent Claim
38 words
The method of claim 28 further comprising: searching a subset of the subset of regions for points to which the non-spatial attribute applies; and returning to the user a list of points distance ordered from the spatial origin.
Claim 36
Independent Claim
71 words
An apparatus comprising: means for receiving a first non-spatial attribute and a spatial origin from a user, the spatial origin identifying a geographic location; means for selecting a bitmap for the attribute from a plurality of bitmaps, each of the plurality of bitmaps being associated with a particular non-spatial attribute; and means identifying from the bitmap a subset of regions containing at least one point to which the non-spatial attribute applies.
Claim 37
Independent Claim
71 words
An apparatus comprising: means for receiving a first non-spatial attribute and a spatial origin from a user, the spatial origin identifying a geographic location; means for selecting a bitmap for the attribute from a plurality of bitmaps, each of the plurality of bitmaps being associated with a particular non-spatial attribute; and means identifying from the bitmap a subset of regions containing at least one point to which the non-spatial attribute applies.
Claim 38
Dependent Claim
40 words
The apparatus of claim 30 further comprising: means searching a subset of the subset of regions for points to which the non-spatial attribute applies; and means returning to the user a list of points distance ordered from the spatial origin.
Claim 39
Independent Claim
80 words
An apparatus comprising: a query processor to receive a first non-spatial attribute and a spatial origin from a user, the spatial origin identifying a geographic location; and a database to store a plurality of bitmaps associated with a particular non-spatial attribute, the query processor to select a bitmap for the first non-spatial attribute from the plurality of bitmaps and to identify from the bitmap a subset of regions containing at least one point to which the first non-spatial attribute applies.
Claim 40
Independent Claim
80 words
An apparatus comprising: a query processor to receive a first non-spatial attribute and a spatial origin from a user, the spatial origin identifying a geographic location; and a database to store a plurality of bitmaps associated with a particular non-spatial attribute, the query processor to select a bitmap for the first non-spatial attribute from the plurality of bitmaps and to identify from the bitmap a subset of regions containing at least one point to which the first non-spatial attribute applies.
References Cited (Backward Citations)
US4839853A
Cited
US5748805A
Cited
US5832494A
Cited
US5619709A
Cited
US5537491A
Cited
US5504889A
Cited
US5983220A
Cited
US5710915A
Cited
US5864855A
Cited
US5761652A
Cited
US5913205A
Cited
US5915250A
Cited
US5940825A
Cited
US6047280A
Cited
US5974412A
Cited
US6021406A
Cited
US6081803A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-08-27 | 2005-02-26 | 2005-08-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-08-27 | 2009-02-26 | 2009-08-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-08-27 | 2013-02-26 | 2013-08-28 | $7700.00 | Window Closed / Lapsed |