Journal Home > Volume 1 , issue 2

A lot of scholars have focused on developing effective techniques for package queries, and a lot of excellent approaches have been proposed. Unfortunately, most of the existing methods focus on a small volume of data. The rapid increase in data volume means that traditional methods of package queries find it difficult to meet the increasing requirements. To solve this problem, a novel optimization method of package queries (HPPQ) is proposed in this paper. First, the data is preprocessed into regions. Data preprocessing segments the dataset into multiple subsets and the centroid of the subsets is used for package queries, this effectively reduces the volume of candidate results. Furthermore, an efficient heuristic algorithm is proposed (namely IPOL-HS) based on the preprocessing results. This improves the quality of the candidate results in the iterative stage and improves the convergence rate of the heuristic algorithm. Finally, a strategy called HPR is proposed, which relies on a greedy algorithm and parallel processing to accelerate the rate of query. The experimental results show that our method can significantly reduce time consumption compared with existing methods.


menu
Abstract
Full text
Outline
About this article

HPPQ: A Parallel Package Queries Processing Approach for Large-Scale Data

Show Author's information Meihui ShiDerong Shen( )Tiezheng NieYue KouGe Yu
College of Computer Science and Engineering, Northeastern University, Shenyang 110000, China.

Abstract

A lot of scholars have focused on developing effective techniques for package queries, and a lot of excellent approaches have been proposed. Unfortunately, most of the existing methods focus on a small volume of data. The rapid increase in data volume means that traditional methods of package queries find it difficult to meet the increasing requirements. To solve this problem, a novel optimization method of package queries (HPPQ) is proposed in this paper. First, the data is preprocessed into regions. Data preprocessing segments the dataset into multiple subsets and the centroid of the subsets is used for package queries, this effectively reduces the volume of candidate results. Furthermore, an efficient heuristic algorithm is proposed (namely IPOL-HS) based on the preprocessing results. This improves the quality of the candidate results in the iterative stage and improves the convergence rate of the heuristic algorithm. Finally, a strategy called HPR is proposed, which relies on a greedy algorithm and parallel processing to accelerate the rate of query. The experimental results show that our method can significantly reduce time consumption compared with existing methods.

Keywords:

