Method and apparatus of expanding web searching capabilities

• US 6,701,307 B2
• Filed: 10/28/1998
• Issued: 03/02/2004
• Est. Priority Date: 10/28/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Halstead, Gerald F., Goldensher, Charles, Himmelstein, Martin W., Aspinwall, Dwight
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US09/182,746
• Publication Number:
  US 20010011270A1
• Time in Patent Office: 1,952 Days
• Field of Search: 707/3-5, 707/9-10, 707/100-104, 707/104, 358/400, 701/200, 701/206-208, 382/190, 382/201
• US Class Current: 707/743
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: Y10S 707/921 Spatial
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method and apparatus for improving searching capability on a Web. At index time, a Web page is spidered and the text and metatags returned to a processor. The processor extracts spatial information from the text and metatags. A geocode is generated for the spatial information. The geocode is then indexed along with the remaining contents of the page. A subsequent query during query time can search for entries based on proximity to a known location using the indexed geocode.

Claims

1. A method for generating searchable information comprising:

scanning a document;

determining whether any portion of the document being scanned contains information indicative of a spatial datum;

finding a document portion that contains the information indicative of the spatial datum;

examining data surrounding the document portion to locate the spatial datum in the document;

extracting to spatial datum from the document;

geocoding the spatial datum by generating a point key from a latitude and longitude, wherein generating the point key comprises;

interleaving bits of the latitude with bits of the longitude; and

converting adjacent pairs of bits to a number, the point key comprising an N-bit binary number that corresponds with the spatial datum; and

generating area keys, each area key comprising an area greater than an area defined by the point key but which includes the area defined by the point key.

2. The method defined in claim 1 further comprising indexing the geocode for the spatial datum.

3. The method defined in claim 1 wherein the document comprises a Web page.

4. The method defined in claim 1 wherein the spatial datum comprises information indicative of an address.

5. The method defined in claim 4 wherein the address comprises a postal address.

6. The method defined in claim 4 wherein the information comprises a postal code.

7. The method defined in claim 4 wherein the information comprises a telephone number.

8. The method defined in claim 1 further comprising spidering the document to extract the spatial datum.

9. The method of claim 1 further comprising extracting the spatial datum by identifying a tag located in the document indicating the presence of the spatial datum.

10. An apparatus for generating searchable information comprising:

means for scanning a document;

means for determining whether any portion of the document being scanned contains information indicative of a spatial datum;

means for finding a document portion containing the information indicative of the spatial datum;

means for examining data surrounding the document portion to locate the spatial datum in the document;

means for extracting the spatial datum from the document;

means for geocoding the spatial datum by generating a point key from a latitude and longitude, wherein generating the point key comprises;

interleaving bits of the latitude with bits of the longitude; and

converting adjacent pairs of bits to a number, the point key comprising an N-bit binary number that corresponds with the spatial datum; and

means for generating a set of area keys to perform geographical searches, each area key comprising an area greater than an area defined by the point key but which includes the area defined by the point key.

11. The apparatus defined in claim 10 further comprising means for recognizing the spatial datum.

12. The apparatus defined in claim 10 wherein the set of area keys are generated at query time.

13. The apparatus defined in claim 10 further comprising means for indexing the geocode for the spatial datum.

14. The apparatus defined in claim 10 wherein the document comprises a Web page.

15. The apparatus defined in claim 10 wherein the spatial datum comprises information indicative of an address.

16. The apparatus defined in claim 15 wherein the address comprises a postal address.

17. The apparatus defined in claim 15 wherein the information comprises a postal code.

18. The apparatus defined in claim 15 wherein the information comprises a telephone number.

19. The apparatus defined in claim 10 further comprising spidering the document to extract the spatial datum.

20. The apparatus defined in claim 10 further comprising extracting the spatial datum by identifying a tag located in the document indicating the presence of the spatial datum.

21. A method for facilitating a search comprising:

