[University of Waterloo]
DAILY BULLETIN

Yesterday

Past days

Search

About the DB

Friday, May 27, 2005

  • Research to speed up computer searches
  • Three drama productions next year
  • Happening, never mind the weather
Editor:
Chris Redmond
credmond@uwaterloo.ca

Lag b'Omer


[Red and blue uniform shirt]

Scars on his chin don't mar Aaron Wilson's smile, after the Toronto Rock won the National Lacrosse League championship by defeating Arizona 19-13 on May 14 at the Air Canada Centre. Wilson -- by day, a staff member in UW's central stores, often spotted on his mail route -- was in his second season as a forward for the Rock, after more than a dozen years in junior leagues. What you can't see is the knee injury that kept him out of the lineup in 2003-04. What you can't smell, he maintains, is the "champagne and sweat" on his game jersey. He'll be back with the team next season.

Research to speed up computer searches

One of the most quoted lines in the English language is "To be or not to be." But if you look up it and similar phrases on the Internet with Google, you start to see some odd behaviour. For example, dropping the "not" gets only 5,000 rather than one million hits (no surprise) but takes about six times as long.

"The truth," says a release from UW's media relations office, "is that Google, and most other search engines, are based on keywords and patching phrases together and a fair bit of caching the results of common queries. Is this the best way to search a large database for phrases? And, what if you had genetic information (long strings of characters over the four-symbol alphabet ACGT)?"

Enter Ian Munro, faculty member in UW's school of computer science and Canada Research Chair in Algorithm Design.

"I want to develop ways of searching text that is time efficient and also takes a minimal amount of space," says Munro. "Most people only focus on one or the other but I focus on both and want to develop methods I can actually prove are the best."

His techniques allow someone to use only a modest amount of space to quickly search very large strings of data, and he doesn't use compression technology. "Standard compression technology is not the right solution for large data because you have to blow it back up to its original size to do anything with it," he explains.

"In my search methods, all the information is easily searchable and manipulatable, but it is about the same size as the raw data. That's a big reduction in file size from earlier attempts, which ended up being about 50 times larger than the actual data. So, there is no need to substantially increase the storage space needed or time needed to process it."

Munro accomplishes this seemingly impossible goal through the use of computing "trees". The tree allows someone to flow through the information selecting different combinations. For example, if you wanted to look through some very long binary code searching for the string "1000100," then it's simple. The search only has to be done once and to find numerous different possibilities someone only has to read off the information at different places along the tree.

To for "100" in "10000110010101011", instead of reading the entire string, a user could simply follow the pattern "100" through a tree representation and find both instances in the text (that is, positions 1 and 7). The usual methods of representing such trees are the main culprit in the "data bloat" and where the key advances are in the research.

