An Indexing Method to Construct Unbalanced Layers for High-Dimensional Data in Mobile Environments

Abstract EN

A top-k query processing is widely used in many applications and mobile environments.

An index is used for efficient query processing and layer-based indexing methods are representative to perform the top-k query processing efficiently.

However, the existing methods have a problem of high index building time for multidimensional and large data; thus, it is difficult to use them.

In this paper, we proposed a new concept of constructing layer-based index, which is called unbalanced layer (UB-Layer).

The existing methods construct a layer as a balanced layer with outermost data and wrap the rest of the input data.

However, UB-Layer constructs a layer as an unbalanced layer that does not wrap the rest of the data.

To construct UB-Layer, we fist divide the dimension of the input data into divided-dimensional data and compute the convex hull in each divided-dimensional data.

And then, we combine divided-convex hull to build UB-Layer.

We also propose UB-SelectAttribute algorithm for dividing the dimension with major attributes.

We demonstrate the superiority of the proposed methods by the performance experiments.