CAREER: Algorithmic Techniques for Massive Data Sets

Polytechnic University Of New York, Brooklyn NY

Investigators

Abstract

A number of new applications have recently emerged that require the storage, maintenance, and analysis of massive amounts of data. Examples such as web search 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 can be 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 estimation and indexing, feedback-based approaches to selectivity estimation, association rule mining problems, and the approximate and precise evaluation of complex queries on large data sets. The problems studied in the second category are concerned with online search on the web, the study of random graph models for the web, and efficient computing with large web graphs and hypertext collections.