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.