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

计算设备的普及带来了电子数据量的指数增长。如此海量的数据需要高效的算法进行处理、搜索和存储。在这种情况下，一种新的算法可以将求解速度从几年缩短到几分钟的CPU时间，或者证明不存在更好的解决方案。我们在四个明确的领域寻求这样的进步：+互联网上的流量测量。我们如何监控和学习互联网上的动态连接属性和使用模式？+搜索引擎的索引大小。搜索引擎使用索引数据结构(与书籍的索引相似)来加速搜索。在模式匹配问题中，我们只需要报告单词是否出现在文本中，而不是它的位置。我们调查在这种情况下索引需要多大。这个问题在其他方面也有应用，如DNA模式匹配和计算机病毒检测。+解决不完全信息的问题。考虑一个程序在请求到达时对其做出反应。该程序必须处理不知道下一个请求何时到达以及它将是什么类型的不确定性。此场景在机器人、内存读取请求(分页)和合同算法的调度中有应用。特别地，我们将研究其中请求序列已知具有特定的正则性(局部性)属性并且因此计算机求解器可以从该知识中受益的情况。我们认为在实践中出现的问题是难以解决的(NP-完全)。我们提出了加速搜索的算法，使得可以求解的实例的大小大大增加。我们研究的限制条件解决了各种问题，例如安排机场登机口的使用、医疗保健中的分流以及计算机资源分配。特别是，我们将研究间隔限制，它对诸如机场降落时段之类的任务进行建模，其中飞机必须在接近跑道时隔开。

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.