Multidimensional range queries on hierarchical Voronoi overlays

Luca Ferrucci, Laura Ricci*, Michele Albano, Ranieri Baraglia, Matteo Mordacchini

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

10 Citations (Scopus)

Abstract

The definition of a support for multi-attribute range queries is mandatory for highly distributed systems. Even if several solutions have been proposed in the last decade, most of them do not meet the requirements of recent platforms, like IoT or smart cities. The paper presents an approach that builds a multidimensional Voronoi graph by exploiting the attributes of the objects published by a node. Our solution overcomes the curse of dimensionality issue affecting Voronoi Tessellations in high dimensional spaces by defining a Voronoi hierarchy. The paper formally defines the structure, analysis the complexity of the operations and presents experimental results.

Original languageEnglish
JournalJournal of Computer and System Sciences
Volume82
Issue number7
Pages (from-to)1161-1179
Number of pages19
ISSN0022-0000
DOIs
Publication statusPublished - 1 Nov 2016
Externally publishedYes

Keywords

  • Distributed systems
  • Range queries
  • Voronoi

Fingerprint

Dive into the research topics of 'Multidimensional range queries on hierarchical Voronoi overlays'. Together they form a unique fingerprint.

Cite this