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

用于网络、信息检索和调度的海量数据集的高效算法

• 批准号: 217254-2007
• 负责人: LopezOrtiz, Alejandro
• 金额: $ 2.11万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2007
• 资助国家: 加拿大
• 起止时间: 2007-01-01 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=365312
• 关键词: Efficient; algorithms; massive; data; sets

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.

计算设备的普及已经带来了电子数据量的指数增长。如此大量的数据需要有效的算法来处理，搜索和存储。在这种情况下，一种新的算法可以将解决方案的速度从几年降低到几分钟的CPU时间，或者证明不存在更好的解决方案。我们在四个明确的领域寻求这样的进步：+互联网上的流量测量。我们如何监控和了解互联网上的动态连接属性和使用模式？+搜索引擎的索引大小。搜索引擎使用索引数据结构（与书籍索引不同）来加速搜索。在模式匹配问题中，我们只需要报告单词是否出现在文本中，而不是它的位置。我们研究在这种情况下索引需要多大。这个问题在其他情况下也有应用，例如DNA模式匹配和计算机病毒检测。解决信息不完整的问题。考虑一个程序在请求到达时对其做出反应。程序必须处理不知道下一个请求何时到达以及它将是什么类型的不确定性。这个场景可以应用于机器人的运动规划、内存读取请求（分页）和合同算法的调度。特别地，我们将研究已知请求序列具有特定规律性（局部性）属性的情况，因此计算机求解器可以从这些知识中受益。约束编程。我们考虑在实践中出现的问题，但仍然是棘手的（NP完全）。我们提出的算法，加快了搜索的解决方案，这样可以解决的实例的大小大大增加。我们所研究的约束解决了各种各样的问题，如调度机场登机口的使用，医疗分流，计算机资源分配。特别是，我们将研究间距约束，该约束对机场着陆槽等任务进行建模，其中飞机在接近跑道时必须间隔开。