CAREER: Algorithmic Techniques for Massive Data Sets

最近出现了许多需要存储、维护和分析大量数据的新应用程序。网络搜索引擎、数据仓库和大型科学数据存储库等示例通常涉及多个用户同时搜索和探索的多TB数据。该研究项目调查在这样的大数据集的背景下产生的基本算法问题，研究这些问题的复杂性，开发新的技术来有效地解决这些问题，并在适当的系统和应用环境中实验验证所提出的技术。主要关注数据库和万维网搜索分析中出现的问题，更准确地说，研究的重点是关于存储，维护，分区，索引和近似表示非常大的数据集的问题，以及有效的探索，分析和精确和近似查询这样的数据。研究的问题类型可以分为两类，一类是主要由数据库领域的应用程序驱动的问题，另一类是由Web搜索和分析中的应用程序驱动的问题。在第一类中，该项目研究多维数据划分问题中出现的选择性估计和索引，反馈为基础的方法来估计选择性，关联规则挖掘问题，以及近似和精确的评估复杂的查询大数据集。第二类研究的问题涉及网络上的在线搜索，网络随机图模型的研究，以及大型网络图和超文本集合的有效计算。

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.