ReSKY: Efficient Subarray Skyline Computation in Array Databases

Abstract

Large-scale spatial data have been generated in various fields such as scientific domains and location-based services. Array databases, which model a space as an array, have become one of the means of managing such spatial data. Each cell in an array tends to interact with cells neighboring with regard to dimensions (such as latitude and longitude); therefore, instead of considering a single cell, considering a concept of subarray is required in some applications. In addition, each cell has several attribute values (such as temperature and price) to indicate its features. Based on the two observations, we propose a new type of query, subarray skyline, that provides a way to find meaningful subarrays or filter less meaningful subarrays considering attributes. We also introduce an efficient processing method, ReSKY, for subarray skyline query processing. To handle large-scale spatial data, we extend ReSKY to distributed processing. We also propose another version of ReSKY that reduces memory usage during query processing. Through extensive experiments using an array database and real datasets, we show that ReSKY has better performance than the existing techniques.