An Efficient Method for Finding Similar Regions in a 2-Dimensional Array Data

KIPS Transactions on Software and Data Engineering, Vol. 6, No.4, pp.185-192, April 2017
10.3745/KTSDE.2017.6.4.185, Full Text

Abstract

In various fields of science, 2-dimensional array data is being generated actively as a result of measurements and simulations. Although various query processing techniques for array data are being studied, the problem of finding similar regions, whose sizes are not known in advance, in 2-dimensional array has not been addressed yet. Therefore, in this paper, we propose an efficient method for finding regions with similar element values, whose size is larger than a user-specified value, for a given 2-dimensional array data. The proposed method, for each pair of elements in the array, expands the corresponding two regions, whose initial size is 1, along the right and down direction in stages, keeping the shape of the two regions the same. If the difference between the elements values in the two regions becomes larger than a user-specified value, the proposed method stops the expansion. Consequently, the proposed method can find similar regions efficiently by accessing only those parts that are likely to be similar regions. Through theoretical analysis and various experiments, we show that the proposed method can find similar regions very efficiently.


Statistics

Show / Hide Statistics

Statistics (Cumulative Counts from October 15, 2016)

Multiple requests among the same browser session are counted as one view. If you mouse over a chart, the values of data points will be shown.


Cite this paper

[KIPS Transactions Style]
Y. Choe and K. Y. Lee, "An Efficient Method for Finding Similar Regions in a 2-Dimensional Array Data," KIPS Transactions on Software and Data Engineering, Vol.6, No.4, pp.185-192, 2017, DOI: 10.3745/KTSDE.2017.6.4.185.

[IEEE Style]
YeonJeong Choe and Ki Yong Lee, "An Efficient Method for Finding Similar Regions in a 2-Dimensional Array Data," KIPS Transactions on Software and Data Engineering, vol. 6, no. 4, pp. 185-192, 2017. DOI: 10.3745/KTSDE.2017.6.4.185.

[ACM Style]
Choe, Y. and Lee, K. Y. 2017. An Efficient Method for Finding Similar Regions in a 2-Dimensional Array Data. KIPS Transactions on Software and Data Engineering, 6, 4, (2017), 185-192. DOI: 10.3745/KTSDE.2017.6.4.185.