Change search
ReferencesLink to record
Permanent link

Direct link
Spatial Search in Networked Systems
KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre. KTH, School of Electrical Engineering (EES), Communication Networks.
KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre. KTH, School of Electrical Engineering (EES), Communication Networks.
Cisco.
2015 (English)In: 2015 11TH INTERNATIONAL CONFERENCE ON NETWORK AND SERVICE MANAGEMENT (CNSM), IEEE conference proceedings, 2015, 327-335 p.Conference paper (Refereed)
Abstract [en]

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.
Series
, International Conference on Network and Service Management, ISSN 2165-9605
Keyword [en]
network search, spatial search, distributed spatial index, distributed query processing
National Category
Engineering and Technology Telecommunications
Research subject
Computer Science; Electrical Engineering
Identifiers
URN: urn:nbn:se:kth:diva-181035DOI: 10.1109/CNSM.2015.7367378ISI: 000379333700048ScopusID: 2-s2.0-84964043453OAI: oai:DiVA.org:kth-181035DiVA: diva2:897983
Conference
11th International Conference on Network and service management (CNSM), Barcelona, Spain, November 9-13, 2015.
Note

QC 20160228

Available from: 2016-01-27 Created: 2016-01-27 Last updated: 2016-08-12Bibliographically approved
In thesis
1. A Bottom-Up Approach to Real-Time Search in Large Networks and Clouds
Open this publication in new window or tab >>A Bottom-Up Approach to Real-Time Search in Large Networks and Clouds
2016 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Networked systems, such as telecom networks and cloud infrastructures, generate and hold vast amounts of conguration and operational data. The goal of this work is to make all this data available through a real-time search process named network search , which will enable new real-time management solutions. The thesis contains several contributions towards engineering a network search system. Key elements of our design are a weakly structured information model that includes spatial properties, a query language that supports location- and schema-oblivious search queries, a peer-to-peer architecture, a set of echo protocols for scalable query processing, and an indexing protocol for ecient routing for spatial queries. The data against which network search is performed is maintained in local real-time databases close to the data sources. The design follows a bottom-up approach in the sense that the topology for query routing is constructed from the underlying network topology. We have built a prototype of the system on a cloud testbed and developed applications that use network search functionality. Testbed measurements suggest that it is feasible to engineer a network search system that processes queries at low latency and low overhead and that can scale to 100'000 nodes. Simulation results for spatial queries show that query processing achieves response times and incurs overhead close to an optimal protocol, and that query result remains accurate under signicant churn.

Place, publisher, year, edition, pages
Stockholm: Kungliga Tekniska högskolan, 2016. 122 p.
Series
TRITA-EE, ISSN 1653-5146 ; 2016:012
National Category
Communication Systems Telecommunications
Research subject
Electrical Engineering
Identifiers
urn:nbn:se:kth:diva-184236 (URN)978-91-7595-858-3 (ISBN)
Public defence
2016-05-03, F3, Lindstedtsvägen 26, våningsplan 2, Sing-Sing, KTH Campus, Stockholm, 09:30 (English)
Opponent
Supervisors
Note

QC 20160411

Available from: 2016-04-11 Created: 2016-03-31 Last updated: 2016-04-11Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Uddin, MisbahStadler, Rolf
By organisation
ACCESS Linnaeus CentreCommunication Networks
Engineering and TechnologyTelecommunications

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

Altmetric score

Total: 5 hits
ReferencesLink to record
Permanent link

Direct link