Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
2015.
National Category
Telecommunications Communication Systems
Identifiers
URN: urn:nbn:se:kth:diva-169107OAI: oai:DiVA.org:kth-169107DiVA: diva2:819983
Note

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

urn-nbn

Altmetric score

urn-nbn
Total: 77 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf