Finding the Minimum MBRs Embedding K Points

Abstract

In the information-oriented society where data is exploding and flooding, it is almost impossible to manually extract information from data. By this reason, the study using computer to extract meaningful information from enormous data has been constantly researched. Especially, with the increase of supply rate of portable devices like smart-phones or tablets, the volume of data is expanded so much that even the classical database cannot manage it. To analyse this data grown to much so that classical database cannot even handle, the technologies called "The big data technology" began advance. One of the big data analysis is to gain useful information from analysing multi-dimensional data. Multi-dimensional data means the data which has many features, and there are already some examples of using valuable information extracted by this multi-dimensional data analysis. The typical example is that of the Amazon, called recommendation system which recommend products to consumer referring on the consumer's previous purchase list. And the US president Barack Obama was elected in the presidential election on 2008 by choosing elections strategies, based on the analysis of collected multi-dimensional data including many features like races, religions, ages, habitants. Like this, multi-dimensional data analysis can extract reasonable information, even if it's hard to know instinctively. There are many ways to extract useful data from multi-dimensional data. One of them is what called, the "Clustering".

Clustering is to gather some data which have some features in common into one class. By clustering, we can find some trend or tendency of data which is hard to be seen. There's many ways in clustering, but one of them is to find the place with dense data as one class. To be one class means gathering of similar data, and we can predict which feature the data has in the same class, by the others.

To search the data organizing the same class in multi-dimension, this paper suggests a method to find the most dense data set which includes data as the number of k in multi-dimension. What this paper suggests are these. First, the method to find the most dense area which includes data as the number of k in 2-dimensional space, next, improving the computational complexity of the method suggested above, last, the improved algorithm which can be also applied in multi-dimension.