ONE CLICK AWAY
  • Changes to the engineers' POETS Pub
  • Library's chat reference service is back
  • Longer training camps before this year's football season
  • WLU names new dean of arts . . . and interim graduate dean . . . and music dean
  • NSERC program 'to foster science literacy and numeracy'
  • 'Canada's Guide to Healthy Eating and Physical Activity'
  • More education is a Good Thing -- or not
  • 'How debt influences students' decisions', and more from OCUFA Forum
  • Kitchener symposium in June: 'Cultivating Intercultural Expression'
  • 'Branding' the University of Alberta
  • U of Guelph president comments on Ontario budget
  • And now, Trump University
  • The same trees can be altered to search the Shakespearean plays or the human genome. The only difference is that instead of two branches, there are 26 or four branches, respectively. The tree might start to look a lot more complicated but it is still the easiest and best way to do such searches.

    "Just because you have more computing power than 10 years ago doesn't mean you can just process anything you want," Munro says. "There are still problems of data size in computing, and now the problems are much bigger. The benefit of this process is that the search is done on the succinct form. We can do a complicated search with minimal storage space and computing time."

    Three drama productions next year

    "Three exhilarating productions" are planned by UW's drama department for 2005-06: Thornton Wilder's modern classic "Our Town", an evening of short plays directed by students in the directing class under the title "New Directions", and British playwright Timberlake Wertenbaker's award-winning drama "Our Country's Good".

    [A man and a woman]

    Student performers in "Kate Herself" from this spring's UpStart festival of short plays

    Here's how a news release from the lower floor of the Modern Languages building celebrates the playbill:

    "Since it opened to rave reviews in 1938, Thornton Wilder's 'Our Town' has become one of the classics of western theatre. In this play Wilder presents a picture of a small town, the fictional hamlet of Grover's Corners, where universal lessons about life can be found in a world which contains both virtue and vice, goodness and hypocrisy. 'Our Town' won Wilder his second Pulitzer Prize and went on to become one of the most performed plays of the twentieth century. Directed by guest artist Alan Sapp, 'Our Town' will be presented at the Theatre of the Arts from November 16-19, 2005.

    "'New Directions' represents a new departure for UW Drama. Following this year's successful fringe-style festival of student-composed plays, 'Upstart '05', 'New Directions' will present short plays staged by students from our directing class. More details will be announced at the beginning of the fall term. 'New Directions' will be presented in Studio 180 of Hagey Hall from February 1-4 and 8-11, 2006.

    "Based on Thomas Keneally's celebrated novel The Playmaker, Timberlake Wertenbaker's 'Our Country's Good' is set in the first Australian penal colony where a group of brutalised convicts rehearse a performance of George Farquhar's play 'The Recruiting Officer'. The play combines historical fact with fiction to illustrate the redemptive power of theatre, even under the direst of circumstances. It was first produced at the Royal Court Theatre in 1988, and in its premiere season was awarded the Laurence Olivier/BBC Award for Best New Play and the New York Drama Critics' Circle Award for Best New Foreign Play. It was also nominated for six 'Tonies'. Directed by faculty member Andrew Houston, 'Our Country's Good' will be presented at the Theatre of the Arts from March 15-18."

    WHEN AND WHERE
    Bookstore remainder sale, South Campus Hall concourse, winds up today.

    Engineering scunt (scavenger hunt) organized by 2nd year Software Engineering, starts 12 noon.

    CKMS yard sale fund-raiser for student radio, Saturday from 6 a.m., 317 Regina Street North.

    Engineering student machine shop power shutoff, Saturday 6 a.m. to 10 a.m., to install emergency stop buttons.

    Centre Stage Dance Saturday and Sunday, Humanities Theatre.

    Staff association annual general meeting Wednesday, June 1, 9 a.m., Davis Centre room 1302.

    Perimeter Institute "audience night" with a panel of researchers, June 1, 7 p.m., Waterloo Collegiate Institute, ticket information online.

    Happening, never mind the weather

    It'll be a Warrior Weekend, meaning that volunteers for the student life office have organized a program of activities tonight and Saturday night, mostly in the Student Life Centre. On tap (if I can use that expression for an event that's explicitly alcohol-free) will be dance lessons from the UW Breakers team, a "craft corner", and -- Saturday from 9 p.m. -- the "Mini Amazing Race" inside the SLC. There are also movies -- "National Treasure" and "The Incredibles" tonight, "Hitch" tomorrow night. Details, and registration information for the amazing race, can be found online.

    To mark the fifth anniversary of the Walkerton water disaster, the UW-based Canadian Water Network as well as other partners (including CRESTech and the municipality that includes Walkerton) is holding a Water and Public Health Training Workshop, "Converting Hindsight to Foresight", starting tomorrow. Over the course of a week, 33 graduate students and young professionals from universities across Canada will take part in a series of seminars that will expand their understanding of water and public health issues. Seminars will be conducted by some of the foremost experts in the field from across North America. Most of the activities will be held in Walkerton itself, a small town 100 kilometres northwest of Waterloo. A key component of the week is a public symposium Tuesday in the Walkerton Community Centre, with a keynote address by Ontario environment minister Leona Dombrowsky.

    LT3 -- the Centre for Learning and Teaching Through Technology -- has something special coming on Monday: "The Great Unsolved Mysteries in Canadian History Project". Peter Goldsworthy of LT3 explains that "The project, based at the University of Victoria, the Université de Sherbrooke, and the Ontario Institute for Studies in Education of the University of Toronto, has created a series of instructional websites based on the premise that students can be drawn into Canadian history and archival research through the enticement of solving historical 'cold crimes'. Historians Ruth Sandwell (OISE/UT) and Peter Gossage (Sherbrooke) will discuss the origins and the historical, political and pedagogical philosophy of the project. With the audience's help, they will demonstrate how the mystery sites 'work' to teach high school and university students about the practices as well as the content of Canadian history, transforming their ideas about what history is, as well as why it matters." This special event is jointly sponsored by the history department and LT3. It starts at 3:00 Monday, in Arts Lecture Hall room 208, and registration is online.

    A student discussion is set for Monday afternoon on "The Future of Hydrogen". As element number one in the periodic table it's pretty secure, I should think, but the organizers -- the UW Alternative Fuels Team -- mean the future of hydrogen as a fuel. Monday's event, starting at 5:00 in Davis Centre room 1350, will include speakers from General Motors and Hydrogenics Corporation, as well as Xianguo Li of the mechanical engineering department and Roydon Fraser of systems design. UWAFT will have a booth outside the lecture hall to attract those interested in the project, and its current car, an ethanol-powered Chevrolet Silverado, will be parked outside, says the team's Alain Boutros.

    CAR


    Communications and Public Affairs, University of Waterloo
    200 University Avenue West, Waterloo, Ontario N2L 3G1
    (519) 888-4567 ext. 3004
    www.bulletin.uwaterloo.ca | Yesterday's Daily Bulletin
    Copyright © 2005 University of Waterloo