Online querying of d-dimensional hierarchies

In this paper we describe a distributed system designed to efficiently store, query and update multidimensional data organized into concept hierarchies and dispersed over a network. Our system employs an adaptive scheme that automatically adjusts the level of indexing according to the granularity of the incoming queries, without assuming any prior knowledge of the workload. Efficient roll-up and drill-down operations take place in order to maximize the performance by minimizing query flooding. Updates are performed on-line, with minimal communication overhead, depending on the level of consistency needed. Extensive experimental evaluation shows that, on top of the advantages that a distributed storage offers, our method answers the vast majority of incoming queries, both point and aggregate ones, without flooding the network and without causing significant storage or load imbalance. Our scheme proves to be especially efficient in cases of skewed workloads, even when these change dynamically with time. At the same time, it manages to preserve the hierarchical nature of data. To the best of our knowledge, this is the first attempt towards the support of concept hierarchies in DHTs.

Research highlights
► First work to address the problem of hierarchical data search in DHT systems.
► HiPPIS allows the reorganization of the indexing structure in favor of resolving queries for the most popular data.
► It manages to preserve useful hierarchy-specific information, that hashing destroys.
► It allows for fast, on-line updates, with an overhead depending on the level of consistency needed by the application.
► HiPPIS proves particularly efficient with highly skewed data distributions, without inducing significant load or storage imbalance.