Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2017) | last year (2016) | two years ago (2015) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Anand, Avishek
Bedathur, Srikanta
Berberich, Klaus
Schenkel, Ralf

dblp
dblp
dblp
dblp

Not MPG Author(s):

Bedathur, Srikanta
Schenkel, Ralf

Editor(s):

Ma, Wei-Ying
Nie, Jian-Yun
Baeza-Yates, Ricardo A.
Chua, Tat-Seng
Croft, W. Bruce

dblp
dblp
dblp
dblp
dblp

Not MPII Editor(s):

Ma, Wei-Ying
Nie, Jian-Yun
Baeza-Yates, Ricardo A.
Chua, Tat-Seng
Croft, W. Bruce

BibTeX cite key*:

BedathurABS2011

Title, Booktitle

Title*:

Temporal Index Sharding for Space-Time Efficiency in Archive Search

Booktitle*:

SIGIR'11 : Proceedings of the 34th International ACM SIGIR Conference on
Research and Development in Information Retrieval

Event, URLs

URL of the conference:


URL for downloading the paper:

http://doi.acm.org/10.1145/2009916.2009991

Event Address*:

Beijing, China

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

24 July 2011

Event End Date:

28 July 2011

Publisher

Name*:

ACM

URL:


Address*:

New York, NY

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

545-554

Year*:

2011

VG Wort Pages:


ISBN/ISSN:

978-1-4503-0757-4

Sequence Number:


DOI:

10.1145/2009916.2009991



Note, Abstract, ©


(LaTeX) 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.



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Databases and Information Systems Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{BedathurABS2011,
AUTHOR = {Anand, Avishek and Bedathur, Srikanta and Berberich, Klaus and Schenkel, Ralf},
EDITOR = {Ma, Wei-Ying and Nie, Jian-Yun and Baeza-Yates, Ricardo A. and Chua, Tat-Seng and Croft, W. Bruce},
TITLE = {Temporal Index Sharding for Space-Time Efficiency in Archive Search},
BOOKTITLE = {SIGIR'11 : Proceedings of the 34th International ACM SIGIR Conference on
Research and Development in Information Retrieval},
PUBLISHER = {ACM},
YEAR = {2011},
PAGES = {545--554},
ADDRESS = {Beijing, China},
ISBN = {978-1-4503-0757-4},
DOI = {10.1145/2009916.2009991},
}


Entry last modified by Anja Becker, 02/21/2013
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
04/11/2011 10:17:35 AM
Revisions
3.
2.
1.
0.
Editor(s)
Anja Becker
Ralf Schenkel
Ralf Schenkel
Ralf Schenkel
Edit Dates
07.03.2012 14:18:58
17.08.2011 16:49:51
19.04.2011 13:12:21
11.04.2011 10:17:35
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section