Conflation Aggregator

[nknize]

Overview

GeoDistance search achieves the most basic spatial search use-case for "Find all points of interest within R units of known location X". This is great when the starting location is already known (e.g., cell phone GPS, travelling location of interest) but doesn't work for conflation use-cases such as: "Find all CVS Pharmacies that are within 1 mile of a Walgreens pharmacy? Or all Home Depot's that are within 2 blocks of a Lowes?" (After all, competition is essential to a free enterprise economy). The current search toolbox (query, filter, aggregations, reducer, percolator) doesn't lend itself well to these types of queries without writing a bit of complex scripting.

This feature will add - what we'll temporarily call - a ConflationAggregator. The purpose of this aggregator is to achieve the above use case. A primary aggregator defines the primary list of buckets (e.g., Home Depots). A list of secondary <filter, aggregator, query> defines the operation or post-filter to perform using the documents in the result set of the primary.

Conflation Aggregation Structure

Below is an initial cut at the colocation grammar. There can be one-to-many secondary filters to achieve multi-conflation queries, such as: "Find all Home Depots within 10 miles of a Lowes or Ace Hardware". The design is intended to be flexible enough to avoid limiting this aggregation to geo only queries.

"aggs" : {
  "<aggregation_name"> : {
    "conflation" : {
      "primary" : {
        "<filter> | <parent aggregation>"
      },
      "secondary" : [
        "<secondary_name>" : {
          "<filter> | <child aggregation>"
        }
      ]
    } 
  }
}

Example

Query

This is an initial rough idea on how to use the conflation aggregator to achieve a complex geodistance query like: "Find all Home Depots that are within 10 miles of a Lowes"

{
  "query": {"match_all": {}}, 
  "aggs": {
    "HomeDepots" : {
      "conflation" : {
        "primary" : {
          "filter" : {
            "bool" : {
              "must" : [
                {"term" : {"name" : "Home Depot"}},
                {"term" : {"businessType": "Home Improvement"}}
              ]
            }
          }
        },
        "secondary": [
          "Lowes": {
            "filter": {
              "and" : {
                "filters" : [
                  "term" : {"name" : "Lowes"},
                  "geo_distance": {
                    "field": "location",
                    "origin_field": "HomeDepots.location",
                    "ranges": [
                      {"from" : 0, "to" : 10}
                    ]
                  }
                ]
              } 
            }
          }
        ]
      }
    }
  }
}

Result

"aggregations": {
  "HomeDepots": {
     "buckets": [
        {
           "key" : "Home Depot",
           "id" : 1034,
           "doc_count": 2
        },
        {
           "key" : "Home Depot",
           "id" : 3432,
           "doc_count": 2
        },
        {
           "key" : "Home Depot",
           "id" : 5644,
           "doc_count": 1
        },
        {
           "key" : "Home Depot",
           "id" : 8999,
           "doc_count": 1
        },
        {
           "key" : "Home Depot",
           "id" : 10232,
           "doc_count": 2
        }
     ]
  }
}

This issue is open for discussion around use-cases (non-geo), design, naming, etc.

[clintongormley]

Hi @nknize

This sounds exciting, but I don't see how it can work in a distributed environment in a scalable way? Surely all nodes need to share all location data to get accurate results?

[nknize]

@clintongormley performance is certainly the primary concern. In a way this is a multi (potentially exponential) query wrapped in aggregator clothing so it would need to be limited to small use cases. That may make the feature DOA? I'm not sure. That's why I'm super interested in soliciting feedback from everyone on ideas for providing easy-to-use tools for accomplishing these types of common use-cases.

[markharwood]

Presumably in this "find an X near a Y" we are starting with the assumption that X and Y are both different elasticsearch documents?
As Clinton points out the initial problem is that the various X and Y docs may be scattered across different shards.
It feels like a two step op -

1. query the X docs and use a geohashgrid agg or similar to build a geo-mask
2. query the Y docs and use the mask from 1 as a filter

[clintongormley]

@nknize yeah - we avoid adding features that don't scale horizontally, eg see the discussion on #3278 about the potential meltdown of cross-shard joins

[nknize]

@markharwood That's basically the idea. The problem with using a grid is that there aren't overlaps. i.e. There may be two Home Depots whose radius buffer overlap, and 1 Lowes falls within the criteria distance for both (i.e. falls in that venn overlap) So the mask would probably be something along the lines of a boolean 'OR' of geo_distance filters created from step 1. Do we run the risk of cluster thrashing in this case?

@colings86 pointed to SignificantLongTerms as a possible reference implementation for something like this.

[markharwood]

Sounds like 2 options for representation of the Home Depot coverage from step 1:
a) A full set of points from which you can later compute radius buffers (good for accuracy, bad if millions of points)
b) A form of multi-polygon that describes the union of the radius buffers (good if a lot of overlaps, bad for overall accuracy).

The multi-polygon in b) would not necessarily be a single-resolution grid but a set of geohashes or similar with variable resolution.

Not sure about the SignificantLongTerms connection?

[colings86]

The reference to SignificantLongTerms was the ability to go back and query the index again in the combine phase on each shard but I hadn't thought about the fact that unlike significant terms (which relies on the assumption that the background stats on the shard are representative of the complete index) in this case you may not have all the information on the shard to be able to find all the hits.

[clintongormley]

So the mask would probably be something along the lines of a boolean 'OR' of geo_distance filters created from step 1. Do we run the risk of cluster thrashing in this case?

If this could be represented as some constant-size data structure, regardless of how many documents/geo-points are involved, then it would work and be scalable. If it requires recording every geo-point, then cluster thrashing would indeed ensue...

[markharwood]

It started to feel like an image compression problem to me - accuracy and space required are based on:

1. The resolution (number of pixels) you want to spend describing a landscape and
2. The aggressiveness of the compression algorithms that bundle nearby similar items into blocks of the same colour

[mikemccand]

This is sort of like a geo-spatial MoreLikeThis query...

[xandyj]

You may already be planning this, but I'd like to note that it would be useful if this ConflationAggregator would be generalized so that it could support not only geospatial but also temporal correlation. Also, it would be useful for it to support nesting.