CAREER: Algorithmic Techniques for Massive Data Sets

点击翻译按钮获取中文摘要

A number of new applications have recently emerged that require the storage,maintenance, and analysis of massive amounts of data. Examples such as websearch engines, data warehouses, and large scientific data repositories often involve multiple terabytes of data that are simultaneously searched and explored by many users. This research project investigates fundamental algorithmic problems arising in the context of such large data sets, studies the complexity of these problems, develops new techniques for their efficient solution, and experimentally validates proposed techniques in the appropriate system and application context. The main focus is on problems arising in databases and in searching and analyzing the World-Wide Web.More precisely, the research focuses on problems concerning the storage, maintenance, partitioning, indexing, and approximate representation of very large data sets, and the efficient exploration, analysis and precise and approximate querying of such data. The types of problems that are studied canbe grouped into two categories, one consisting of problems motivated mainly by applications in the database area, and one motivated by applications in web search and analysis. In the first category, the project studies multi-dimensional data partitioning problems arising in selectivity estimationand indexing, feedback-based approaches to selectivity estimation, associationrule mining problems, and the approximate and precise evaluation of complexqueries on large data sets. The problems studied in the second category areconcerned with online search on the web, the study of random graph models forthe web, and efficient computing with large web graphs and hypertext collections.