A peer-to-peer design for spatial search system
2015 (English)Report (Other academic)
Information in networked systems often has spatial semantics: routers, sensors, or virtual machines have coordinates in a geographical or virtual space, for instance. In this paper, we propose a peer-to-peer design for a spatial search system that processes queries, such as range or nearest-neighbor queries, on spatial information cached on nodes inside a networked system. Key to our design is a protocol that creates a distributed index of object locations and adapts it to object and node churn. The index is build around the concept of minimum bounding rectangle to efficiently encode locations. We present a search protocol, which is based on an echo protocol that prunes the search space and performs query routing. Simulations show the efficiency of the protocol in pruning the search space, thereby reducing the protocol overhead. For many queries, the protocol efficiency increases with the network size and approaches that of an optimal protocol for large systems. The protocol overhead depends on the network topology and is lower if neighboring nodes are spatially close. In contrast to recent works in spatial databases, our design is bottom-up, which makes query routing network-aware and thus efficient in networked systems.
Place, publisher, year, edition, pages
Telecommunications Communication Systems
IdentifiersURN: urn:nbn:se:kth:diva-169107OAI: oai:DiVA.org:kth-169107DiVA: diva2:819983
QC 201506122015-06-112015-06-112015-06-12Bibliographically approved