We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Scalable keyword search on large data streams.
- Authors
Qin, Lu; Yu, Jeffrey; Chang, Lijun
- Abstract
It is widely recognized that the integration of information retrieval ( IR) and database ( DB) techniques provides users with a broad range of high quality services. Along this direction, IR-styled m-keyword query processing over a relational database in an rdbms framework has been well studied. It finds all hidden interconnected tuple structures, for example connected trees that contain keywords and are interconnected by sequences of primary/foreign key relationships among tuples. A new challenging issue is how to monitor events that are implicitly interrelated over an open-ended relational data stream for a user-given m-keyword query. Such a relational data stream is a sequence of tuple insertion/deletion operations. The difficulty of the problem is related to the number of costly joins to be processed over time when tuples are inserted and/or deleted. Such cost is mainly affected by three parameters, namely, the number of keywords, the maximum size of interconnected tuple structures, and the complexity of the database schema when it is viewed as a schema graph. In this paper, we propose new approaches. First, we propose a novel algorithm to efficiently determine all the joins that need to be processed for answering an m-keyword query. Second, we propose a new demand-driven approach to process such a query over a high speed relational data stream. We show that we can achieve high efficiency by significantly reducing the number of intermediate results when processing joins over a relational data stream. The proposed new techniques allow us to achieve high scalability in terms of both query plan generation and query plan execution. We conducted extensive experimental studies using synthetic data and real data to simulate a relational data stream. Our approach significantly outperforms existing algorithms.
- Subjects
KEYWORD searching; RELATIONAL databases; INFORMATION retrieval; ALGORITHMS; QUERY (Information retrieval system)
- Publication
VLDB Journal International Journal on Very Large Data Bases, 2011, Vol 20, Issue 1, p35
- ISSN
1066-8888
- Publication type
Article
- DOI
10.1007/s00778-010-0190-x