2013 DynamicMemoryAllocationPolicies

• (Asadi et al., 2013) ⇒ Nima Asadi, Jimmy Lin, and Michael Busch. (2013). “Dynamic Memory Allocation Policies for Postings in Real-time Twitter Search.” In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ISBN:978-1-4503-2174-7 doi:10.1145/2487575.2488221

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222013%22+Dynamic+Memory+Allocation+Policies+for+Postings+in+Real-time+Twitter+Search
• http://dl.acm.org/citation.cfm?id=2487575.2488221&preflayout=flat#citedby

Quotes

Author Keywords

• Information search and retrieval; inverted indexing; memory allocation

Abstract

We explore a real-time Twitter search application where tweets are arriving at a rate of several thousands per second. Real-time search demands that they be indexed and searchable immediately, which leads to a number of implementation challenges. In this paper, we focus on one aspect: dynamic postings allocation policies for index structures that are completely held in main memory. The core issue can be characterized as a “Goldilocks Problem ". Because memory remains today a scare resource, an allocation policy that is too aggressive leads to inefficient utilization, while a policy that is too conservative is slow and leads to fragmented postings lists. We present a dynamic postings allocation policy that allocates memory in increasingly-larger” slices " from a small number of large, fixed pools of memory. With an analytical model and experiments, we explore different settings that balance time (query evaluation speed) and space (memory utilization).

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2013 DynamicMemoryAllocationPolicies	Jimmy Lin Nima Asadi Michael Busch			Dynamic Memory Allocation Policies for Postings in Real-time Twitter Search				10.1145/2487575.2488221		2013