UBI-Tree: Indexing Method for Schema-Less Search

We propose an indexing method called UBI-Tree for improving the efficiency of a new type of data search called schema-less search. Schema-less search is a multi-dimensional range search from a wide variety of data, such as sensor data, collected through participatory sensing. Such data have different types and number of dimensions because a participant uses various devices. Therefore, applications must search for their target data within the sensor data in a cross-schema manner. UBI-Tree is a tree-structured index based on R-Tree. The insert algorithm classifies various data into nodes according to newly introduced scores to estimate the inefficiency of classification. The score can uniformly represent the difference in the types of dimensions between data as well as the difference in dimension values. By classifying data that have a similar dimension set into the same node, UBI-Tree suppresses the curse of dimensionality and makes schema-less searches efficient. The validity of UBI-Tree was evaluated through experiments.