receiving a user request for a proximity search of one or more objects, the user request including a spatial location and a distance from the spatial location, wherein the spatial location and the distance from the spatial location correspond to a desired search area;

in response to the user request, generating a point key of the spatial location;

defining the desired search area by covering an area around the point key from a latitude and longitude, wherein generating the point key comprises;

interleaving bits of the latitude with bits of the longitude; and

converting adjacent pairs of bits to a number, the point key comprising an N-bit binary number that corresponds with the spatial location based on the distance from the spatial location;

determining a set of area keys intersecting the desired search area, each area key comprising an area greater than an area defined by the point key but which includes the area defined by the point key; and

searching a database for one or more records that have keys matching any one of the set of area keys.

22. The method defined in claim 21 wherein the information indicative of a spatial location comprises an address.

23. The method defined in claim) 21 wherein the information indicative of a spatial location comprises a latitude and a longitude.

24. The method defined in claim 21 wherein information indicative of a spatial location comprises a specified location on a user specified region of a map.

25. The method defined in claim 21 wherein receiving the user request comprises receiving a selection from a pop-up menu.

26. The method defined in claim 21 wherein the predetermined region comprises a circle having a radius of the distance.

27. The method of claim 21 further comprising returning identifiers for a set of documents satisfying a criterion and containing an address within the desired search area.

28. The method defined in claim 27 wherein the identifiers comprise resource locators.

29. The method defined in claim 28 wherein the resource locators comprise URLs.

30. The method defined in claim 27 wherein the documents comprise Web pages.

31. The method defined in claim 21 further comprising:

searching the database with the set of area keys to locate records in the database that each include a matching point key; and

identifying a matching record as one in which at least one of the area keys match a stored area key.

32. The method defined in claim 21 further comprising:

searching the database with the set of area keys and a predetermined criteria to locate records in the database; and

identifying a matching record as one in which at least one of the area keys partially matches a point key for the record and also matches the predetermined criteria.

33. The method defined in claim 32 wherein the predetermined criteria comprises one or mare keywords.

34. The method defined in claim 32 wherein the predetermined criteria comprises spatial criteria.

35. A system comprising:

an address extractor to scan an arbitrary document, to determine whether any portion of the document being scanned contains information indicative of spatial data, to find a document portion that contains the information indicative of the spatial data, to examine data surrounding the document portion to locate the spatial data in the document, and to automatically extract the spatial data from the arbitrary document;

a point key generator to generate a point key from a latitude and longitude, the point key comprising an N-bit binary number corresponding to the spatial data in response to extraction of the spatial data, wherein the point key generator generates the point key by interleaving bits of the latitude with bits of the longitude and converting adjacent pairs of bits to a number; and

an area key producer to create a set of area keys responsive to a query specifying an origin and a distance, each area key comprising an area greater than an area defined by a respective point key but which includes the area defined by a respective point key.

36. The system of claim 35 further comprising a database storing an index of keys corresponding to an arbitrarily large set of spatial data.

37. The system of claim 35 further comprising a processor to search the index based on the set of area keys and a user supplied criterion.

38. A method of spatially locating a document comprising:

receiving a user request for a proximity search of one or more objects, the user request including information indicative of an address of a spatial location and a selected distance from the spatial location, wherein the spatial location and the selected distance from the spatial location correspond to a desired search area;

in response to the user request, generating a first key indicative of the spatial location from a latitude and longitude, the first key comprising an N-bit binary number corresponding to the spatial location, wherein generating the first key comprises;

interleaving bits of the latitude with bits of the longitude; and

converting adjacent pairs of bits to a number;

generating a second key intersecting the desired search area around the first key corresponding to the selected distance from the spatial location, the second key comprising an area greater than an area defined by the first key but which includes the area defined by the first key; and

performing a text search of a plurality of records using the second key.

39. The method defined in claim 38 wherein the size of the second key is determined based on the selected distance from the spatial location.