Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Bast, Holger
Mortensen, Christian Worm
Weber, Ingmar

dblp
dblp
dblp

Not MPG Author(s):

Mortensen, Christian Worm

Editor(s):

Crestani, Fabio
Ferragina, Paolo
Sanderson, Mark

dblp
dblp
dblp

Not MPII Editor(s):

Crestani, Fabio
Ferragina, Paolo
Sanderson, Mark

BibTeX cite key*:

bastetal06spire

Title, Booktitle

Title*:

Output-Sensitive Autocompletion Search

Booktitle*:

String Processing and Information Retrieval : 13th International Conference, SPIRE 2006

Event, URLs

URL of the conference:

http://www.cis.strath.ac.uk/external/spire06/

URL for downloading the paper:

http://www.springerlink.com/content/98tp27415651q468/fulltext.pdf

Event Address*:

Glasgow, GB

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

11 October 2006

Event End Date:

13 October 2006

Publisher

Name*:

Springer

URL:


Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

4209

Number:


Month:


Pages:

150-162

Year*:

2006

VG Wort Pages:


ISBN/ISSN:

978-3-540-45774-9

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

We consider the following autocompletion search scenario: imagine a user of a search engine typing a query; then with every keystroke display those completions of the last query word that would lead to the best hits, and also display the best such hits. The following problem is at the core of this feature: for a fixed document collection, given a set D of documents, and an alphabetical range W of words, compute the set of all word-in-document pairs (w,d) from the collection such that w ∈W and d∈D. We present a new data structure with the help of which such autocompletion queries can be processed, on the average, in time linear in the input plus output size, independent of the size of the underlying document collection. At the same time, our data structure uses no more space than an inverted index. Actual query processing times on a large test collection correlate almost perfectly with our theoretical bound.

URL for the Abstract:

http://www.springerlink.com/content/98tp27415651q468/



Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

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



BibTeX Entry:

@INPROCEEDINGS{bastetal06spire,
AUTHOR = {Bast, Holger and Mortensen, Christian Worm and Weber, Ingmar},
EDITOR = {Crestani, Fabio and Ferragina, Paolo and Sanderson, Mark},
TITLE = {Output-Sensitive Autocompletion Search},
BOOKTITLE = {String Processing and Information Retrieval : 13th International Conference, SPIRE 2006},
PUBLISHER = {Springer},
YEAR = {2006},
VOLUME = {4209},
PAGES = {150--162},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Glasgow, GB},
ISBN = {978-3-540-45774-9},
}


Entry last modified by Uwe Brahm, 07/18/2007
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)
Ingmar Weber
Created
06/09/2006 12:07:57 PM
Revisions
7.
6.
5.
4.
3.
Editor(s)
Uwe Brahm
Uwe Brahm
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
2007-07-18 15:00:33
07/07/2007 00:46:52
05.02.2007 15:56:20
05.02.2007 15:45:37
09/30/2006 06:50:56 PM