T 1238/20 (Location information/FOURSQUARE LABS) of 25.5.2023

Summary of Facts and Submissions

I. The appellant (applicant) appealed against the decision of the examining division refusing European patent application No. 14720841.7, which was published as international application WO 2014/145069 and claims a priority date of 15 March 2013.

II. The contested decision cited the following documents:

D1: |"SpatialPrefixTree (Lucene 4.0.0 API)", 13 March 2013, retrieved from https://web.archive.org/web/20130313072002/http://lucene.apache.org/core/4_0_0/spatial/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTree.html;|

D2: |D. Smiley: "Lucene 4 spatial", Open Source Search Conference, 2 October 2012; |

D3: |H. Samet: "Hierarchical spatial data structures", Proceedings of the First Symposium on Design and Implementation of Large Spatial Databases, 17 July 1989, pp. 193-212; |

D4: |US 2006/0253481 A1, 9 November 2006; |

D5: |P. van Oosterom and T. Vijlbrief: "The Spatial Location Code", Proceedings of the Seventh International Symposium on Spatial Data Handling, 12 August 1996; |

D8: |"GeohashPrefixTree (Lucene 4.0.0 API)", 13 March 2013, retrieved from https://web.archive.org/web/20130313071952/http://lucene.apache.org/core/4_0_0/spatial/org/apache/lucene/spatial/prefix/tree/GeohashPrefixTree.html;|

D9: |"Geohash", Wikipedia, 14 November 2012, retrieved from http://en.wikipedia.org/w/index.php?title=Geohash&oldid=523024733; |

D10:|"Geohash", Wikipedia, 16 January 2013, retrieved from: https://web.archive.org/web/20130116074554/https://en.wikipedia.org/wiki/Geohash; |

D11:|"Trie", Wikipedia, 25 January 2013, retrieved from https://web.archive.org/web/20130125115830/https://en.wikipedia.org/wiki/Trie. |

The examining division decided that the subject-matter of claim 1 of the main request and of the first and second auxiliary requests lacked inventive step in view of documents D1, D2, D4, D8, D10 and D11 and that claim 1 of the second auxiliary request did not comply with Article 84 EPC.

Under the heading "Further considerations", the examining division noted that two of the clarity objections raised against claim 1 of the second auxiliary request also applied to claim 1 of the main request and of the first auxiliary request.

III. With its statement of grounds of appeal, the appellant filed an amended main request and amended first and second auxiliary requests and requested reimbursement of the appeal fee in view of three substantial procedural violations.

IV. In a communication accompanying the summons to oral proceedings, the board expressed the preliminary opinion that the request for reimbursement of the appeal fee could not be allowed and that the subject-matter of claim 1 of the main request and of the first and second auxiliary requests lacked an inventive step over document D4 combined with the common general knowledge as exemplified by documents D3 and D5. It also raised objections under Article 84 EPC against the main request and first and second auxiliary requests and under Article 123(2) EPC against the second auxiliary request.

V. With its written submissions in preparation for the oral proceedings, the appellant replaced its requests with an amended main request and amended first and second auxiliary requests.

VI. Oral proceedings were held as scheduled. At the end of the oral proceedings, the chair announced the board's decision.

VII. The appellant's final requests were that the decision under appeal be set aside, that a patent be granted on the basis of the claims of the main request or, in the alternative, one of the first and second auxiliary requests, and that the appeal fee be reimbursed.

VIII. Claim 1 of the main request reads as follows:

"An apparatus comprising:

a processor (108) configured to execute instructions stored in memory (110) to:

represent (1202) a region of interest with one or more polygons;

determine (1204) a plurality of sub-polygons that are contained within the one or more polygons, wherein each of the sub-polygons is associated with a unique code comprising a geohash code; and

generate (1206) a first index system based on the plurality of sub-polygons,

wherein the processor is further configured to:

receive a location query from a client device, wherein the location query includes a location identifier providing geolocation of the client device;

determine a query geohash code corresponding to the location identifier;

compare the query geohash code with the index system to determine that the location identifier provided by the client device is within the region of interest; and

based on the location being within the region of interest,

provide a service associated with the region of interest to the client device over a communication network."

IX. Claim 1 of the first auxiliary request differs from claim 1 of the main request in that:

- the text "and wherein the sub-polygons include sub-polygons of different precisions" has been inserted after "a unique code comprising a geohash code";

- the text "compare the query geohash code with the index system" has been replaced with "compare a first set of bits of the query geohash code, corresponding to a lower precision sub-polygon, with the index system before comparing a second set of bits of the query geohash code, corresponding to a higher precision sub-polygon".

X. Claim 1 of the second auxiliary request reads as follows:

"An apparatus comprising:

a processor (108) configured to execute instructions stored in memory (110) to:

represent (1202) a region of interest with one or more polygons;

