English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Temporal Index Sharding for Space-time Efficiency in Archive Search

Anand, A., Bedathur, S., Berberich, K., & Schenkel, R. (2011). Temporal Index Sharding for Space-time Efficiency in Archive Search. In W.-Y. Ma, J.-Y. Nie, R. A. Baeza-Yates, T.-S. Chua, & W. B. Croft (Eds.), SIGIR’11 (pp. 545-554). New York, NY: ACM. doi:10.1145/2009916.2009991.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0010-14C8-6 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-11CD-D
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Anand, Avishek1, Author           
Bedathur, Srikanta1, Author           
Berberich, Klaus1, Author           
Schenkel, Ralf1, Author           
Affiliations:
1Databases and Information Systems, MPI for Informatics, Max Planck Society, ou_24018              

Content

show
hide
Free keywords: -
 Abstract: Time-travel queries that couple temporal constraints with keyword queries are useful in searching large-scale archives of time-evolving content such as the Web, document collections, wikis, and so on. Typical approaches for efficient evaluation of these queries involve \emph{slicing} along the time-axis either the entire collection~\cite{253349}, or individual index lists~\cite{kberberi:sigir2007}. Both these methods are not satisfactory since they sacrifice compactness of index for processing efficiency making them either too big or, otherwise, too slow. We present a novel index organization scheme that \emph{shards} the index with \emph{zero increase in index size}, still minimizing the cost of reading index index entries during query processing. Based on the optimal sharding thus obtained, we develop practically efficient sharding that takes into account the different costs of random and sequential accesses. Our algorithm merges shards from the optimal solution carefully to allow for few extra sequential accesses while gaining significantly by reducing the random accesses. Finally, we empirically establish the effectiveness of our novel sharding scheme via detailed experiments over the edit history of the English version of Wikipedia between 2001-2005 ($\approx$ 700 GB) and an archive of the UK governmental web sites ($\approx$ 400 GB). Our results demonstrate the feasibility of faster time-travel query processing with no space overhead.

Details

show
hide
Language(s): eng - English
 Dates: 20112011
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 618955
DOI: 10.1145/2009916.2009991
URI: http://doi.acm.org/10.1145/2009916.2009991
Other: Local-ID: C1256DBF005F876D-CBF71516EA666361C125786F002D8E69-BedathurABS2011
 Degree: -

Event

show
hide
Title: 34th International ACM SIGIR Conference on Research and Development in Information Retrieval
Place of Event: Beijing, China
Start-/End Date: 2011-07-24 - 2011-07-28

Legal Case

show

Project information

show

Source 1

show
hide
Title: SIGIR’11
  Subtitle : Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval
  Abbreviation : SIGIR 2011
Source Genre: Proceedings
 Creator(s):
Ma, Wei-Ying1, Editor
Nie, Jian-Yun1, Editor
Baeza-Yates, Ricardo A.1, Editor
Chua, Tat-Seng1, Editor
Croft, W. Bruce1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: New York, NY : ACM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 545 - 554 Identifier: ISBN: 978-1-4503-0757-4