Prior art — US Patent 9846887

To identify the most relevant prior art for US patent 9846887, I will examine the citations listed on the patent itself. The USPTO provides a Patent Public Search tool that allows users to search for patents and their associated information, including citations. Since I cannot directly access a live, interactive USPTO database to pull the full list of cited prior art and their details, I will rely on the provided patent text, which typically includes the relevant prior art cited by the examiner and applicant.

Upon reviewing the provided full patent text of US9846887B1, I see several references incorporated by reference, which typically form part of the prior art considered during examination.

Here's an analysis of the most relevant prior art explicitly mentioned and incorporated by reference within the patent's description:

Most Relevant Prior Art for US Patent 9846887

1. "Distance dependent Chinese restaurant processes" by D. M. Blei and P. I. Frazier

Full Citation: D. M. Blei and P. I. Frazier, “Distance dependent Chinese restaurant processes,” J. Mach. Learn. Res., 2461-2488, November 2011.
Publication/Filing Date: November 2011 (publication date).
Brief Description: This academic paper introduces the Distance Dependent Chinese Restaurant Process (ddCRP), a non-parametric Bayesian method for clustering non-exchangeable data where the probability of clustering items together depends on their similarity. It extends the traditional Chinese Restaurant Process (CRP) by incorporating a similarity matrix to influence customer (data point) assignments to tables (clusters).
Potential Anticipation (35 U.S.C. § 102): This reference directly anticipates aspects of independent claims 1, 2, and 3, particularly where the claims involve using probabilistic models and statistical inference (such as Gibbs sampling) for identifying clusters based on similarity.
- Claim 1 (System): The paper describes a core algorithmic component (ddCRP) for clustering based on pairwise similarities, which aligns with the "identifying two or more geographic clusters of venues... based on at least the pairwise venue similarity matrix" (Claim 1(iii)). The mention of "the similarity matrix A is a flexible way to specify prior assumptions about the strength of relationships between pairs of venues" directly relates to the pairwise venue similarity matrix in Claim 1. The patent explicitly states, "In one embodiment, the Gibbs sampler follows closely that of D. M. Blei and P. I. Frazier, 'Distance dependent Chinese restaurant processes,' ... for the ddCRP" (Description, 0070).
- Claim 2 (Method): Similar to Claim 1, the method steps of generating a pairwise venue similarity matrix and identifying clusters based on it are anticipated. The patent's description of using "probabilistic (generative) modeling, and in particular topic modeling... such as the distance dependent Chinese restaurant franchise model" (Description, 0064) further links to this prior art.
- Claim 3 (System for Sub-Region Clusters): While Claim 3 focuses on sub-regions rather than individual venues, the underlying clustering mechanism using a similarity matrix and probabilistic models would still be informed by this reference. The patent notes that "the sub-regions could be grouped, for example, based on social similarity... or whether the geographic sub-regions are emblematic of certain geographic area typologies, or emblematic of temporal check-in pattern types, or combinations thereof" (Description, 0081). The ddCRP provides a framework for such similarity-based grouping.

2. "Spatial distance dependent Chinese restaurant processes for image segmentation" by Ghosh et al.

Full Citation: Ghosh et al., “Spatial distance dependent Chinese restaurant processes for image segmentation,” Neural Information Processing Systems, 2011.
Publication/Filing Date: 2011 (publication date).
Brief Description: This paper extends the ddCRP to hierarchical modeling, specifically for image segmentation, where observations in different groups (e.g., cities in the patent's context) are linked by sharing parameters. This hierarchical approach allows for deriving insights about commonalities across different groups.
Potential Anticipation (35 U.S.C. § 102): This reference is particularly relevant to the hierarchical probabilistic modeling used in US9846887, especially when discovering neighborhood typologies across multiple cities.
- Claim 1 & 2 (System & Method for Venue Clusters): The patent states, "The Gibbs sampler follows closely that of... the extension of the ddCRP to hierarchical modeling by Ghosh et al., 'Spatial distance dependent Chinese restaurant processes for image segmentation'" (Description, 0070). This directly indicates that the hierarchical aspects of the clustering, especially when aiming for "neighborhoods consisting of venues of relatively homogenous venue categories, rather than neighborhoods with venues that reflect the syntax of common neighborhood types" (Description, 0067) and topics being "shared across all cities" (Description, 0068), are informed by Ghosh et al. This directly impacts how the "mix of venues for each cluster is emblematic of a neighborhood type" as recited in dependent claims, and thus potentially anticipates the broader clustering approach of the independent claims.
- Claim 3 (System for Sub-Region Clusters): The hierarchical modeling for shared typologies or patterns across different geographic groups would be highly relevant to clustering sub-regions, especially if the intent is to find common "region types" across different cities or larger areas. The concept of "sharing the neighborhood parameters across the cities" (Description, 0068) as taught by Ghosh et al. is crucial here.

3. "Exploring millions of footprints in location sharing services" by Cheng et al.

Full Citation: Cheng et al. (“Exploring millions of footprints in location sharing services,” AAAIICWSM, 2011)
Publication/Filing Date: 2011 (publication date).
Brief Description: This paper likely describes methods for extracting and analyzing check-in data from location-based social networks, such as Foursquare, which is used as a dataset in the experiments for US9846887.
Potential Anticipation (35 U.S.C. § 102): This reference primarily anticipates the source and type of data used in the patent, rather than the core clustering methodology.
- Claims 1, 2, and 3 (all claims): All independent claims rely on "venue check-in data from multiple venue visitors." Cheng et al. describes the collection and exploration of such data, specifically "11 million of these [Foursquare check-ins] were extracted from the data released by Cheng et al." (Description, 0073). This shows that the concept of using large-scale check-in data from location-based social services was known prior to US9846887.

4. "From deformations to parts: Motion-based segmentation of 3d objects" by Ghosh et al.

Full Citation: Ghosh et al. (“From deformations to parts: Motion-based segmentation of 3d objects,” Advances in Neural Information Processing Systems 25, pp. 2006-2014, 2012, incorporated herein by reference)
Publication/Filing Date: 2012 (publication date).
Brief Description: This paper focuses on 3D mesh segmentation using a ddCRP Gibbs sampler. While the application domain (image segmentation) is different from neighborhood clustering, the underlying algorithmic approach for inference is directly relevant.
Potential Anticipation (35 U.S.C. § 102): This reference anticipates the specific implementation of the Gibbs sampling algorithm for ddCRP, even if applied to a different data type.
- Claims 1, 2, and 3 (all claims): The patent explicitly states, "A MATLAB implementation of the above Gibbs sampling algorithm for posterior inference was used. It used portions of the ddCRP Gibbs sampler released by Ghosh et al. ('From deformations to parts: Motion-based segmentation of 3d objects,'... for 3D Mesh segmentation, which was modified and extended it to fit the hierarchical model)" (Description, 0075). This indicates that the core Gibbs sampling technique for ddCRP, a fundamental part of the clustering process in US9846887, was known prior to the patent's filing.