Spatial Search in Networked Systems
2015 (English)In: 2015 11TH INTERNATIONAL CONFERENCE ON NETWORK AND SERVICE MANAGEMENT (CNSM), IEEE conference proceedings, 2015, 327-335 p.Conference paper (Refereed)
Information in networked systems often has spatial properties: 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 to object and node churn. The indexbuilds upon the concept of the minimum bounding rectangle, to efficiently encode a large set of locations. We present a search protocol, which is based on an echo protocol 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. As a key difference to 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
IEEE conference proceedings, 2015. 327-335 p.
, International Conference on Network and Service Management, ISSN 2165-9605
network search, spatial search, distributed spatial index, distributed query processing
Engineering and Technology Telecommunications
Research subject Computer Science; Electrical Engineering
IdentifiersURN: urn:nbn:se:kth:diva-181035DOI: 10.1109/CNSM.2015.7367378ISI: 000379333700048ScopusID: 2-s2.0-84964043453OAI: oai:DiVA.org:kth-181035DiVA: diva2:897983
11th International Conference on Network and service management (CNSM), Barcelona, Spain, November 9-13, 2015.
QC 201602282016-01-272016-01-272016-08-12Bibliographically approved