HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >

Please use this identifier to cite or link to this item:
Title: Reachability indexes for relational keyword search
Authors: Markowetz, Alexander
Yang, Yin
Papadias, Dimitris
Keywords: Keyword search
Reachability indexing
Relational databases
Issue Date: 2009
Citation: Proceedings of the IEEE International Conference on Data Engineering (ICDE), Shanghai, China, March 29-April 2, 2009, p. 1163-1166
Abstract: Due to its considerable ease of use, relational keyword search (R-KWS) has become increasingly popular. Its simplicity, however, comes at the cost of intensive query processing. Specifically, R-KWS explores a vast search space, comprised of all possible combinations of keyword occurrences in any attribute of every table. Existing systems follow two general methodologies for query processing: (i) graph based, which traverses a materialized data graph, and (ii) operator based, which executes relational operator trees on an underlying DBMS. In both cases, computations are largely wasted on graph traversals or operator tree executions that fail to return results. Motivated by this observation, we introduce a comprehensive framework for reachability indexing that eliminates such fruitless operations. We describe a range of indexes that capture various types of join reachability. Extensive experiments demonstrate that the proposed techniques significantly improve performance, often by several orders of magnitude.
Rights: © 2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Appears in Collections:CSE Conference Papers

Files in This Item:

File Description SizeFormat
ICDE09-KWS.pdfpre-published version226KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.