Spatially coding and displaying information

• US 20020078035A1
• Filed: 02/22/2001
• Published: 06/20/2002
• Est. Priority Date: 02/22/2000
• Status: Active Grant

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Metacarta, Inc.
• Inventors: Frank, John R., Rauch, Erik M., Donoghue, Karen
• Granted Patent: US 7,117,199 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99939 Privileged access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

An interface program stored on a computer-readable medium for causing a computer system with a display device to perform the functions of: accepting search criteria from a user including a free text entry query and a domain identifier identifying a domain; in response to accepting the search criteria, retrieving a plurality of record identifiers each of which identifies a corresponding record which: (1) has associated therewith a location identifier that locates it at a specific location within the domain identified by the domain identifier; and (2) contains information that is responsive to the free text entry query; displaying a representation of the domain on the display device; and displaying on the display device a plurality of icons as representations of the records identified by the plurality of record identifiers, wherein for each of the record identifiers, a corresponding one of the plurality of icons is displayed within the representation of the domain that is being displayed on the display device, the corresponding icon for each of the plurality of record identifiers being positioned within the representation of the domain at a coordinate within the domain that corresponds to the location identifier for the corresponding record.

Claims

1. An interface program stored on a computer-readable medium for causing a computer system with a display device to perform the functions of:

accepting search criteria from a user including a free text entry query and a domain identifier identifying a domain;

in response to accepting said search criteria from the user, retrieving a plurality of record identifiers each of which identifies a corresponding record which;

(1) has associated therewith a location identifier that locates it at a specific location within the domain identified by the domain identifier; and

(2) contains information that is responsive to the free text entry query;

displaying a representation of said domain on the display device; and

displaying on the display device a plurality of icons as representations of the records identified by said plurality of record identifiers, wherein for each of said plurality of record identifiers, a corresponding one of the plurality of icons is displayed within said representation of the domain that is being displayed on the display device, the corresponding icon for each of said plurality of record identifiers being positioned within the representation of the domain at a coordinate within the domain that corresponds to the location identifier for the corresponding record.

2. The interface program of claim 1 wherein the domain is a geographical region and said representation is a multi-dimensional map of the geographical region.

3. The interface program of claim 1 wherein said representation is a two-dimensional map of the geographical region.

4. The interface program of claim 2 wherein accepting input further comprises accepting a designation by the user of a designated category and wherein each of the records corresponding to the plurality of retrieved record identifiers also includes information that falls within the designated category.

5. The interface program of claim 4 wherein accepting said designation by the user of a category comprises presenting to the user a list of predefined categories and accepting as the designated category a selection by the user from that list.

6. The interface program of claim 3 for causing the computer to perform the further functions of:

after displaying the corresponding icon for each of the plurality of record identifiers, accepting further search criteria from the user, said further search criteria selected from the group of search criteria types consisting of a domain identifier input type, a free text entry query input type, and a category type;

in response to accepting said further search criteria from the user, retrieving a subset of said plurality of record identifiers, wherein said subset of said plurality of record identifiers identifies all record identifiers among said plurality of record identifiers that fall within said further search criteria;

displaying a two-dimensional map of a revised geographical region on the display device that is responsive to said further search criteria; and

for each of the record identifiers of said subset of plurality of record identifiers, displaying a corresponding icon within said displayed map, the corresponding icon for each of the record identifiers of said subset of said plurality of record identifiers being positioned within the displayed map at a coordinate that corresponds to the location identifier for the corresponding record.

7. The interface program of claim 6 for causing the computer to perform the further functions of storing as a filter the first-mentioned search criteria in combination with said further search criteria, wherein said stored filter is retrievable for use by the user in specifying a future search through the interface.

8. The interface program of claim 7 wherein the first-mentioned search criteria in combination with said further search criteria is an ordered sequence of inputs and wherein the stored filter is the ordered sequence of inputs preserving the order of the sequence of inputs

9. The interface program of claim 3 for causing the computer to perform the further functions of:

presenting to the user via the display device a map; and

enabling the user to input said domain identifier as part of the search criteria by interacting with the displayed map.

10. The interface program of claim 3 wherein said plurality of icons include an icon of a first icon class and an icon of a second icon class, wherein the icon of the first icon class has first visual characteristics and the icon of the second icon class has second visual characteristics that are different from the visual characteristics associated with the first icon class.

11. The interface program of claim 10 wherein at least some of the records identified by said plurality of record identifiers are of a first type and at least some of the other records identified by said plurality of record identifiers are of a second type and wherein records of the first type are displayed using the icon of the first icon class and records of the second type are displayed using the icon of the second icon class.

12. The interface program of claim 3 wherein at least one of the icons of the plurality of icons represents multiple of the records identified by said plurality of record identifiers, each of said multiple of the records having a location identifier that locates that record within a neighborhood about a central location.

13. The interface program of claim 3 for causing the computer to perform the further functions of:

accepting a change of scale request from the user;

in response to accepting said change of scale request, consolidating at least some of said plurality of icons with each other to form a second plurality of icons that is fewer in number than the number of icons in said first-mentioned plurality of icons; and

in response to accepting said change of scale request, redisplaying said domain using a decreased scale and also using the second plurality of icons to identify the locations of the records identified by said plurality of record identifiers.

14. The interface program of claim 3 for causing the computer to perform the further functions of:

accepting from the user a specification of an electronic note which has an associated location within the map; and

