Efficient algorithms for massive data sets for networks, information retrieval and scheduling

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

The pervasiveness of computing devices has brought an exponential increase in the amount of electronic data. Such massive amounts of data necessitate efficient algorithms for processing, search and storage. In this case a novel algorithm can speed up solutions from years down to minutes of CPU time, or alternatively, prove that no better solution exists. We seek such advances in four well identified areas:+ Traffic measurement on the Internet. How can we monitor and learn dynamic connectivity properties and usage patterns on the Internet?+ Index size for search engines. Search engines use an index data structure (not unlike a book's index) to speedup  searches. In the pattern matching problem, we are only required to report whether the word appears in the text, but not its location. We investigate how large the index needs to be in this case. This problem has applications in other contexts, such as DNA pattern matching and computer virus detection.+ Solving problems with incomplete information. Consider a program reacting to requests as they arrive. The program must deal with the uncertainty of not knowing when the next request will arrive and of what type it will be. This scenario has applications for motion planning in robotics, memory-read requests (paging), and scheduling of contract algorithms. In particular we will study the case in which the request sequence is known to have specific regularity (locality) properties and hence the computer solver can benefit from this knowledge.+ Constraint programming. We consider problems that arise in practice yet are intractable (NP-complete). We propose algorithms that speed up the search for a solution such that the size of instances that can be solved is increased greatly. The constraints we have studied address a variety of problems such as scheduling airport gate usage, triage in health care, and computer resource allocation. In particular we will study the interdistance constraint, which models tasks such as landing slots in an airport in which airplanes must be spaced out in their approach to the runway.