Pre-judgment and Incomplete Allocation Approach for Query Result Cache

QIAN Libing; JI Zhenzhou; FU Zhongchuan; WU Qianqian; SONG Guangjia

doi:10.1049/cje.2016.08.025

Volume 25 Issue 6

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2016 > 25(6): 1101-1108

QIAN Libing, JI Zhenzhou, FU Zhongchuan, et al., “Pre-judgment and Incomplete Allocation Approach for Query Result Cache,” Chinese Journal of Electronics, vol. 25, no. 6, pp. 1101-1108, 2016, doi: 10.1049/cje.2016.08.025

Citation:

QIAN Libing, JI Zhenzhou, FU Zhongchuan, et al., “Pre-judgment and Incomplete Allocation Approach for Query Result Cache,” Chinese Journal of Electronics, vol. 25, no. 6, pp. 1101-1108, 2016, doi: 10.1049/cje.2016.08.025

Citation:

PDF( 564 KB)

Pre-judgment and Incomplete Allocation Approach for Query Result Cache

doi: 10.1049/cje.2016.08.025

School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China

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

Abstract

Abstract

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.
- Time-to-live(TTL),
- Caching freshness,
- Pre-judgment,
- Result cache,
- Cache structure

FullText(HTML)

References(18)

References

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.

Relative Articles

Supplements(0)

Cited By

Proportional views