Enabling Skip Graphs to Process K-Dimensional Range Queries in a Mobile Sensor Network
Gregory J. Brault, Christopher J. Augeri, Barry E. Mullins, Rusty O. Baldwin, Christopher B. Mayer · 2007
A skip graph is a resilient application-layer routing structure that supports range queries of distributed k-dimensional data. By sorting deterministic keys into groups based on locally computed random membership vectors, nodes in a standard skip graph can optimize range query performance in mobile networks such as unmanned aerial vehicle swarms. We propose a skip graph extension that inverts the key and membership vector roles and bases group membership on deterministic vectors derived from the z-ordering of k-dimensional data and sorting within groups is based on locally computed random keys.