Searching by using spatial document and spatial keyword document indexes

• US 7,953,732 B2
• Filed: 06/07/2005
• Issued: 05/31/2011
• Est. Priority Date: 02/22/2000
• Status: Expired due to Fees

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Corporation
• Inventors: Frank, John R., Rauch, Erik M.
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): Uddin; Mohammed R
• Application Number:
  US11/147,033
• Publication Number:
  US 20060036588A1
• Time in Patent Office: 2,184 Days
• Field of Search: 707/3, 707/4, 707/5, 707/6, 707/101, 707/102, 707/104.1, 707/724
• US Class Current: 707/724
• 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

A computer-implemented method for searching a corpus of documents for documents that are responsive to a query specifying one or more search words and spatial information, the method involving: storing in memory a spatial document index for the corpus of documents, wherein the spatial document index indexes documents in the corpus according to spatial references found within the documents; storing in a storage medium a plurality of spatial keyword document indexes for the corpus of documents, wherein each of the spatial keyword document indexes is for a different keyword and indexes those documents among the corpus that are responsive to that keyword; and intersecting a portion of the spatial document index and selected indexes among the plurality of spatial keyword document indexes to identify a result set of those documents from among the corpus of documents that are responsive to the query.

Claims

1. A method comprising:

determining to store a spatial document index for a corpus of documents, wherein the spatial document index indexes documents in the corpus according to spatial references found within the documents;

determining to store a plurality of spatial keyword document indexes for the corpus of documents, wherein the spatial keyword document indexes are derived from the spatial document index, are for a different keyword, and indexes those documents among the corpus that are responsive to that keyword; and

intersecting a portion of the spatial document index and selected indexes among the plurality of spatial keyword document indexes to identify a result set of those documents from among the corpus of documents that are responsive to a query.

2. The method of claim 1, wherein the spatial document index includes:

a plurality of leaf nodes, at least one of which identifies a corresponding document from the corpus of documents;

a root node representing a range of space encompassing any space that a valid query may refer to; and

a collection of non-leaf nodes, at least one of which represents a corresponding region of space.

3. The method of claim 2, wherein the at least one of the plurality of leaf nodes also contains relevance information about a corresponding spatial location referred to by the document corresponding to that leaf node.

4. The method of claim 3, further comprising constructing the spatial keyword document indexes for the corresponding keyword by:

populating the at least one of the plurality of leaf nodes with a copy of the spatial document index with a relevance of that corresponding keyword to the document identified by that leaf node;

pruning all unpopulated leaf nodes where the corresponding keyword does not appear in the document identified by that leaf node; and

recursively pruning from the bottom up all non-leaf nodes that have no children.

5. The method of claim 1, further comprising determining to present the result set to a user.

6. The method of claim 1, wherein said spatial document index is a tree data structure of degree k, k is an integer, wherein at least one index of the plurality of spatial keyword document indexes is a tree data structure of degree m, m is an integer, and wherein k=m.

7. The method of claim 1, further comprising:

paging selected indexes among the plurality of spatial keyword document indexes into a main memory as needed,

wherein the spatial document index for the corpus of documents is stored in a main memory, and

wherein the plurality of spatial keyword document indexes for the corpus of documents are stored in a disk storage.

8. The method of claim 1, wherein at least one of the spatial keyword document indexes is a pruned version of the spatial document index that indexes only documents among the corpus of documents that are responsive to that keyword.

9. The method of claim 8, wherein at least one of the spatial keyword document indexes is constructed by trimming nodes from the spatial document index, wherein the trimmed nodes represent documents that are not responsive to any of the one or more keywords.

10. The method of claim 1, wherein at least one of the documents of the result set contains the said one or more keywords specified in the query and is responsive to the spatial information specified in the query.

11. The method of claim 1, wherein the spatial document index and at least one of the spatial keyword document indexes comprise nodes within corresponding tree data structures, said method further comprising:

identifying those indexes among the spatial keyword document indexes that are responsive to said one or more keywords, the identified indexes being said selected ones of the plurality of spatial keyword document indexes; and

to generate said portion of the spatial document index, trimming away all nodes from the spatial document index that correspond to coordinates outside of a region bounded by the spatial information.

12. The method of claim 11, wherein intersecting includes selecting an index from among the identified spatial keyword document indexes and said portion of the spatial document index, and generating a result tree from the selected index by trimming away all nodes from the selected index except those that represent documents that are responsive to the query, wherein the result tree represents the result set.

13. The method of claim 1, wherein the plurality of spatial keyword document indexes is for a plurality of keywords, wherein the plurality of keywords is indexed by a corresponding different spatial keyword document index among the plurality of spatial keyword document indexes.

14. The method of claim 1, wherein at least one of the plurality of spatial keyword document indexes is for only a single corresponding keyword.

15. The method of claim 1, wherein at least one of the spatial keyword document indexes indexes the documents among the corpus that include text containing the keyword to which that spatial document keyword index corresponds.

16. The method of claim 1, wherein intersecting includes trimming away from one of the selected indexes all nodes except those that represent documents that are responsive to the query.

17. An apparatus comprising:

at least one processor; and

at least one memory including computer program code,

the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus at least to;

determine to store a spatial document index for a corpus of documents, wherein the spatial document index indexes documents in the corpus according to spatial references found within the documents,

determine store a plurality of spatial keyword document indexes for the corpus of documents, wherein the spatial keyword document indexes are derived from the spatial document index, are for a different keyword, and indexes those documents among the corpus that are responsive to that keyword, and

intersect a portion of the spatial document index and selected indexes among the plurality of spatial keyword document indexes to identify a result set of those documents from among the corpus of documents that are responsive to the query.

18. The apparatus of claim 17, wherein the spatial document index includes:

a plurality of leaf nodes, at least one of which identifies a corresponding document from the corpus of documents;

a root node representing a range of space encompassing any space that a valid query may refer to; and

a collection of non-leaf nodes, at least one of which represents a corresponding region of space.

19. A computer-readable medium carrying one or more instructions which, when executed by one or more processors, cause an apparatus to at least perform the following steps:

determining to store a spatial document index for a corpus of documents, wherein the spatial document index indexes documents in the corpus according to spatial references found within the documents;

determining to store a plurality of spatial keyword document indexes for the corpus of documents, wherein the spatial keyword document indexes are derived from the spatial document index, are for a different keyword, and indexes those documents among the corpus that are responsive to that keyword; and

intersecting a portion of the spatial document index and selected indexes among the plurality of spatial keyword document indexes to identify a result set of those documents from among the corpus of documents that are responsive to the query.

20. The computer-readable medium of claim 19, wherein the spatial document index includes:

a plurality of leaf nodes, at least one of which identifies a corresponding document from the corpus of documents;

a root node representing a range of space encompassing any space that a valid query may refer to; and

a collection of non-leaf nodes, at least one of which represents a corresponding region of space.