The empty bin: A data structure for spatial search of time‐varying data
Rainald Löhner · Communications in Numerical Methods in Engineering · 2006
Abstract An extension of the classic bin data structure with linked list storage is proposed and tested. This ‘empty‐bin’ data structure is particularly well suited for problems where spatial search is required for items that: (a) do not change significantly in numbers; (b) have similar size; and (c) move a fraction of the bin size in every timestep. This ‘empty‐bin’ data structure can be updated and rebalanced efficiently on shared‐memory parallel machines. Several examples demonstrate the effectiveness of the proposed data structure. Copyright © 2006 John Wiley & Sons, Ltd.