A survey of spatial data structures and their applications

Chas Emerick (http://cemerick.com & http://twitter.com/cemerick) presents a survey of metric and spatial data structures, guided by the book 'Foundations of Multidimensional and Metric Data Structures' by Hanan Samet, with particular details on two data structures and their papers:

• 'Corner Stitching: A Data-Structuring Technique for VLSI Layout Tools' by Ousterhout, (https://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/CSD-83-114.pdf)
• 'R-trees: A Dynamic Index Structure for Spatial Searching' by Guttman,(https://klevas.mif.vu.lt/~algis/DSA/guttman.pdf)

Abstract

Most of us are familiar with the notion of indexes thanks to databases, but that exposure belies the rich kaleidoscope of techniques available to provide efficient representations of how objects and entities relate to each other or to the space that they occupy. Disciplines as varied as computer graphics, GIS, gaming, bioinformatics, and document analysis and layout have their own unique demands and data modeling requirements which have driven the development of hundreds of different ways to "index" their respective data. This presentation will touch on a dozen different such approaches, sketching out their strengths and tradeoffs and common applications, all Samet's encyclopedic survey of the field. We'll also do deeper dives into a couple of the papers it cites that describe data structures you indirectly rely upon every day via mapping services and digital circuit design and fabrication.

The meetup

PapersWeLove (http://paperswelove.org) London proudly brings to you the best papers every month! Please join us to read and discuss the most amazing ideas in computer science. We meet at ZPG (https://www.uswitch.com/about-us/contact-us/) offices near Tower Bridge (https://goo.gl/maps/qJXZek4fMNU2) with the following schedule:

• 6.30pm: networking, pizza and drinks.
• 7:00pm: presentation starts

The Speaker

Chas Emerick (http://cemerick.com & http://twitter.com/cemerick) is a software engineer who has been building systems to analyze and consume PDF documents for 15 years, now with PDFDATA.io
(https://www.PDFDATA.io). His other interests include compilers, programming language theory, distributed systems, database implementation, future computing of all sorts, circuit design via FPGAs,
ethics in technology, and radical politics.