package queries, heuristic algorithms, parallel processing, opposition-based learning
Received: 08 January 2018 Accepted: 11 January 2018 Published: 12 April 2018 Issue date: June 2018
References(23)
[1]
M. Brucato, J. F. Beltran, A. Abouzied, and A. Meliou, Scalable package queries in relational database systems, Proc. VLDB Endow., vol. 9, no. 7, pp. 576-587, 2016.
[2]
M. De Choudhury, M. Feldman, S. Amer-Yahia, N. Golbandi, R. Lempel, and C. Yu, Automatic construction of travel itineraries using social breadcrumbs, in Proc. 21st ACM Conf. Hypertext and Hypermedia, Toronto, Canada, 2010, pp. 35-44.
[3]
M. Xie, L. V. S. Lakshmanan, and P. T. Wood, Breaking out of the box of recommendations: From items to packages, in Proc. 4th ACM Conference on Recommender Systems, Barcelona, Spain, 2010, pp. 151-158.
[4]
A. Parameswaran, P. Venetis, and H. Garcia-Molina, Recommendation systems with complex constraints: A course recommendation perspective, ACM Trans. Inf. Syst., vol. 29, no. 4, p. 20, 2011.
[5]
T. Lappas, K. Liu, and E. Terzi, Finding a team of experts in social networks, in Proc. 15th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, Paris, France, 2009, pp. 467-476.
[6]
A. Baykasoglu, T. Dereli, and S. Das, Project team selection using fuzzy optimization approach, Cybern. Syst., vol. 38, no. 2, pp. 155-185, 2007.
[7]
M. Brucato, R. Ramakrishna, A. Abouzied, and A. Meliou, PackageBuilder: From tuples to packages, Proc. VLDB Endow., vol. 7, no. 13, pp. 1593-1596, 2014.
[8]
Y. D. Cui, A new dynamic programming procedure for three-staged cutting patterns, J. Global Optim., vol. 55, no. 2, pp. 349-357, 2013.
[9]
T. Meng and Q. K. Pan, An improved fruit fly optimization algorithm for solving the multidimensional knapsack problem, Appl. Soft Comput., vol. 50, pp. 79-93, 2017.
[10]
Z. L. Guo, S. W. Wang, X. Z. Yue, and H. G. Yang, Global harmony search with generalized opposition-based learning, Soft Comput., vol. 21, no. 8, pp. 2129-2137, 2017.
[11]
R. Sarkhel, T. M. Chowdhury, M. Das, N. Das, and M. Nasipuri, A novel harmony search algorithm embedded with metaheuristic opposition based learning, J. Intell. Fuzzy Syst., vol. 32, no. 4, pp. 3189-3199, 2017.
[12]
M. I. Andreica, A dynamic programming framework for combinatorial optimization problems on graphs with bounded pathwidth, arXiv preprint arXiv: 0806.0840, 2008.
[13]
Q. Louveaux and S. Mathieu, A combinatorial branch-and-bound algorithm for box search, Discrete Optim., vol. 13, pp. 36-48, 2014.
[14]
E. I. Hsu and S. A. McIlraith, Computing equivalent transformations for combinatorial optimization by branch-and-bound search, in Proc. 3rd Annual Symposium on Combinatorial Search, Atlanta, GA, USA, 2010.
[15]
B. Haddar, M. Khemakhem, S. Hanafi, and C. Wilbaut, A hybrid quantum particle swarm optimization for the multidimensional knapsack problem, Eng. Appl. Artif. Intell., vol. 55, pp. 1-13, 2016.
[16]
Y. H. Feng, K. Jia, and Y. C. He, An improved hybrid encoding cuckoo search algorithm for 0-1 knapsack problems, Comput. Intell. Neurosci., vol. 2014, p. 970456, 2014.
[17]
A. Rezoug and D. Boughaci, A self-adaptive harmony search combined with a stochastic local search for the 0-1 multidimensional knapsack problem, Int. J. Bio-Inspired Comput., vol. 8, no. 4, pp. 234-239, 2016.
[18]
Z. W. Geem, J. H. Kim, and G. V. Loganathan, A new heuristic optimization algorithm: Harmony search, Simulation, vol. 76, no. 2, pp. 60-68, 2001.
[19]
M. Mahdavi, M. Fesanghary, and E. Damangir, An improved harmony search algorithm for solving optimization problems, Appl. Math. Comput., vol. 188, no. 2, pp. 1567-1579, 2007.
[20]
M. G. H. Omran and M. Mahdavi, Global-best harmony search, Appl. Math. Comput., vol. 198, no. 2, pp. 643-656, 2008.
[21]
Q. K. Pan, P. N. Suganthan, M. F. Tasgetiren, and J. J. Liang, A self-adaptive global best harmony search algorithm for continuous optimization problems, Appl. Math. Comput., vol. 216, no. 3, pp. 830-848, 2010.
[22]
D. X. Zou, L. Q. Gao, J. H. Wu, and S. Li, Novel global harmony search algorithm for unconstrained problems, Neurocomputing, vol. 73, nos. 16-18, pp. 3308-3318, 2010.
[23]
X. Z. Gao, X. Wang, S. J. Ovaska, and K, Zenger, A hybrid optimization method of harmony search and opposition-based learning, Eng. Optimiz., vol. 44, no. 8, pp. 895-914, 2012.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 08 January 2018
Accepted: 11 January 2018
Published: 12 April 2018
Issue date: June 2018

Copyright

© The author(s) 2018

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Nos. 61472070 and 61672142).

Rights and permissions

Reprints and Permission requests may be sought directly from editorial office.

Return