A bottom‐up design for spatial search in large networks and clouds. Issue 6 (22nd August 2018)

• Record Type: Journal Article
• Authors: Uddin, Misbah; Stadler, Rolf; Clemm, Alexander
• Is Part Of: International journal of network management. Volume 28:Issue 6(2018)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2018-08-22
• Subjects: Computer networks -- Management -- Periodicals; 004.6
• DOI: 10.1002/nem.2041
• Languages: English
• ISSNs: 1055-7148

Abstract

Summary: 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 design for a spatial search system that processes queries against spatial information that is maintained in local databases inside a large networked system. In contrast to previous works in spatial databases and peer‐to‐peer designs, our design is bottom‐up, which makes query routing network aware and thus efficient, and which facilitates system bootstrapping and adaptation. Key to our design is a protocol that creates and maintains a distributed index of object locations based on information from local databases and the underlying network topology. The index builds upon minimum bounding rectangles to efficiently encode locations. We present a generic search protocol that is based on an echo protocol and uses the index to prune the search space and perform query routing. The response times of search queries increase with the diameter of the network, which is asymptotically optimal. We study the performance of the protocol through simulation in static and dynamic network environments, for different network topologies, and for network sizes up to 100 000 nodes. In most experiments, the overhead incurred by our protocol lies well below 30% of a hypothetical optimal protocol. In addition, the protocol provides high accuracy under significant churn. Abstract : We propose a bottom‐up design for a spatial search system that processes queries against spatial information. We introduce a protocol that creates and maintains a distributed index of object locations, built upon minimum bounding rectangles, and a generic search protocol that is based on an echo protocol and uses the index to prune the search space and to perform query routing. Simulation studies for static and dynamic environments suggest that these protocols and the overall system are highly scalable.