determine (1204) a plurality of sub-polygons that are contained within the one or more polygons, wherein each of the sub-polygons is associated with a unique code comprising a geohash code and wherein the sub-polygons include sub-polygons of different precisions;

generate (1206) indices for a first index system based on the plurality of sub-polygons, the first index system based on a tree structure wherein the tree structure includes a branch node and a leaf node and the branch node is associated with a sub-polygon of lower precision than a sub-polygon of the leaf node; and

wherein the processor (108) is further configured to

generate the indices for the first index system by traversing the tree structure from the branch node to the leaf node each index corresponding to a value of each traversed node;

receive a location query from a client device, wherein the location query includes a location identifier providing geolocation of the client device;

determine a query geohash code corresponding to the location identifier;

compare a first set of bits of the query geohash code corresponding to a lower precision sub-polygon with a first index of the index system before comparing a second set of bits of the query geohash code corresponding to a higher precision sub-polygon with a second index of the index system, to determine that the location identifier provided by the client device is within the region of interest; and

based on the location being within the region of interest, provide a service associated with the region of interest to the client device over a communication network."

XI. The appellant's arguments, where relevant to this decision, are discussed in detail below.

Reasons for the Decision

1. The application relates to providing location-dependent services over a communication network.

2. Alleged substantial procedural violations

In its statement of grounds of appeal, the appellant submitted that the first-instance proceedings had been tainted by three substantial procedural violations. At the beginning of the oral proceedings before the board, the appellant clarified that it did not request an immediate remittal of the case. Moreover, the board did not consider that any deficiencies in the first-instance proceedings were so fundamental within the meaning of Article 11 RPBA 2020 that they necessitated an immediate remittal without a substantive assessment of the merits of the case.

3. Admission into the appeal proceedings

3.1 The main request and the first and second auxiliary requests were filed after the notification of the summons to oral proceedings before the board. They are based on the requests considered in the decision under appeal with amendments filed with the appellant's statement of grounds of appeal and with the appellant's written submissions in preparation for the oral proceedings before the board.

3.2 Since the amendments filed with the statement of grounds of appeal represented reasonable attempts at overcoming the clarity objections raised in the contested decision, in its communication the board expressed the intention to admit them into the appeal proceedings (Article 12(4) RPBA 2020).

3.3 The amendments filed with the written submissions in preparation for the oral proceedings were made in response to clarity objections raised for the first time in the board's communication. Their admission into the appeal proceedings is therefore justified by exceptional circumstances (Article 13(2) RPBA 2020).

3.4 Hence, the main request and the first and second auxiliary requests are admitted into the appeal proceedings.

4. Document D9

4.1 Document D9 is a printout of the "Geohash" Wikipedia entry as revised on 14 November 2012. It was retrieved on 16 June 2014 from the Wikipedia website by using the "View history" function, which allows users to access the revision history of an entry. The board is not aware of any sound reason to doubt that the revision history of this Wikipedia entry had been tampered with.

4.2 In its statement of grounds of appeal, the appellant took the view - with respect to document D10, which is another version of the same Wikipedia entry - that a document published on the internet is not part of the prior art before it has actually been accessed or read by a member of the public. However, the criterion for a document to be part of the prior art under Article 54(2) EPC is that it has been made available to the public before the effective filing date as determined by Article 89 EPC, not that a member of the public has actually accessed or read it (see decision T 381/87, OJ EPO 1990, 213, Reasons 4).

4.3 Since the content of document D9 could be accessed by any member of the public on the Wikipedia website on 14 November 2012 and thus before the priority date, it is prior art under Article 54(2) EPC.

Main request

5. The invention as defined by claim 1

5.1 Claim 1 is directed to an apparatus comprising a processor configured to execute instructions stored in memory to carry out the following steps.

5.2 First, an "index system" is generated for a "region of interest".

The region of interest is represented by one or more polygons. A plurality of sub-polygons is determined, where each sub-polygon is contained within one or more of the polygons and is associated with "a unique code comprising a geohash code". The first index system is generated based on the plurality of sub-polygons.

5.3 Next, a location query is received from a client device. The location query includes a location identifier providing geolocation of the client device.

The location identifier is converted into a query geohash code.

The query geohash code is compared with the index system to determine whether the location of the client device is within the region of interest.

If the location is within the region of interest, a service associated with the region is provided to the client device over a communication network.

5.4 According to paragraph [0066] of the published application, a "geohash code" is "a hierarchical spatial data structure that subdivides a region into tiles" which "can include a sequence of bits that substantially uniquely identifies a location".

Paragraph [0066] mentions "a geohash code of the type defined in http://geohash.org/" as a non-limiting example of a geohash code. The geohash codes used at http://geohash.org/ are a base-32 encoding of a bit pattern formed by interleaving the binary representations of latitude and longitude coordinates (see document D9, page 1, first paragraph, and page 2, section "Decode from base 32").

