Abstract. We point out that for two sets of measurements, it can happen that the average of one set is larger than the average of the other set on one scale, but becomes smaller after a non-linear...
Towards Peer-to-Peer Web Search (Extended Abstract) (2008)
Gerhard Weikum, Holger Bast, Geoffrey Canright, David Hales, Christian Schindelhauer, Peter Triantafillou
The peer-to-peer (P2P) computing paradigm is an intriguing alternative to Google-style search engines for querying and ranking Web content. In a network with many thousands or millions of peers the...
ABSTRACT When You’re Lost for Words: Faceted Search with Autocompletion (2008)
In this paper, we show how the autocompletion data structure of [2] can be used to answer faceted-search queries efficiently. Specifically, we have built a fully-functional browserbased search engine...
ABSTRACT Why Spectral Retrieval Works (2008)
We argue that the ability to identify pairs of related terms is at the heart of what makes spectral retrieval work in practice. Schemes such as latent semantic indexing (LSI) and its descendants have...
Towards Self-Organizing Query Routing and Processing for Peer-to-Peer Web Search (2008)
Gerhard Weikum, Holger Bast, Geoffrey Canright, David Hales, Christian Schindelhauer, Peter Triantafillou
peer-to-peer systems, probabilistic and statistical methods, semantic overlay networks, self-organization, Web search. The peer-to-peer computing paradigm is an intriguing alternative to Google-style...
TopX: Efficient and versatile top-k query processing for semistructured data (2008)
Martin Theobald, Holger Bast, Debapriyo Majumdar, Ralf Schenkel Gerhard, Martin Theobald, Holger Bast, ...
Abstract Recent IR extensions to XML query languages such as Xpath 1.0 Full-Text or the NEXI query language of the INEX benchmark series reflect the emerging interest in IR-style ranked retrieval...
Semantic Full-Text Search with ESTER: Scalable, Easy, Fast (2008)
Bast, Holger, Suchanek, Fabian, Weber, Ingmar
We present a demo of ESTER, a search engine that combines the ease of use, speed and scalability of full-text search with the powerful semantic capabilities of ontologies. % ESTER supports full-text...
TopX: Efficient and Versatile Top-k Query Processing for Semistructured Data (2008)
Theobald, Martin, Bast, Holger, Majumdar, Debapriyo, Schenkel, Ralf, Weikum, Gerhard
Recent IR extensions to XML query languages such as Xpath 1.0 Full-Text or the NEXI query language of the INEX benchmark series reflect the emerging interest in IR-style ranked retrieval over...
Ester: efficient search on text, entities, and relations (2007)
Holger Bast, Alexandru Chitea, Fabian Suchanek, Ingmar Weber
We present ESTER, a modular and highly efficient system for combined full-text and ontology search. ESTER builds on a query engine that supports two basic operations: prefix search and join. Both of...
ESTER: efficient search on Text, Entities, and Relations (2007)
Bast, Holger, Chitea, Alexandru, Suchanek, Fabian M., Weber, Ingmar
We present ESTER, a modular and highly efficient system for combined full-text and ontology search. ESTER builds on a query engine that supports two basic operations: prefix search and join. Both of...
Efficient interactive query expansion with CompleteSearch (2007)
Bast, Holger, Majumdar, Debapriyo, Weber, Ingmar
We present an efficient realization of the following interactive search engine feature: as the user is typing the query, words that are related to the last query word and that would lead to good hits...
Fast Routing in Road Networks using Transit Nodes (2007)
Bast, Holger, Funke, Stefan, Sanders, Peter, Schultes, Dominik
In Transit to Constant Time Shortest-Path Queries in Road Networks (2007)
Bast, Holger, Funke, Stefan, Matijevic, Domagoj, Sanders, Peter, Schultes, Dominik
Managing Helpdesk Tasks with CompleteSearch: A Case Study (2007)
CompleteSearch is a highly interactive search engine, which, instantly after every single keystroke, offers to the user various kinds of feedback, like promising query completions or refinements by...
The CompleteSearch Engine: Interactive, Efficient, and Towards IR & DB integration (2007)
We describe CompleteSearch, an interactive search engine that offers the user a variety of complex features, which at first glance have little in common, yet are all provided via one and the same...
Discovering a term taxonomy from term similarities using principal component analysis (2006)
Holger Bast, Georges Dupret, Debapriyo Majumdar, Benjamin Piwowarski
Abstract. We show that eigenvector decomposition can be used to extract a term taxonomy from a given collection of text documents. So far, methods based on eigenvector decomposition, such as latent...
Io-top-k: Index-access optimized top-k query processing (2006)
Holger Bast, Debapriyo Majumdar, Ralf Schenkel, Martin Theobald, Gerhard Weikum
Top-k query processing is an important building block for ranked retrieval, with applications ranging from text and data integration to distributed aggregation of network logs and sensor data. Top-k...
TRANSIT— ultrafast shortest-path queries with linear-time preprocessing (2006)
Holger Bast, Stefan Funke, Domagoj Matijevic
{bast,funke,dmatijev} at mpi-inf dot mpg dot de We introduce the concept of transit nodes, as a means for preprocessing a road network, with given coordinates for each node and a travel time for each...
ii Datum des Kolloquiums: 14. 05. 2007 (2006)
Annamária Kovács, Dekan Prof, Dr. Thorsten Herfet, Vorsitzender Prof, Dr. Raimund Seidel, ...
iii Abstract. The thesis deals with problems from two distint areas of scheduling theory. In the first part we consider the preemptive Sum Multicoloring (pSMC) problem. In an instance of pSMC,...
Matching algorithms are fast in sparse random graphs (2006)
Holger Bast, Kurt Mehlhorn, Guido Schäfer, Hisao Tamaki
Abstract. We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every...
Authors ’ Addresses Publication Notes (2006)
Holger Bast, Christian W. Mortensen, Ingmar Weber
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...
Matching algorithms are fast in sparse random graphs (2006)
Holger Bast, Kurt Mehlhorn, Guido Schäfer, Hisao Tamaki
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every non-maximum...
TRANSIT— ultrafast shortest-path queries with linear-time preprocessing (2006)
Holger Bast, Stefan Funke, Domagoj Matijevic
{bast,funke,dmatijev} at mpi-inf dot mpg dot de We introduce the concept of transit nodes, as a means for preprocessing a road network, with given coordinates for each node and a travel time for each...
Io-top-k: Index-access optimized top-k query processing (2006)
Holger Bast, Debapriyo Majumdar, Ralf Schenkel, Martin Theobald, Gerhard Weikum
Top-k query processing is an important building block for ranked retrieval, with applications ranging from text and data integration to distributed aggregation of network logs and sensor data. Top-k...
Output-sensitive autocompletion search (2006)
Holger Bast, Christian W. Mortensen, Ingmar Weber
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...
TRANSIT— ultrafast shortest-path queries with linear-time preprocessing (2006)
Holger Bast, Stefan Funke, Domagoj Matijevic
{bast,funke,dmatijev} at mpi-inf dot mpg dot de We introduce the concept of transit nodes, as a means for preprocessing a road network, with given coordinates for each node and a travel time for each...
Type less, find more: fast autocompletion search with a succinct index (2006)
We consider the following full-text search autocompletion feature. Imagine a user of a search engine typing a query. Then with every letter being typed, we would like an instant display of...
Io-top-k: Index-access optimized top-k query processing (2006)
Holger Bast, Debapriyo Majumdar, Ralf Schenkel, Martin Theobald, Gerhard Weikum
Top-k query processing is an important building block for ranked retrieval, with applications ranging from text and data integration to distributed aggregation of network logs and sensor data. Top-k...
Discovering a Term Taxonomy from Term Similarities Using Principal Component Analysis (2006)
Bast, Holger, Dupret, Georges, Majumdar, Debapriyo, Piwowarski, Benjamin, Ackermann, Markus, Berendt, Bettina, ...
We show that eigenvector decomposition can be used to extract a term taxonomy from a given collection of text documents. So far, methods based on eigenvector decomposition, such as latent semantic...
IO-Top-k: Index-Access Optimized Top-k Query Processing (2006)
Bast, Holger, Majumdar, Debapriyo, Schenkel, Ralf, Theobald, Martin, Weikum, Gerhard, Dayal, Umeshwar, ...
Top-$k$ query processing is an important building block for ranked retrieval, with applications ranging from text and data integration to distributed aggregation of network logs and sensor data....
Output-Sensitive Autocompletion Search (2006)
Bast, Holger, Mortensen, Christian Worm, Weber, Ingmar, Crestani, Fabio, Ferragina, Paolo, Sanderson, Mark
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...
Type Less, Find More: Fast Autocompletion Search with a Succinct Index (2006)
Bast, Holger, Weber, Ingmar, Efthimiadis, Efthimis N., Dumais, Susan, Hawking, David, Järvellin, Kalervo
We consider the following full-text search autocompletion feature. Imagine a user of a search engine typing a query. Then with every letter being typed, we would like an instant display of...
IO-Top-k at TREC 2006: Terabyte Track (2006)
Bast, Holger, Majumdar, Debapriyo, Schenkel, Ralf, Theobald, Martin, Weikum, Gerhard, Voorhees, Ellen M., ...
TRANSIT: Ultrafast Shortest-Path Queries with Linear-Time Preprocessing (2006)
Bast, Holger, Funke, Stefan, Matijevic, Domagoj, Demetrescu, Camil, Goldberg, Andrew, Johnson, David
Matching Algorithms are Fast in Sparse Random Graphs (2006)
Bast, Holger, Mehlhorn, Kurt, Schäfer, Guido, Tamaki, Hisao
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on $n$ vertices, with high probability every non-maximum...
IO-Top-k: Index-access Optimized Top-k Query Processing (2006)
Bast, Holger, Majumdar, Debapriyo, Schenkel, Ralf, Theobald, Martin, Weikum, Gerhard, Dayal, Umeshwar, ...
Top-$k$ query processing is an important building block for ranked retrieval, with applications ranging from text and data integration to distributed aggregation of network logs and sensor data....
IO-Top-k at TREC 2006: Terabyte Track (2006)
Bast, Holger, Majumdar, Debapriyo, Schenkel, Ralf, Theobald, Martin, Weikum, Gerhard, Voorhees, Ellen M., ...
This paper describes the setup and results of our contribution to the TREC 2006 Terabyte Track. Our implementation was based on the algorithms proposed in [IO-Top-k: Index-Access Optimized Top-K...
Towards Peer-to-Peer Web Search (2005)
Weikum, Gerhard, Bast, Holger, Canright, Geoffrey, Hales, David, Schindelhauer, Christian, Triantafillou, Peter
Towards Self-Organizing Query Routing and Processing for Peer-to-Peer Web Search (2005)
Weikum, Gerhard, Bast, Holger, Canright, Geoffrey, Hales, David, Schindelhauer, Christian, Triantafillou, Peter
The peer-to-peer computing paradigm is an intriguing alternative to Google-style search engines for querying and ranking Web content. In a network with many thousands or millions of peers the storage...
Towards Peer-to-Peer Web Search (2005)
Weikum, Gerhard, Bast, Holger, Canright, Geoffrey, Hales, David, Schindelhauer, Christian, Triantafillou, Peter
Insights from Viewing Ranked Retrieval as Rank Aggregation (2005)
Bast, Holger, Weber, Ingmar, Adachi, Jun, Shan, Wang, Vakali, Athena
Why Spectral Retrieval Works (2005)
Bast, Holger, Majumdar, Debapriyo, Marchionini, Gary, Moffat, Alistair, Tait, John, Baeza-Yates, Ricardo, ...
We introduce the \emph{synonymy graph} as a new angle of looking at spectral retrieval techniques, including latent semantic indexing (LSI) and its many successors. The synonymy graph is defined for...
Towards Self-Organizing Query Routing and Processing for Peer-to-Peer Web Search (2005)
Weikum, Gerhard, Bast, Holger, Canright, Geoffrey, Hales, David, Schindelhauer, Christian, Triantafillou, Peter
The peer-to-peer computing paradigm is an intriguing alternative to Google-style search engines for querying and ranking Web content. In a network with many thousands or millions of peers the storage...
Matching Algorithms Are Fast in Sparse Random Graphs (2004)
Bast,Holger, Mehlhorn,Kurt, Schäfer,Guido, Tamaki,Hisao
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every nonmaximum...
Matching Algorithms Are Fast in Sparse Random Graphs (2004)
Bast, Holger, Mehlhorn, Kurt, Schäfer, Guido, Tamaki, Hisao, Diekert, Volker, Habib, Michel
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every nonmaximum...
Matching Algorithms Are Fast in Sparse Random Graphs (2004)
Bast, Holger, Mehlhorn, Kurt, Schäfer, Guido, Tamaki, Hisao, Diekert, Volker, Habib, Michel
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every nonmaximum...
Bast,Holger, Mehlhorn,Kurt, Schäfer,Guido, Tamaki,Hisao
We consider the single-source many-targets shortest-path (SSMTSP) problem in directed graphs with non-negative edge weights. A source node $s$ and a target set $T$ is specified and the goal is to...
Bast, Holger, Mehlhorn, Kurt, Schäfer, Guido, Tamaki, Hisao
We consider the single-source many-targets shortest-path (SSMTSP) problem in directed graphs with non-negative edge weights. A source node $s$ and a target set $T$ is specified and the goal is to...