Change search
ReferencesLink to record
Permanent link

Direct link
A peer-to-peer design for spatial search system
KTH, School of Electrical Engineering (EES), Communication Networks.
KTH, School of Electrical Engineering (EES), Communication Networks. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
Cisco Systems, Inc..
2015 (English)Report (Other academic)
Abstract [en]

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
National Category
Telecommunications Communication Systems
URN: urn:nbn:se:kth:diva-169107OAI: diva2:819983

QC 20150612

Available from: 2015-06-11 Created: 2015-06-11 Last updated: 2015-06-12Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Uddin, MisbahStadler, Rolf
By organisation
Communication NetworksACCESS Linnaeus Centre
TelecommunicationsCommunication Systems

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 65 hits
ReferencesLink to record
Permanent link

Direct link