displaying a sticky-note icon on the map at position that corresponds to the associated location.

15. The interface program of claim 14 wherein the electronic note comprises a web page with its own externally accessible address which enables people to electronically access its contents through that address.

18. The method of claim 17 wherein the spatial-keyword document index comprises a spatial index tree extended to reference documents and a plurality of trees with the same structure as said spatial index tree but trimmed for particular lexicon entries and filters.

19. The method of claim 17 wherein said plurality of record identifiers are retrieved in a spatial-keyword document index tree and the branching structure of said tree is analyzed to identify geographic phenomena.

20. The method of claim 19 wherein a geographic phenomena is a spatial-keyword document index tree branching structure in which more than a predetermined fraction of the branches share more than predetermined number of parent nodes.

16. A database system stored on a computer-readable medium for causing a computer system to perform the functions of:

accepting search criteria including at least one of;

(1) text;

(2) a domain identifier identifying a domain; and

(3) a filter identifier identifying a filter; and

retrieving a plurality of record identifiers each of which identifies a corresponding record which has associated therewith the text, domain identifier, or layer identifier of the search criteria, where the retrieving is performed with a spatial-keyword document index.

17. A method of retrieving a plurality of record identifiers each of which identifies a corresponding record which has associated therewith at least one of a text, a domain identifier, and a layer identifier as specified by search criteria, wherein such retrieving is performed with a spatial-keyword document index.

21. A program stored on a computer-readable medium for causing a computer system to perform the functions of:

loading documents referred to by document addresses;

parsing those documents for more document addresses to load; and

parsing those documents for possible spatial identifiers.

22. The program of claim 21 for causing the computer system to perform the further function of analyzing the possible spatial identifiers to determine a location in a domain.

23. The program of claim 21 wherein a portion of the document addresses are gathered by a metasearcher process, which queries other computer systems using text that refers to spatial domains.

24. The program of claim 21 for causing the computer system to perform the further function of computing a relevance score for each of the possible spatial identifiers found in each document.

25. The program of claim 21 wherein the relevance score comprises one or more of:

(1) the possible spatial identifier'"'"'s position in the document;

(2) the number of other possible spatial identifiers in the document;

(3) whether the possible spatial identifier is in a sentence or is free standing; and

(4) the formatted emphasis of the characters in the possible spatial identifier.

26. The program of claim 21 for causing the computer system to perform the further function of sorting the document addresses by relevance score before loading.

29. The method of claim 28, wherein the result set, when it contains more than one element, comprises a plurality of groups organized by spatial proximity, each group containing at least one document of the result set.

30. The method of claim 29 wherein the plurality of groups is ordered according to a predetermined function on groups representing relevance to the criteria.

31. The method of claim 29, wherein the content of each group is ordered according to a predetermined function on elements representing relevance to the criteria.

32. The method of claim 28, wherein the criteria include keywords.

27. A program stored on a computer-readable medium for causing a computer system to perform the functions of:

loading documents referred to by document addresses;

parsing those documents for more document addresses to load;

parsing those documents for possible spatial identifiers; and

analyzing the possible spatial identifiers to determine a location in a domain.

28. A method of displaying spatially coded information, comprising:

through an automated computer process, gathering documents in a database;

selecting a subset of the documents which can be determined to contain spatial information;

associating at least one spatial identifier with each document in the subset;

indexing the documents, the indexing comprising an index on spatial identifiers and an index on keywords;

providing a computer interface through which a user can submit a query comprising spatial information;

responding to the query with a result set comprising documents; and

displaying the result set to the user through the computer interface.

33. A method for populating a spatial document database with hyperlinked documents containing spatial information, the method comprising:

providing a destination database containing potential sources of gatherable documents;

providing a history database of known sources where documents have been gathered;

providing a crawler computer process which can follow a hyperlink in a document to access a potential source of gatherable documents specified by the hyperlink;

bootstrapping the crawler;

iterating the crawler over the destination database, including the steps of;

moving a potential source of gatherable documents from the destination database to the history database;

inspecting the potential source for gatherable documents;

storing any such gatherable documents in the spatial document database; and

adding to the destination database all potential sources of gatherable documents which are referenced by a hyperlink in the gatherable documents.

34. The method of claim 33, wherein the bootstrapping comprises

providing a plurality of locations of known interest;

providing the destination database with a plurality of metasources, each metasource being a source of potential sources of gatherable documents, and each metasource responding to queries by the computer process with a result set comprising potential sources of gatherable documents; and

priming the destination database by repeatedly running a primer process comprising;

formulating a query based on at least one of the locations of known interest;

directing the query to a metasource;

receiving a result set for the query; and

inserting each element of the result set into the destination database.

35. A method for scoring the relevance to a query of a document containing a known spatial identifier, the method comprising:

scoring the document for its relevance to a place specified in the query;

scoring the document for its relevance to a word specified in the query;

scoring the document for its quality; and

combining the scores to form a single score.

36. A method for indexing a plurality of documents to enable queries comprising keywords and spatial information, the method comprising:

initializing a master spatial tree of predetermined degree as a computer data structure, such that;

(1) each leaf node of the master spatial tree represents a document;

(2) each non-leaf node of the master spatial tree represents a range of space;

(3) a root node of the master spatial tree represents a range of space encompassing any space that a valid query may refer to; and

(4) the collection of non-leaf child nodes, relative to a parent node, define a partition on the range of space represented by the parent;

recursively adding a child node to the tree.