The International Arab Journal of Information Technology (IAJIT)


Skyline Recommendation in Distributed Networks

Skyline recommendation technology has recently received a lot of attention in the database community. However, the existing works mostly focus on how to obtain skyline objects from fine-grained data in centralized environments. And the time cost of skyline recommendation will increase exponentially as the number of data and skyline recommendation instructions increases, which will seriously influence the recommendation efficiency. Motivated by the above fact, this paper proposes an efficient algorithm Skyline Recommendation Algorithm in Distributed Networks (SRADN) in Super-Peer Architecture (SPA) distributed networks to handle multiple subspace skyline recommendations by prestoring the set of skyline snapshots under the cost constraint of maintenance and communication. The proposed SRADN algorithm fully considers the characteristic of storage and communication of SPA networks, and uses the map/reduce distributed computation model. The SRADN algorithm can quickly produce the optimal set of skyline snapshots through the following two phases: Heuristically constructing the initial set of snapshots, and adjusting the set of snapshots based on the genetic algorithm. The detailed theoretical analyses and extensive experiments demonstrate that the proposed SRADN algorithm is both efficient and effective.

[1] Afrati F. and Ullman J., Optimizing Multiway Joins in a Map-Reduce Environment, IEEE Transactions on Knowledge and Data Engineering, vol. 23, no. 9, pp. 1282-1298, 2011.

[2] Borzsonyi S., Kossmann D., and Stocker K., The Skyline Operator, in Proceeding of 17th International Conference on Data Engineering, Heidelberg, pp. 421-430, 2001.

[3] Chaudhuri S., Dalvi N., and Kaushik R., Robust Cardinality and Cost Estimation for Skyline Operator, in Proceeding of 22th International Conference on Data Engineering, Atlanta, pp. 1- Skyline Recommendation in Distributed Networks 379 10, 2006.

[4] Chen Q., Zhang Q., and Niu Z., A Graph Theory based Opportunistic Link Scheduling for Wireless Ad-Hoc Networks, IEEE Transactions on Wireless Communications, vol. 8, no. 10, pp. 5075-5085, 2009.

[5] Chomicki J., Godfrey P., Gryz J., and Liang D., Skyline with Presorting: Theory and Optimization, in Proceeding of 14th International Conference on Intelligent Information System, Oslo, pp. 593-602, 2005.

[6] Doulkeridis C., Vlachou A., N rv g K., Kotidis Y., and Vazirgiannis M., Multidimensional Routing Indices for Efficient Distributed Query Processing, in Proceeding of 18th ACM Conference on Information and Knowledge Management, Hong Kong, pp. 1489-1492, 2009.

[7] Gasse M., Aussem A., and Elghazel H., A hybrid Algorithm for Bayesian Network Structure Learning with Application to Multi-Label Learning, Expert Systems with Applications, vol. 41, no. 15, pp. 6755-6772, 2014.

[8] Godfrey P., Skyline Cardinality for Relational Processing, Springer Berlin Heidelberg, 2004.

[9] Huang Z., Guo J., Sun S., and Wang W., Efficient Optimization of Multiple Subspace Skyline Queries, Journal of Computer Science and Technology, vol. 23, no. 1, pp. 103-111, 2008.

[10] Huang Z., Sun S., and Wang W., Efficient mining of Skyline Objects in Subspaces Over Data Streams, Knowledge and Information Systems, vol. 22, no. 2, pp. 159-183, 2010.

[11] Huang Z., Xiang Y., Sun S., and Chen Q., Optimizing Skyline Queries in SPA Distributed Networks, Chinese Journal of Electronics, vol. 41, no. 8, pp. 1515-1520, 2013.

[12] Huang Z., Xiang Y., Zhang B., and Liu X., A Clustering based Approach for Skyline Diversity, Expert Systems with Applications, vol. 38, no. 7, pp. 7984-7993, 2011.

[13] Hu H., Xu J., Xu X., Pei K., Choi B., and Zhou S., Private Search on Key-Value Stores with Hierarchical Indexes, in Proceeding of 30th IEEE International Conference on Data Engineering, Chicago, pp. 628-639, 2014.

[14] Itmazi J. and Meg as M., Using Recommendation Systems in Course Management Systems to Recommend Learning Objects, The International Arab Journal for Information Technology, vol. 5, no. 3, pp. 234- 240, 2008.

[15] Pei J., Jiang B., Lin X., and Yuan Y., Probabilistic Skylines on Uncertain Data, in Proceeding of 33rd International Conference on Very Large Data Bases, Vienna, pp. 15-26, 2007.

[16] Pospiech S., Mielke S., Mertens R., Pelke M., Jagannath K., and Stadler M., Exploration and Analysis of Undocumented Processes using Heterogeneous and Unstructured Business Data, in Proceeding of International Conference on Semantic Computing, Newport Beach, pp. 191-198, 2014.

[17] Rodrigo C., Gaspar F., and Lisbona F., Multigrid Methods on Semi-Structured Grids, Archives of Computational Methods in Engineering, vol. 19, no. 4, pp. 499-538, 2012.

[18] Trimponias G., Bartolini I., Papadias D., and Yang Y., Skyline Processing on Distributed Vertical Decompositions, IEEE Transactions on Knowledge and Data Engineering, vol. 25, no. 4, pp. 850-862, 2013.

[19] Vlachou A., Doulkeridis C., Kotidis Y., and Vazirgiannis M., SKYPEER: Efficient Subspace Skyline Computation over Distributed Data, in Proceeding of 23th International Conference on Data Engineering, Istanbul, pp. 416-425, 2007.

[20] Xu X. and Song M., Restricted Coverage in Wireless Networks, in Proceeding of International Conference on Computer Communications, London, pp. 558-564, 2014.

[21] Zhang N., Li C., Hassan N., Rajasekaran S., and Das G., On Skyline Groups, IEEE Transactions on Knowledge and Data Engineering, vol. 26, no. 4, pp. 942-956, 2014.

[22] Zhang Q., Fu H., and Qiu G., Tree Partition Voting Min-Hash for Partial Duplicate Image Discovery, in Proceeding of International Conference on Multimedia and Expo, San Jose, pp. 1-6, 2013.

[23] Zhang W., Zhang S., Qi F., and Cai M., Self- Organized P2P Approach to Manufacturing Service Discovery for Cross-Enterprise Collaboration, IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 44, no. 3, pp. 263-276, 2014. Zhenhua Huang is currently an associate professor at the School of Electronics and Information, Tongji University. He received his PhD. degree in computer science from Fudan University. His research interests include information service, data mining and knowledge discovery. He has published over 50 papers in various journals and conference proceedings. Jiawen Zhang received her BSc degree in computer science from Tongji University. She is currently a MSc student at Tongji University. She has authored a number of journal and conference papers in the fields of data mining, query optimization and information recommendation.