›› 2010, Vol. 25 ›› Issue (3): 431-443.

Special Issue: Computer Networks and Distributed Computing

• Special Section on Trends Changing Data Management • Previous Articles     Next Articles

Towards Progressive and Load Balancing Distributed Computation: A Case Study on Skyline Analysis

Jin Huang1 (黄晋), Feng Zhao2 (赵丰), Jian Chen2,* (陈健), Member, CCF, Jian Pei3 (裴健), Senior Member, ACM, IEEE, and Jian Yin1(印鉴), Senior Member, CCF   

  1. 1School of Information Science and Technology, Sun Yat-Sen University, Guangzhou 510275, China
    2School of Software Engineering, South China University of Technology, Guangzhou 510006, China
    3School of Computing Science, Simon Fraser University, British Columbia, V5A 1S6, Canada
  • Received:2009-11-03 Revised:2009-12-09 Online:2010-05-05 Published:2010-05-05
  • About author:
    Jin Huang is a Ph.D. candidate at School of Information Science and Technology, Sun Yat-Sen University, China. He received his M.Sc. degree in software engineering from Sun Yat-Sen University in 2004. His current research interests cover distributed computing, database, and data mining.
    Feng Zhao received his B.Sc. degree in computer science from the School of Computer Science and Technology, South China University of Technology, Guangzhou, China, in 2008. His current research interests include skyline query, probabilistic database and data mining.
    Jian Chen received her B.S., and Ph.D. degrees, both in computer science, from Sun Yat-Sen University, China, in 2000 and 2005 respectively. She joined the School of Software Engineering of South China University of Technology (SCUT) as an assistant professor in 2005, and at present she is an associate professor and director of the Data Mining Group in School of Software Engineering, SCUT. Her research interests can be summarized as developing effective and efficient data analysis techniques for complex data and the related applications. Since 2005, she has served as PC member of PAKDD2009, CIKM2009, ADMA2009, etc. Her research has been supported in part by the National Natural Science Foundation of China, Natural Science Foundation of Guangdong Province (China), the Natural Science Key Program of Higher Education Institutions of Guangdong Province and Hewlett-Packard Company (HP), etc. She is a member of China Computer Federation.
    Jian Pei received his Ph.D. degree in computing science from Simon Fraser University, Canada, in 2002. He is currently the associate director (research) and an associate professor at School of Computing Science, Simon Fraser University. His research interests can be summarized as developing effective and efficient data analysis techniques for novel data intensive applications. Particularly, he is currently interested in various techniques of data mining, Web search, information retrieval, data warehousing, online analytical processing, and database systems, as well as their applications in social networks, health-informatics, business and bioinformatics. He has published prolifically in refereed journals, conferences, and workshops. He is an associate editor of ACM Transactions on Knowledge Discovery from Data (TKDD) and IEEE Transactions of Knowledge and Data Engineering (TKDE). He has served regularly in the organization committees and the program committees of many international conferences and workshops. He is a senior member of ACM and IEEE. He is the recipient of several prestigious awards.
    Jian Yin received the B.S., M.S., and Ph.D. degrees from Wuhan University, China, in 1989, 1991, and 1994, respectively, all in computer science. He joined Sun Yat-Sen University in July 1994 and now he is a professor in Information Science and Technology School. He has published more than 100 papers in refereed journals and conferences. His current research interests are in the areas of data mining, artificial intelligence, and machine learning. He is a senior member of China Computer Federation.
  • Supported by:

    Supported by the Doctoral Research Foundation of the Natural Science Foundation of Guangdong Province under Grant No. 8451064101000054, the National Natural Science Foundation of China under Grant Nos. 60773198, 60703111, Natural Science Foundation of Guangdong Province under Grant Nos. 06104916, 8151027501000021, Research Foundation of Science and Technology Plan Project in Guangdong Province under Grant No. 2008B050100040, Program for New Century Excellent Talents in University of China under Grant No. NCET-06-0727, and the Fundamental Research Funds for the Central Universities, SCUT, under Grant No. 2009ZM0008.

