Efficient column-oriented processing for mutual subspace skyline queries
- PDF / 2,451,120 Bytes
- 19 Pages / 595.276 x 790.866 pts Page_size
- 97 Downloads / 189 Views
(0123456789().,-volV) (0123456789().,-volV)
METHODOLOGIES AND APPLICATION
Efficient column-oriented processing for mutual subspace skyline queries Tao Jiang1 • Bin Zhang1 • Dan Lin2 • Yunjun Gao3 • Qing LI4
Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract A mutual skyline query will enable some new applications, such as marketing analysis, task allocation, and personalized matching. Algorithms for efficient processing of this query have been recently proposed in the literature. Those approaches use the R-tree indexes and apply a series of pruning criteria toward efficient processing. However, they are characterized by several limitations: (1) they cannot process different interests on attributes for skyline and reverse skyline, (2) they require a multidimensional index, which suffers from performance degradation, especially in high-dimensional space, and (3) they do not support vertically decomposed data that is a natural and intuitive choice for the parallel queries. To this end, we address aforementioned these problems and propose three efficient algorithms, i.e., index-based mutual subspace skyline, optimized index-based MSS, and parallel mutual subspace skyline, using the column-oriented processing that is more suitable for subspace and parallel skyline. Extensive experimental results show that our proposed algorithms are effective and efficient. Keywords Subspace Mutual skyline queries Algorithm Spatial database
1 Introduction Communicated by V. Loia. & Tao Jiang [email protected] Bin Zhang [email protected] Dan Lin [email protected] Yunjun Gao [email protected] Qing LI [email protected] 1
College of Mathematics Physics and Information Engineering, Jiaxing University, 56 Yuexiu Road (South), Jiaxing 314001, People’s Republic of China
2
Department of Computer Science, Missouri University of Science and Technology, 500West 15th Street, Rolla, MO 65409, USA
3
College of Computer Science, Zhejiang University, 38 Zheda Road, Hangzhou 310027, People’s Republic of China
4
Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong, People’s Republic of China
The skyline (Borzsonyi et al. 2001) and its variants (Jiang et al. 2014, 2015) are a popular query operator for multiple criteria decision making and have fostered a large number of applications, such as market analysis (Li et al. 2006), environmental surveillance (Lian and Chen 2010), trip planning and disaster management (Jiang et al. 2015), and community finding (Li et al. 2018). Recently, there has been an interesting skyline query variant, called mutual skyline (Jiang et al. 2014) which retrieves both skyline and reverse skyline (Dellis and Seeger 2007) objects of a query object q. For example, consider a profile-based investment service, where B is a set of stocks and A is a set of customer profiles. The dimensions are different properties of stocks, such as risk (on the scale from 0 to 1), volatility, and daily turnover. A mutual skyline query of q [ B returns the stocks p [ B
Data Loading...
