• Article
  • | |
  • Metrics
  • |
  • Reference [23]
  • |
  • Related
  • | | |
  • Comments
    Abstract:

    This paper proposes a multi-query optimization algorithm for pipeline-based distributed similarity query processing (pGMSQ) in grid environment. First, when a number of query requests are simultaneously submitted by users, a cost-based dynamic query clustering (DQC) is invoked to quickly and effectively identify the correlation among the query spheres (requests). Then, index-support vector set reduction is performed at data node level in parallel. Finally, refinement of the candidate vectors is conducted to get the answer set at the execution node level. By adopting pipeline-based technique, this algorithm is experimentally proved to be efficient and effective in minimizing the response time by decreasing network transfer cost and increasing the throughput.

    Reference
    [1] Sellis TK. Multi-Query optimization. ACM Trans. on Database Systems, 1988,13(1):23?52.
    [2] B?hm C, Berchtold S, Keim D. Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases. ACM Computing Surveys, 2001,33(3):322?373.
    [3] Guttman A. R-Tree: A dynamic index structure for spatial searching. In: Yormark B, ed. Proc. of the ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD’84). 1984. 47?54.
    [4] Beckmann N, Kriegel HP, Schneider R, Seeger B. The R*-tree: An efficient and robust access method for points and rectangles. In: Garcia-Molina H, Jagadish HV, eds. Proc. of the ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD 2000). 1990. 322?331.
    [5] Ratnasamy S, Francis P, Handley M, Karp R, Shenker S. A scalable content-addressable network. In: Proc. of the ACM SIGCOMM Int’l Conf. on Data Communication (SIGCOMM). 2001. 161?172.
    [6] Aspnes J, Shah G. Skip graphs. In: Proc. of the ACM-SIAM Symp. on Discrete Algorithms. 2003. 384?393.
    [7] Smith J, Gounaris A, Watson P, Paton NW, Fernandes AAA, Sakellariou R. Distributed query processing on the grid. In: Proc. of the 3rd Int’l Workshop on Grid Computing. Berlin: Springer-Verlag, 2002. 279?290.
    [8] Jagadish HV, Ooi BC, Tan KL, Yu C, Zhang R. iDistance: An adaptive B+-tree based indexing method for nearest neighbor search. ACM Trans. on Data Base Systems, 2005,2(30):364?397.
    [9] Berchtold S, Bohm C, Braunmuller B, Keim DA, Kriegel HP. Fast parallel similarity search in multimedia databases. In: Peckham J, ed. Proc. of the ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD’97). 1997. 1?12.
    [10] Papadopoulos AN, Manolopoulos Y. Similarity query processing using disk arrays. In: Haas LM, Tiwary A, eds. Proc. of the ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD’98). 1998. 225?236.
    [11] Weber R, Schek H, Blott S. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In: Gupta A, Shmueli O, Widom J, eds. Proc. of the Int’l Conf. on Very Large Databases (VLDB’98). 1998. 194?205.
    [12] Lee J, Lee H, Kang S, Choe S, Song J. CISS: An efficient object clustering framework for DHT-based peer-to-peer applications. In: Proc. of the DBISP2P. 2004. 215?229.
    [13] Tang C, Xu Z, Dwarkadas S. Peer-to-Peer information retrieval using self-organizing semantic overlay networks. In: Proc. of the ACM SIGCOMM Int’l Conf. on Data Communication (SIGCOMM). 2003.
    [14] Sahin OD, Gupta A, Agrawal D, Abbadi AE. A peer-to-peer framework for caching range queries. In: Proc. of the IEEE Int’l Conf. on Data Engineering (ICDE 2004). 2004.
    [15] Zhang C, Krishnamurthy A, Wang RY. Skipindex: Towards a scalable peer-to-peer index service for high dimensional data. Technical Report, TR-703-04, Princeton University, 2004.
    [16] Kalnis P, Ng WS, Ooi BC, Tan KL. Answering similarity queries in peer-to-peer networks. Information Systems, 2006,31(1): 57?72.
    [17] Segal B. Grid computing: The European data grid project. In: Proc. of the 2000 IEEE Nuclear Science Symp. and Medical Imaging Conf. Lyon, 2000.
    [18] Hoschek W, Jaen-Martinez J, Samar A, Stockinger H, Stockinger K. Data management in an international data grid project. In: Proc. of the 1st IEEE/ACM Int’l Workshop on Grid Computing. Berlin: Springer-Verlag, 2001. 17?20.
    [19] Yang DH, Li JZ, Zhang WP. Grid-Based join operation. Journal of Computer Research and Development, 2004,41(10):1848?1855 (in Chinese with English abstract).
    [20] Zhuang Y, Li Q, Chen L. Multi-Query optimization for distributed similarity query processing. In: Proc. of the IEEE Int’l Conf. on Distributed Computing Systems (ICDCS 2008). 2008. 639?646.
    [21] Shen HT, OOi BC, Zhou XF, Huang Z. Towards effective indexing for very large video sequence database. In: ?zcan F, ed. Proc. of the 24th ACM SIGMOD Int’l Conf. on Management of Data (SIGMOD). 2005. 730?741.
    [22] UCI KDD Archive. 2002. http://www.kdd.ics.uci.edu
    附中文参考文献: [19] 杨东华,李建中,张文平.基于数据网格环境的连接操作算法.计算机研究与发展,2004,41(10):1848?1855.
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

胡华,庄毅,胡海洋,赵格华.网格环境下基于流水线的多重相似查询优化.软件学报,2010,21(1):55-67

Copy
Share
Article Metrics
  • Abstract:7041
  • PDF: 7052
  • HTML: 0
  • Cited by: 0
History
  • Received:June 05,2008
  • Revised:February 24,2009
You are the first2049976Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063