PDF

2167

Many latest high performance distributed computational environments come with high bandwidth in communication. Such high bandwidth distributed systems provide unprecedented opportunities for analyzing huge datasets, but simultaneously posts new technical challenges. For users, progressive query answering is important. For utility of systems, load balancing is critical. How we can achieve progressive and load balancing distributed computation is an interesting and promising research direction. As skyline analysis has been shown very useful in many multi-criteria decision making applications, in this paper, we study the problem of progressive and load balancing distributed skyline analysis. We propose a simple yet scalable approach which comes with several nice properties for progressive and load balancing query answering. We conduct extensive experiments which demonstrate the feasibility and effectiveness of the proposed method.


[1] Borzsonyi S, Kossmann D, Stocker K. The skyline operator. In Proc. ICDE 2001, Heidelberg, Germany, April 2-6, 2001, pp.421-430.

[2] Lee K C K, Zheng B, Li H, Lee W. Approaching the skyline in Z-order. In Proc. VLDB2007, Vienna, Austria, Sept. 23-27, 2007, pp.279-290.

[3] Ratnasamy S, Francis P, Handley M, Karp R, Schenker S. A scalable content addressable network. In Proc. SIGCOMM, San Diego, USA, Aug. 27-31, 2001, pp.161-172.

[4] Chomicki J, Godfrey P, Gryz J, Liang D. Skyline with presorting. In Proc. ICDE 2003, Bangalore, India, Mar. 5-8, 2003, pp.816-825.

[5] Godfrey P, Shipley R, Gryz J. Maximal vector computation in large data sets. In Proc. VLDB2005, Trondheim, Norway, Aug. 30-Sept. 2, 2005, pp.229-240.

[6] Kossmann D, Ramsak F, Rost S. Shooting stars in the sky: An online algorithm for skyline queries. In Proc. VLDB, Hong Kong, China, Aug. 20-23, 2002, pp.275-286.

[7] Papadias D, Tao Y, Fu G, Seeger B. An optimal and progressive algorithm for skyline queries. In Proc. SIGMOD2003, San Diego, USA, June 9-12, 2003, pp.467-478.

[8] Wu P, Zhang C, Feng Y, Zhao B, Agrawal D, Abbadi E. Parallelizing skyline queries for scalable distribution. In Proc. EDBT2006, Munich, Germany, Mar. 26-31, 2006, pp.112-130.

[9] Wang S, Vu Q, Ooi B C, Tung A K H, Xu L. Skyframe: A framework for skyline query processing in peer-to-peer systems. VLDB Journal, 2009, 18(1): 345-362.

[10] Balke W, Guntzer U, Zheng J. Efficient distributed skylining for Web information systems. In Proc. EDBT2004, Heraklion, Greece, Mar. 14-18, 2004, pp.256-273.

[11] Cui B, Lu H, Xu Q, Chen L, Dai Y, Zhou Y. Parallel distributed processing of constrained skyline queries byfiltering. In Proc. ICDE 2008, Cancun, Mexico, Apr. 7-12, 2008, pp.546-555.

[12] Guttman A. R-trees: A dynamic index structure for spatial searching. In Proc. SIGMOD1984, Boston, USA, Jun. 18-21, 1984, pp.47-57.

[13] Fagin R, Lotem A, Naor M. Optimal aggregation algorithms for middleware. In Proc. ACM Symp. Principles of Database Systems, Santa Barbara, USA, May 21-23, 2001, pp.102-113.

[14] Wang S, Ooi B C, Tung A K H, Xu L. Efficient skyline query processing on peer-to-peer networks. In Proc. ICDE 2007, Istanbul, Turkey, April 15-20, 2007, pp.1126-1135.

[15] Li H, Tan Q, Lee W C. Efficient progressive processing of skyline queries in peer-to-peer systems. In Proc. INFOSCALE2006, Hong Kong, China, May 2006.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved