Data Structures the Fun Way: An Amusing Adventure with Coffee-Filled Examples by Jeremy Kubica

Author:Jeremy Kubica [Kubica, Jeremy]
Language: eng
Format: epub
ISBN: 9781718502611
Published: 2022-08-18T00:00:00+00:00

Why This Matters

Nearest-neighbor search allows us to find points that are “close” to some target value, whether spatial or non-spatial. From an algorithmic point of view, nearest-neighbor search moves us from searching for an exact target to searching based on distance metrics. The details of search get more complex as we step away from one-dimensional data sets into the realm of multidimensional data. As we saw with the shift from arrays to grids, this extension opens a range of new questions in terms of how we organize and search the data. It’s no longer possible to consider a simple ordering, as we did with a binary search for one-dimensional data. We need to adapt our data structures to a new type of multidimensional structure. Grids provide a new way to structure data based on aggregating points within the same spatial regions into the same bin.

At the same time, grids illustrate a different structure than the one-bucket, one-value structure we have seen with arrays. Grids use linked-list or other internal data structures to store multiple values per bin, a technique we will reuse in future chapters. By using this structure, grids also introduce a new tradeoff to consider—the size of the bins. By increasing the size of the bins, we can shift cost from evaluating many small bins to scanning through a large number of points per bin. Choosing the right number of bins is an example of the common task of tuning our data structure for the specific problem at hand.

In the next chapter, we’ll take spatial partitioning further by combining the adaptive properties of trees with the spatial properties of grids. In doing so, we’ll address some of the major drawbacks of grids—and make the search for a good cup of coffee significantly more efficient.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.