AIM:
Supporting Efficient Top-k Query Processing
With the massive amount of data everywhere, database systems are
facing new challenges: to support non-traditional fuzzy retrieval,
in contrast to the Boolean true/false of SQL queries,
for returning best matches in a ranking of results.
That is, even for structured data, we need a retrieval
system, much like a ''Google'' for relational databases.
Our goal is to support ranking queries, or top-k queries, for
matching data by "soft" conditions such as similarity, relevance, or
preference, in order to return best k answers.
Such ranking queries order results by combining the scores of fuzzy
predicates that are evaluated by different sources, which can be a
local database, a multimedia subsystem, or a Web source.
This project aims at developing semantics, algorithms, and systems
for effective ranking query processing.
Specifically, we address the following challenges, corresponding to
four major barriers in realizing our goals.
Projects
-
Rank Formulation: to achieve usability, we investigate
what the right mechanism is for users to interactively and exploratorily
express their desired ranking criteria.
-
Ranking Query Processing: to achieve efficiency,
we develop new query algorithms and data structures
for processing ranking queries.
-
Relational Integration: to achieve compatibility,
we study how to seamlessly integrate ranking as a first-class construct in
Boolean-based relational databases.
-
Semantic Extension: to achieve extensibility,
we look into meaningful and useful extensions of ranking to other kinds
of queries such as aggregation, and study how to support these extensions.
People
Alumni
Collaborators
- Supporting Ranking and Clustering as Generalized Order-By and Group-By.
C. Li, M. Wang, L. Lim, H. Wang, and K. C.-C. Chang.
In Proceedings of the 2007 ACM SIGMOD Conference (SIGMOD 2007), pages 127-138, Beijing, China, June 2007.
[PDF]
[Slides PPT]
- Progressive and Selective Merge: Computing Top-k with Ad-hoc Fanking Functions.
D. Xin, J. Han, and K. C.-C. Chang.
In Proceedings of the 2007 ACM SIGMOD Conference (SIGMOD 2007), pages 103-114, Beijing, China, June 2007.
[PDF]
[Slides PPT]
- Optimizing Top-k Queries for Middleware Access: A Unified Cost-based Approach.
S.-W. Hwang and K. C.-C. Chang.
In ACM Transactions on Database Systems (TODS), 32(1):5, March 2007.
[PDF]
- Probe Minimization by Schedule Optimization: Supporting Top-k Queries with Expensive Predicates.
S.-W. Hwang and K. C.-C. Chang.
In IEEE Transactions on Knowledge and Data Engineering (TKDE), 19(5):646-662, may 2007.
[PDF]
- Top-k Query Processing in Uncertain Databases.
M. A. Soliman, K. C.-C. Chang, and I. F. Ilyas.
In Proceedings of the 2007 IEEE 23rd International Conference on Data Engineering (ICDE 2007), pages 896-905, Istanbul, Turkey, April 2007.
[PDF]
[Slides PPT]
- Supporting Ad-hoc
Ranking Aggregates.
C. Li, K. C.-C. Chang, and I. F. Ilyas.
In Proceedings of the 2006 ACM SIGMOD Conference (SIGMOD 2006), pages 61-72, Chicago, June 2006.
[PDF]
[Slides PPT]
- Boolean +
Ranking: Querying a Database by K-Constrained Optimization.
Z. Zhang, S. Hwang, K. C.-C. Chang, M. Wang, C. Lang, and Y. Chang.
In Proceedings of the 2006 ACM SIGMOD Conference (SIGMOD 2006),
pages 359-370, Chicago, June 2006.
[PDF]
[Slides PPT]
-
RankSQL: Query Algebra and Optimization for Relational Top-k Queries. C. Li, K. C.-C. Chang, I. F. Ilyas, and S. Song.
In Proceedings of the 2005 ACM SIGMOD Conference (SIGMOD 2005),
pages 131-142, Baltimore, Maryland, June 2005.
[PDF]
[Slides PPT]
-
Optimizing Access Cost for Top-k Queries over Web Sources: A Unified Cost-based Approach
. S.-W. Hwang and K. C.-C. Chang.
In Proceedings of the 21st International Conference on Data Engineering
(ICDE 2005), Tokyo, Japan, April 2005.
Also as UIUC CS Technical Report UIUCDCS-R-2003-2324, Mar. 2003.
[PDF]
[Extended Version]
-
RankFP: A Framework for
Supporting Rank Formulation and Processing.
H. Yu, S.-W. Hwang, and K. C.-C. Chang.
In Proceedings of the 21st International Conference on Data Engineering
(ICDE 2005), Tokyo, Japan, April 2005.
[PDF]
-
Minimal Probing: Supporting
Expensive Predicates for Top-k Queries. K. C.-C. Chang and S.-W.
Hwang. In Proceedings of the 2002 ACM SIGMOD Conference (SIGMOD 2002),
pages 346-357, Madison, Wisconsin, June 2002. Also as UIUC CS Technical
Report UIUCDCS-R-2001-2258, Dec. 2001. [PDF]
[Extended
Version]
[Slides PPT]
Demos
-
URank: Formulation and Efficient Evaluation of Top-k Queries in Uncertain Databases.
Mohamed A. Soliman, Ihab F. Ilyas, and Kevin Chen-Chuan Chang.
In Proceedings of the 2007 ACM SIGMOD Conference (SIGMOD 2007), pages 1082-1084, Beijing, China, June 2007. Demonstration description.
[PDF]
-
RankSQL: Supporting Ranking Queries in Relational Database Management Systems.
Chengkai Li, Mohamed A. Soliman, Kevin Chen-Chuan Chang, and Ihab F. Ilyas.
In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB 2005),
pages 1342-1345, Trondheim, Norway, August 2005. Demonstration description.
[PDF]