Spatial Search Tricks for People Who Don't Have Spatial Data

Chris Hostetter

2013-01-17 MeetUp

@_hossman

http://people.apache.org/~hossman/

http://lucene.apache.org/solr/

Intro: Solr4 Spatial

http://wiki.apache.org/solr/SolrAdaptersForLuceneSpatial4

Index Multiple Points Or Shapes Per Document
Query Using Shapes To Find Intersections (or Distances From Points)

<field name="zone"> POLYGON((9 33, 41 42, 35 4, 11 23, 2 15)) </field>

q = zone:"Intersects(10 15 22 30)"

Modeling Data With Coordinates

Spatial Search Is Designed For Geographic Data/Queries
Works On Sphere, Works Faster On A Plane
Can Be Used With Any Data You Can Model Into 2 Dimensional Coordinates

Time Duration Data

Semi-Common Problems

Easy...

Find People Alive On May 25, 1977
Find Reservations That Overlap With The Scheduled Pool Maintence June 20-25

Hard...

Find Restraunts Open Now
Find Hotels With Availability March 10-17

Area Intersections To The Rescue!

Index (Multiple) Durrations As (Multiple) Points
- X = "Start"
- Y = "End"
Query Using Rectangles Defined in Various Ways
- Document Durration Contains Query Durration
  q=fieldX:"Intersects(-∞ end start ∞)"
- Document Durration Overlaps Query Durration
  q=fieldX:"Intersects(-∞ start end ∞)"
- Document Durration Within Query Durration
  q=fieldX:"Intersects(start -∞ ∞ end)"

The big caveat here is that -∞ and ∞ are not actually supported, you must have lower and upper bounds on your coordinate space.

Example

Totally Realistic Government Usecase

Top Secret Wormhole To A Distant Galaxy
Research Base In An Alien City
Personnel Scheduled To Be Off-Earth On Sporadic Multi-Day Shifts
Want To Query For Personnel Based On Shift Schedule

There is a demo directory with solr configs and sample data for this example.

Data Model

Each Person Is A Document
Each Shift Is A Point In A Multivalued Spatial Field
- X Axis: When Shift Starts
- Y Axis: When Shift Ends

Sample Data

<doc> <field name="id">1</field> <field name="name">Adam Anderson</field> <field name="rank">6</field> <field name="dept">astronomy</field> <field name="shift">1 3</field> <field name="shift">5 7</field> <field name="shift">10 15</field> ...

Sample Data

Diagram generated using a gnuplot script.

Query: Contains

Personnel on shift continuously from Jan8-9

"Find the senior astronomers on shift during the next alien eclipse to put them in chage of the project to observe it."

q = shift:"Intersects(0 9 8 365)" fq = dept:astronomy sort = rank asc rows = 1

Query URL using the provided demo files.

Query: Contains

Diagram generated using a gnuplot script.

Query: Overlaps

Personnel on shift sometime overlapping Jan19-23

"Email blast everyone who will be on duty during the alien overloard's diplomatic visit reminding them to be on their best behavior."

q = shift:"Intersects(0 19 23 365)"

Query URL using the provided demo files.

Query: Overlaps

Diagram generated using a gnuplot script.

Query: Within

People on duty for some period starting after Jan6 and ending by Jan10

"Find someone to courier these time sensitive treaty documents; they must be taken to the alien capital after the president signs them, and the response needs to be brought back before the next UN summit."

q = shift:"Intersects(6 0 365 10)" sort = rank asc

Query URL using the provided demo files.

Query: Within

Diagram generated using a gnuplot script.

Conclusions

THINK

Credit

Big Thanks to David Smiley And Ryan McKinley For All Of The Great Lucene/Solr Spatial Work
Inspiration For This Durration Modeling Idea Thanks To Geert-Jan And David Smiley
Awesome Use Case Scnerio Idea Was All Me

This durration modeling as coordinates idea originated in a solr-user@lucene thread. See David's initial response to Geert-Jan's question and the subsequent followup about using differnt rectangle intersections.