(will be inserted by the editor) A Distributed Spatial Index for Error-Prone Wireless Data Broadcast

Abstract Information is valuable to users when it is available not only at the right time but also at the right place. To support efficient location-based data access in wireless data broadcast systems, a distributed spa-tial index (called DSI) is presented in this paper. DSI is highly efficient because it has a linear yet fully dis-tributed structure that naturally shares links in differ-ent search paths. DSI is very resilient to the error-prone wireless communication environment because interrupted search operations based on DSI can be resumed eas-ily. It supports search algorithms for classical location-based queries such as window queries and kNN querie