QIAN Libing, JI Zhenzhou, FU Zhongchuan, WU Qianqian, SONG Guangjia. Pre-judgment and Incomplete Allocation Approach for Query Result Cache[J]. Chinese Journal of Electronics, 2016, 25(6): 1101-1108. doi: 10.1049/cje.2016.08.025
Citation: QIAN Libing, JI Zhenzhou, FU Zhongchuan, WU Qianqian, SONG Guangjia. Pre-judgment and Incomplete Allocation Approach for Query Result Cache[J]. Chinese Journal of Electronics, 2016, 25(6): 1101-1108. doi: 10.1049/cje.2016.08.025

Pre-judgment and Incomplete Allocation Approach for Query Result Cache

doi: 10.1049/cje.2016.08.025
Funds:  This work is supported by the National Natural Science Foundation of China (No.61472100).
  • Received Date: 2015-10-10
  • Rev Recd Date: 2016-05-04
  • Publish Date: 2016-11-10
  • Query result caching is a crucial technique employed in search engines, reducing the response time and load of the search engines. As search engines continuously update their indexes, the query results in long-lived cache entries may become stale. It is important to provide the refresh mechanism to enhance the degree of freshness of cached results. We present a pre-judgment approach to improve the freshness of the result cache and design an incomplete allocation algorithm. We introduce the query-Time-to-live (TTL) and term-TTL structure to pre-judge the result cache. The query-TTL is used to pre-check the likelihood of a cache hit and term-TTL is applied to maintain all terms of the latest posting list. For the cache structure, we design a Queue-Hash structure and develop the corresponding incomplete allocation algorithm. The preliminary results demonstrate that our approaches can improve the freshness of cached results and decrease processing overhead compared with no pre-judgment approaches.
  • loading
  • R. Baeza-Yates, A. Gionis, F. Junqueira, et al., "The impact of caching on search engines", Proc. of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Amsterdam, Netherlands, pp.183-190, 2007.
    R. Baeza-Yates, A. Gionis, F.P. Junqueira, et al., "Design tradeoffs for search engine caching", ACM Transactions on the Web (TWEB), Vol.2, No.4, pp.20-28, 2008.
    E.P. Markatos, "On caching search engine query results", Computer Communications, Vol.24, No.2, pp.137-143, 2001.
    Q. Gan and T. Suel, "Improved techniques for result caching in web search engines", Proc. of the 18th International Conference on World Wide Web, Madrid, Spain, pp.431-440, 2009.
    R. Baeza-Yate, F. Junqueira, V. Plachouras, et al., "Admission policies for caches of search engine results", String Processing and Information Retrieval, Berlin, Germany, pp.74-85, 2007.
    Y. Zeng, M. Jin and H. Luo, "LICA: A Segment-Popularity Based Caching Scheme in ICN", Acta Electronica Sinica, Vol.44, No.2, pp.358-364, 2016. (in Chinese)
    R. Lempel and S. Moran, "Optimizing result prefetching in web search engines with segmented indices", ACM Transactions on Internet Technology (TOIT), Vol.4, No.1, pp.31-59, 2004.
    H. Li, W.C. Lee, A. Sivasubramaniam, et al., "A hybrid cache and prefetch mechanism for scientific literature search engines", Proc. of the 7th International Conference on Web Engineering, Como, Italy, pp.121-136, 2007.
    N. Lester, J. Zobel and H.E. Williams, "In-place versus re-build versus re-merge: index maintenance strategies for text retrieval systems", Proc. of the 27th Australasian Conference on Computer Science, Sydney, Australia, Vol.26, pp.15-23, 2004.
    F.B. Sazoglu, B.B Cambazoglu, R. Ozcan, et al., "Strategies for setting time-to-live values in result caches", Proc. of the 22nd ACM International Conference on Conference on Information & Knowledge Management, Burlingame, USA, pp.1881-1884, 2013.
    R. Blanco, E. Bortnikov, F. Junqueira, et al., "Caching search engine results over incremental indices", Proc. of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval, Raleigh, USA, pp.82-89, 2010.
    X. Bai and F.P. Junqueira, "Online result cache invalidation for real-time web search", Proc. of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval, Portland, USA, pp.641-650, 2012.
    T. Fagni, R. Perego, F. Silvestri, et al., "Boosting the performance of web search engines: Caching and prefetching query results by exploiting historical usage data", ACM Transactions on Information Systems (TOIS), Vol.24, No.1, pp.51-78, 2006.
    X. Wu, C. Wu, B. Wang, et al., "Network View and Cognitive Mechanism for Virtual Network Resource Management Based Intelligent", Chinese Journal of Electronics, Vol.23, No.3, pp.574-578, 2014.
    Y. Tsegay, A. Turpin and J. Zobel, "Dynamic index pruning for effective caching", Proc. of the 16th ACM Conference on Conference on Information and Knowledge Management, New York, USA, pp.987-990, 2007.
    B.B. Cambazoglu, F.P. Junqueira, V. Plachouras V, et al., "A refreshing perspective of search engine caching", Proc of the 19th International Conference on World Wide Web, New York, USA, pp.181-190, 2010.
    R. Ozcan, I.S. Altingovde, B.B. Cambazoglu, et al., "Second chance: A hybrid approach for dynamic result caching and prefetching in search engines", ACM Transactions on the Web (TWEB), Vol.8, No.1, pp.3-22, 2013.
    W.B. Croft, D. Metzler and T. Strohman, Search Engines: Information Retrieval in Practice, Peason Education, New Jersey, USA, pp.36-44, 2010.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (188) PDF downloads(632) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return