Grant: Discovery Grants Program - Individual
University of Waterloo
$29,000.00
Efficient algorithms for massive data sets for networks, information retrieval and scheduling
EF 2008-09
Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
217254-2007
Name nom
LopezOrtiz, Alejandro
Department département
Computer Science, School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2008
Competition year année de concours
2007
Award amount
29000
Program id
RGPIN
Program nane en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
2
Nb partie
5
Application title
Efficient algorithms for massive data sets for networks, information retrieval and scheduling
Keyword
NA
Application summary
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.