Method and Apparatus for Geographic Document Retrieval

• US 20140129566A1
• Filed: 04/19/2013
• Published: 05/08/2014
• Est. Priority Date: 11/08/2012
• Status: Active Grant

• Current Assignee: xAd, Inc
• Original Assignee: xAd, Inc
• Inventors: Chang, Chi-Chao, Mediano, Mauricio, Venkatesan, Srihari, Muttineni, Prakash, Sharma, Dipanshu
• Granted Patent: US 9,210,540 B2
• Time in Patent Office: Days
• US Class Current: 707/742
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06Q 30/0205 Location or geographical consideration
• CPC Class Codes: G06Q 30/0261 based on user location
• CPC Class Codes: H04L 67/53 using third party service providers
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

A geographic document retrieval method (GDR) can be executed by a computer system to index, retrieve and rank geographical documents. Textual and spatial attributes of geographical documents are indexed separately using inverted index and spatial index, respectively. Spatial attributes of a document are represented as one or more contiguously closed regions of arbitrary shapes. Upon receiving an input query carrying a geographic representation of a location using arbitrary regions, the GDR method retrieves one or more documents by executing an overlap test between arbitrary regions from the query and the arbitrary regions associated with the documents.

Claims

1. A method of indexing geographical documents, comprising:

separating textual attributes and spatial attributes associated with each of the geographical documents;

indexing the textual attributes using inverted index; and

indexing the spatial attributes using spatial index.

2. The method of claim 1 wherein the spatial attributes include one or more contiguously closed geographical regions of arbitrary shapes.

3. The method of claim 2, further comprising:

for each respective contiguously closed region, computing a smallest rectangle that contains the respective contiguously closed region.

4. The method of claim 3, wherein the spatial index includes a bounding box field corresponding to the smallest rectangles and a shape field corresponding to geometry of the contiguously closed regions.

5. The method of claim 2, further comprising:

storing each contiguously closed region in a respective V-tree.

6. A method of retrieving geographical documents, comprising:

receiving a query having one or more spatial clauses and at least one other clause, the one or more spatial clauses representing one or more contiguously closed geographical regions of arbitrary shapes;

selecting at least one first document from geographical documents stored in a computer readable medium, the geographical documents each having associated therewith a spatial index and an inverted index, each of the at least one first document having a spatial index matching the one or more spatial clauses; and

selecting at least one second document from the at least one first document, the at least one second document each having an inverted index that matches the at least one other clause in the query.

7. The method of claim 6 wherein the spatial index associated with each geographical document represents one or more contiguously closed geographical regions of arbitrary shapes.

8. The method of claim 7, wherein each of the one or more contiguously closed geographical regions represented by the spatial index has associated therewith a bounding box, and wherein retrieving at least one first document comprises:

computing a bounding box for each of the one or more contiguously closed geographical regions represented by the query; and

selecting at least one third document each having one or more bounding boxes intersecting one or more bounding boxes for the one or more contiguously closed geographical regions represented by the query.

9. The method of claim 8, wherein the at least one first document is selected from the at least one third document such that each of the at least one first document has one or more contiguously closed geographical regions overlapping at least one of the one or more contiguously closed regions represented by the query.

10. The method of claim 6, further comprising ranking the at least one second document.

11. The method of claim 10, wherein the at least one second document is ranked based on features of the one or more contiguously closed geographical regions represented by the spatial index that overlap with any of the one or more contiguously closed regions represented by the query.

12. The method of claim 10, wherein the at least one second document is ranked based on features of the query.

13. The method of claim 10, further comprising selecting one of the at least one second document for retrieval based on result of the ranking

14. An apparatus, comprising:

one or more data stores storing therein geographical documents each having associated therewith a spatial index and an inverted index, the spatial index associated with each geographical document represents one or more contiguously closed geographical regions of arbitrary shapes; and

a geographical document retrieval engine configured to retrieve from the one or more data store a geographical document in response to a query having one or more spatial clauses and at least one other clause, the one or more spatial clauses representing one or more contiguously closed geographical regions of arbitrary shapes.

15. The apparatus of claim 14, wherein the geographical document retrieval engine is further configured to:

selecting at least one first document from the one or more data stores, each of the at least one first document having a spatial index matching the one or more spatial clauses; and

selecting at least one second document from the at least one first document, the at least one second document each having an inverted index that matches the at least one other clause in the query.

16. The apparatus of claim 15, wherein each of the one or more contiguously closed geographical regions represented by the spatial index has associated therewith a bounding box, and wherein retrieving at least one first document comprises:

computing a bounding box for each of the one or more contiguously closed geographical regions represented by the query; and

selecting at least one third document each having one or more bounding boxes intersecting one or more bounding boxes for the one or more contiguously closed geographical regions represented by the query.

17. The apparatus of claim 16, wherein the at least one first document is selected from the at least one third document such that each of the at least one first document has one or more contiguously closed geographical regions overlapping at least one of the one or more contiguously closed regions represented by the query.

18. The apparatus of claim 14, further comprising ranking the at least one second document.

19. The apparatus of claim 18, wherein the at least one second document is ranked based on features of the one or more contiguously closed geographical regions represented by the spatial index that overlap with any of the one or more contiguously closed regions represented by the query.

20. The apparatus of claim 18, wherein the at least one second document is ranked based on features of the query.