We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Ying-Yuan Xiao, Yue-Guo Chen. Efficient Distributed Skyline Queries for Mobile Applications[J]. Journal of Computer Science and Technology, 2010, 25(3): 523-536.
Citation: Ying-Yuan Xiao, Yue-Guo Chen. Efficient Distributed Skyline Queries for Mobile Applications[J]. Journal of Computer Science and Technology, 2010, 25(3): 523-536.

Efficient Distributed Skyline Queries for Mobile Applications

Funds: This work is supported by the Natural Science Foundation of Tianjin under Grant No. 08JCYBJC12400, the Innovative Foundation of Small and Medium Enterprises under Grant No. 08ZXCXGX15000, the National High-Technology Research and Development 863 Program of China under Grant No. 2009AA01Z152 and the National Natural Science Foundation of China under Grant No. 60872064.
More Information
  • Author Bio:

    Ying-Yuan Xiao received the B.Sc. degree in mathematics fromHunan Normal University, Changsha, China in 1991, the M.Sc. degree incomputer science from Wuhan University, Wuhan, China in 1999, and thePh.D. degree in computer science from Huazhong University of Scienceand Technology, Wuhan, China in 2005. He is currently an associateprofessor in the School of Computer Science and Technology at TianjinUniversity of Technology. He is a senior member of China ComputerFederation. His research interests include real-time informationprocessing, advanced databases and Web data management. He has publishedover 60 journal and conference papers in these areas. He also served as apublicity chair or session chair in some inter-national conferences. Atpresent, he is a visiting scholar in School of Computing of NationalUniversity of Singapore.

    Yue-Guo Chen received the B.Sc. and M.Sc. degrees in mechanicalengineering and control engineering from Tsinghua University, Beijing,in 2001 and 2004, and Ph.D. degree in computer science from NationalUniversity of Singapore in 2009. He is an assistant professor in theKey Laboratory of Data Engineering and Knowledge Engineering, RenminUniversity of China. His research interests include spatial temporaldata management, data driven computer games, and community informationmanagement. He has published some papers in international conferences,including ICDE, EDBT and DASFAA.

  • Received Date: June 07, 2009
  • Revised Date: February 11, 2010
  • Published Date: May 04, 2010
  • In this paper, we consider skyline queries in a mobile and distributed environment, where data objects are distributed in some sites (database servers) which are interconnected through a high-speed wired network, and queries are issued by mobile units (laptop, cell phone, etc.) which access the data objects of database servers by wireless channels. The inherent properties of mobile computing environment such as mobility, limited wireless bandwidth, frequent disconnection, make skyline queries more complicated. We show how to efficiently perform distributed skyline queries in a mobile environment and propose a skyline query processing approach, called efficient distributed skyline based on mobile computing (EDS-MC). In EDS-MC, a distributed skyline query is decomposed into five processing phases and each phase is elaborately designed in order to reduce the network communication, network delay and query response time. We conduct extensive experiments in a simulated mobile database system, and the experimental results demonstrate the superiority of EDS-MC over other skyline query processing techniques on mobile computing.
  • [1]
    Formanand G, Zahorjan J. The challenges of mobile computing. IEEE Computer, 1994, 27(4): 38-47.
    [2]
    Imielinski T, Badrinath B. Wireless mobile computing: Challenges in data management. Communications of the ACM, 1994, 37(10): 18-28.
    [3]
    Sashidhar G, Vijay K. Recovery in the mobile wireless environment using mobile agents. IEEE Transactions on Mobile Computing, 2004, 3(2): 180-191.
    [4]
    Tao Y, Xiao X, Pei J. SUBSKY: Efficient computation of skylines in subspaces. In Proc. ICDE, Atlanta, USA, Apr. 3-8, 2006, pp.711-720.
    [5]
    Chan C Y, Jagadish H V, Tan K L et al. Finding k-dominant skylines in high dimensional space. In Proc. SIGMOD, Chicago, Illinois, June 27-29, 2006, pp.503-514.
    [6]
    Chan C Y, Jagadish H V, Tan K L et al. On high dimensional skylines. In Proc. EDBT, Munich, Germany, Mar. 26-31, 2006, pp.478-495.
    [7]
    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.
    [8]
    Morese M, Patel J M, Jagadish H V. Efficient skyline computation over low-cardinality domains. In Proc. VLDB, Vienna, Austria, Sept. 23-27, 2007, pp.267-278.
    [9]
    Stephan B, Donald K, Konrad S. The skyline operator. In Proc. ICDE, Heidelberg, Germany, Apr. 2-6, 2001, pp.421430.
    [10]
    Chomicki J, Godfrey P et al. Skyline with presorting. In Proc. ICDE, Bangalore, India, Mar. 5-8, 2003, pp.717-719.
    [11]
    Tan K L, Eng P K, Ooi B C et al. Efficient progressive skyline computation. In Proc. ICDE, Heidelberg, Germany, Apr. 2-6, 2001, pp.301-310.
    [12]
    Lee K, Zheng B, Li H et al. Approaching the skyline in z order. In Proc. VLDB, Vienna, Austria, Sept. 23-27, 2007, pp.279-290.
    [13]
    Papadias D, Tao Y, Greg F et al. An optimal and progressive algorithm for skyline queries. In Proc. SIGMOD, San Diego, USA, June 9-12, 2003, pp.467-478.
    [14]
    Papadias D, Tao Y, Greg F et al. Progressive skyline computation in database systems. ACM Transactions on Database Systems, 2005, 30(1): 41-82.
    [15]
    Chaudhuri S, Dalvi N, Kaushik R. Robust cardinality and cost estimation for skyline operator. In Proc. ICDE, Atlanta, GA, Apr. 3-8, 2006, pp.64-73.
    [16]
    Huang Z H, Guo J K, Sun S L et al. Efficient optimization of multiple subspace skyline queries. Journal of Computer Science and Technology, 2008, 23(1): 103-111.
    [17]
    Pei J, Jiang B, Lin X et al. Probabilistic skylines on uncertain data. In Proc. VLDB, Vienna, Austria, Sept. 23-27, 2007, pp.15-26.
    [18]
    Sharifzadeh M, Shahabi C. The spatial skyline query. In Proc. VLDB, Seoul, Korea, Sept. 12-15, 2006, pp.751-762.
    [19]
    Deng K, Zhou X, Shen H T. Multi-source skyline query processing in road networks. In Proc. ICDE, Istanbul, Turkey, Apr.15-20, 2007, pp.796-805.
    [20]
    Zhu L, Tao Y, Zhou S G. Distributed skyline retrieval with low bandwidth consumption. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(3): 384-400.
    [21]
    Huang Z, Jensen C S, Lu H et al. Skyline queries against mobile lightweight devices in MANETs. In Proc. ICDE, Atlanta, USA, Apr. 3-8, 2006, pp.66-77.
    [22]
    Wang S, Ooi B C, Tung A K H et al. Efficient skyline query processing on peer-to-peer networks. In Proc. ICDE, Istanbul, Turkey, Apr. 15-20, 2007, pp.1126-1135.
    [23]
    Wu P, Zhang C, Feng Y et al. Parallelizing skyline queries for scalable distribution. In Proc. EDBT, Munich, Germany, Mar. 26-31, 2006, pp.112-130.
    [24]
    Hose K, Lemke C, Sattler K U et al. Processing relaxed skylines in PDMS using distributed data summaries. In Proc. CIKM, Arlington, USA, Nov. 6-11, 2006, pp.425-434.
    [25]
    Vlachou A, Doulkeridis C, Kotidis Y et al. Skypeer: Efficient subspace skyline computation over distributed data. In Proc. ICDE'07, Istanbul, Turkey, Apr. 15-20, 2007, pp.416-425.
    [26]
    Balke W T, Guntzer U, Zheng J X. Efficient distributed skyline forWeb information systems. In Proc. EDBT, Heraklion, Greece, Mar. 14-18, 2004, pp.256-273.
    [27]
    Eric L, Kevin Y Y, Lin K et al. Progressive skylining over Web-accessible databases. Data & Knowledge Engineering, 2006, 57(2): 122-147.
  • Related Articles

    [1]Lei Zhao, Yan-Yan Yang, Xiaofang Zhou. Continuous Probabilistic Subspace Skyline Query Processing Using Grid Projections[J]. Journal of Computer Science and Technology, 2014, 29(2): 332-344. DOI: 10.1007/s11390-014-1434-9
    [2]Jin Huang, Feng Zhao, Jian Chen, Jian Pei, Jian Yin. Towards Progressive and Load Balancing Distributed Computation: A Case Study on Skyline Analysis[J]. Journal of Computer Science and Technology, 2010, 25(3): 431-443.
    [3]Zhen-Hua Huang, Jian-Kui Guo, Sheng-Li Sun, Wei Wang. Efficient Optimization of Multiple Subspace Skyline Queries[J]. Journal of Computer Science and Technology, 2008, 23(1): 103-111.
    [4]WANG Chen, ZHANG Defu, ZHOU Ying. A Framework of Auto-Adapting Distributed Object for Mobile Computing[J]. Journal of Computer Science and Technology, 1999, 14(6): 590-598.
    [5]Matthew Hennessy. Process Calculifor Describing Distributed Systems[J]. Journal of Computer Science and Technology, 1998, 13(6): 490.
    [6]Zhou Aoying, Shi Baile. Query Optimization for Deductive Databases[J]. Journal of Computer Science and Technology, 1995, 10(2): 134-148.
    [7]Li Jianzhong. Range Query Processing in Multidisk Systems[J]. Journal of Computer Science and Technology, 1992, 7(4): 316-327.
    [8]Jin Zhiquan, Liu Chengfei, Sun Zhongxiu, Zhou Xiaofang, Chen Peipei, Gu Jianming. Design and Implementation of a Heterogeneous Distributed Database System[J]. Journal of Computer Science and Technology, 1990, 5(4): 363-373.
    [9]Liu Weiyi. An Efficient Algorithm for Processing Multi-Relation Queries in Relational Databases[J]. Journal of Computer Science and Technology, 1990, 5(3): 236-240.
    [10]Wang Hanhu. Transaction Management in Distributed Database System POREL[J]. Journal of Computer Science and Technology, 1988, 3(2): 139-146.

Catalog

    Article views (25) PDF downloads (1850) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return