6. Inventive step

6.1 Document D4 discloses a navigation services server 320 associated with a geographic database 140 that facilitates location-based advertising and other location-based services (abstract; paragraphs [0042] to [0045] and [0056]; Figure 7).

6.2 The geographic database 140 includes advertising zone data 270 representing "regions of interest" in the form of advertising zones 250 (paragraph [0035]; Figures 2 and 4). Advertising zones may have different sizes and shapes (paragraph [0029]).

6.3 As end users with mobile or portable computing platforms travel through a geographic region, their position is determined by positioning equipment associated with their computing platform (paragraph [0060]). A virtual billboard application 388 running on the navigation services server 320 receives "location queries" including location identifiers indicating each end user's current position (paragraph [0061]; Figure 7). Based on the end user's current position, the virtual billboard application identifies the advertising zone in which an end user is located, retrieves from an ad database 398 the advertising message associated with the advertising zone, and sends the message to the end user (paragraphs [0061] and [0062]).

6.4 The subject-matter of claim 1 differs from the disclosure of document D4 in that:

(a) an advertising zone/region of interest is defined by one or more polygons;

(b) the advertising zone/region of interest is encoded in the database as an "index system" which is generated based on a plurality of sub-polygons which are contained in the polygons, each sub-polygon being associated with a unique code comprising a geohash code;

(c) whether an end user's current position/location is within an advertising zone/region of interest is determined by converting the current location into a query geohash code and comparing the query geohash code with the index system encoding the advertising zone.

6.5 As for feature (a), allowing an advertising zone to be defined by one or more polygons, such as a rectangle, is an obvious possibility.

In fact, paragraph [0034] of document D4 states that the boundaries of advertising zones "do not necessarily correspond to the rectangular areas defined for data parcels" and therefore clearly hints to the possibility that an advertising zone may be defined by such a rectangular area, i.e. by a polygon. Moreover, Figure 4 shows advertising zones in the shape of rectangles in layers 260(1) and 260(3).

6.6 Features (b) and (c) specify details relating to how the advertising zone is encoded in a geographic database and how it is determined whether a given location is within the advertising zone.

6.7 The appellant argued that document D4 provided a complete, self-contained solution to determining whether an end user's current position was within an advertising zone. The skilled person would therefore have had no incentive to look for other possibilities.

6.7.1 In its statement of grounds of appeal, the appellant, referring in particular to Figures 3 and 5 and paragraph [0039], argued that document D4 disclosed only one way of determining the presence of a user in an advertising zone, namely by means of road segment data records 200 which included data that identified the advertising zones in which a road segment was located.

However, there is no reason why, in document D4, a road segment that intersects an advertising zone necessarily lies completely within the advertising zone. Figure 4 rather suggests that each road segment drawn in geographic region 100 intersects a plurality of the disjoint advertisement zones shown in each of layers 260(1), 260(2) and 260(3). Hence, even when it is known that the end user's position is on a particular road segment, it is still necessary to determine, for each of the advertisement zones intersecting that road segment, whether the user's current position is within the zone.

6.7.2 At the oral proceedings, the appellant relied instead on paragraph [0036] of document D4, which disclosed that the geographic database 140 included boundary data 280(2) indicating the boundaries of the advertising zones in terms of (i) geographic coordinates of the boundaries, (ii) a radius from a point, (iii) parcel boundaries, or (iv) geographic features such as streets and rivers. None of these possibilities corresponded to the claimed solution.

6.8 The board accepts that document D4 provides some guidance on how to encode advertising zones in the geographic database and how to determine whether a given location is within an advertising zone, and that this guidance does not point to features (b) and (c). However, this does not mean that the skilled person, starting from document D4, would not consider the problem of providing an (alternative) implementation of determining whether the end user's current position is within an advertising zone.

6.9 The board agrees with the appellant that documents D1, D2 and D8, on which the examining division relied to show that the implementation represented by features (b) and (c) was obvious, do not represent an enabling teaching.

However, the geographic indexing technique specified by features (b) and (c) was part of the skilled person's common general knowledge at the priority date, as explained below.

6.10 As confirmed by document D3, section 2 and Figure 1, and document D5, section 2.1 and Figure 1, quadtree representations were a well-known technique for encoding geographical regions. Figure 1 of document D3, reproduced below, shows a polygonal region (a), which is decomposed into sub-polygons in the form of blocks as shown in (c). On the basis of these sub-polygons, an index structure is generated in the form of a tree structure (d), in which the black leaf nodes correspond to the sub-polygons making up region (a).

FORMULA/TABLE/GRAPHIC

6.11 Each sub-polygon/leaf in the tree is assigned a "locational code" or "quadcode", which corresponds to a sequence of directional codes that locate the leaf along a path from the root of the quadtree (D3, page 197, last paragraph; D5, section 2.1). This is analogous to taking the binary representation of the x and y coordinates of a designated pixel in the sub-polygon in the block and interleaving them (D3, page 197, last paragraph).

6.12 The board notes that the locational codes and quadcodes of documents D3 and D5 are "geohash codes" within the meaning of claim 1, as they correspond to a sequence of bits that represent a tile obtained by subdividing a geographical region (see point 5.4 above).

6.13 The appellant argued that documents D3 and D5 were concerned with representing and classifying regions of pictures, not with determining whether a position was within a particular geographic region.

However, document D3, page 196, lines 23 to 25, confirms that quadtrees were a known means of indexing into a geographic database.

6.14 The appellant further argued that, as recognised in paragraphs [0045] and [0096] of the published application, the look-up mechanism specified by features (b) and (c) was efficient in terms of speed. Documents D3, D4 and D5 did not mention the problem of improving query response times. At the oral proceedings, the appellant conceded that quadtrees were known to be efficient but argued that the skilled person needed a pointer before they would look into speeding up the query response times of document D4. Without such a pointer, the choice to optimise this particular aspect of the system of document D4 out of all possible aspects amounted to an inadmissible use of hindsight.

The board does not agree. The geographic database 140 is a readily identifiable aspect of the system of document D4, and the skilled person would therefore not need a pointer to consider the problem of providing an alternative or more efficient implementation. The fact that the system of document D4 may comprise many aspects which are the potential subject of further routine development does not render the choice for one such aspect inventive.

6.15 In view of the above, the board considers that the objective technical problem may validly be formulated as providing an efficient implementation of the geographic database and the mechanism for determining whether a given location is within the advertising zone.

The skilled person, starting from document D4 and faced with this problem, would consider using a well-known quadtree representation to encode an advertising zone as an "index structure" consisting of a tree with leaf nodes corresponding to sub-polygons in the form of blocks contained within the zone and labelled with geohash codes. They would thereby arrive at features (b) and (c) without the exercise of inventive skill.

6.16 Hence, the subject-matter of claim 1 of the main request lacks an inventive step (Article 56 EPC).

First auxiliary request

7. Inventive step

7.1 Claim 1 of the first auxiliary request adds to claim 1 of the main request that:

(d) the sub-polygons include sub-polygons of different precisions;

(e) comparing the query geohash code with the index system involves comparing a first set of bits corresponding to a lower-precision sub-polygon before comparing a second set of bits corresponding to a higher-precision sub-polygon.

7.2 As for feature (d), the well-known quadtree representation uses sub-polygons in the form of blocks of different sizes and thus of different precisions.

7.3 As for feature (e), when traversing a quadtree-based index system from the root node to a leaf node to determine whether a geohash code corresponds to a position within one of the sub-polygons, the geohash code will first be compared with lower-precision sub-polygons closer to the root node before it is compared with higher-precision sub-polygons at a larger distance from the root node.

7.4 Thus, features (d) and (e) follow in a obvious manner from the choice by the skilled person to use a quadtree representation to encode an advertising zone. Hence, the subject-matter of claim 1 of the first auxiliary request also lacks an inventive step (Article 56 EPC).

Second auxiliary request

8. Inventive step

8.1 Claim 1 of the second auxiliary request adds to claim 1 of the first auxiliary request that:

(f) the index system is based on a tree structure wherein the tree structure includes a branch node and a leaf node and the branch node is associated with a sub-polygon of lower precision than a sub-polygon of the leaf node;

(g) indices for the index system are generated by traversing the tree structure from the branch node to the leaf node, each index corresponding to a value of each traversed node.

8.2 In the quadtree structure shown in Figure 1(d) of document D3 (see point 6.10 above), leaf node 4 is associated with sub-polygon 4 of Figure 1(c), and branch node B is associated with the sub-polygon formed by blocks 2, 3, 4 and 5 of Figure 1(c), i.e. a sub-polygon of lower precision than sub-polygon 4.

Moreover, nodes of the trees, corresponding to indices of the tree index system, are generated by traversing the tree structure from the branch node to the leaf node while subdividing the corresponding sub-polygons.

Hence, the features (f) and (g) follow in a obvious manner from the choice by the skilled person to use a quadtree representation to encode an advertising zone.

8.3 It follows that the subject-matter of claim 1 of the second auxiliary request lacks an inventive step (Article 56 EPC).

9. Since none of the substantive requests on file is allowable, the appeal is to be dismissed.

10. As the appeal is not allowed, the appellant's request for reimbursement of the appeal fee under Rule 103(1)(a) EPC cannot be allowed, either. Moreover, none of the other reimbursement possibilities listed in Rule 103 EPC applies.

Order

For these reasons it is decided that:

The appeal is dismissed.