Impact of information representation on computation

信息表示对计算的影响

• 批准号: 238828-2011
• 负责人: Evans, William
• 金额: $ 1.75万
• 依托单位: University of British Columbia
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=570501
• 关键词: Impact; information; representation; computation

My research objectives, generally speaking, are to further our understanding of the fundamental and practical limits of information representation and computation. My research combines both systems/experimental and more theoretical viewpoints. For example, I'm interested in producing compressed representations of data. Typically, one requires that the original data can be reconstructed from the compressed representation. My research focuses instead on preserving functional aspects of the data. My students and I investigate how to compress a program so that it can execute in its compressed form, thus using less memory. We also explore compressing databases so that they still support query operations. Both applications share the basic approach of finding and exploiting redundancy in the original structured data. We rely on theoretical and experimental evaluation to determine if our approaches are practical and beneficial. Another main area of my research is in computation involving geometric objects. I'm interested in computation when the geometric input is imprecise or uncertain. For example, the closest taxi to a particular location depends on knowing the precise location of the taxis. If those locations are only known approximately, what is the appropriate answer? I'm also interested in understanding visibility between geometric objects, such as points on a terrain, in order to exploit the structure of this visibility relation, for example, to place guards that can see everything. These applications require the solution of fundamental algorithmic questions. In my research, I try to address these fundamental questions as well as create and test practical systems.

总的来说，我的研究目标是进一步了解信息表示和计算的基本和实际限制。我的研究结合了系统/实验和更多的理论观点。例如，我对生成数据的压缩表示感兴趣。通常，要求原始数据可以从压缩表示中重建。相反，我的研究侧重于保存数据的功能方面。我和我的学生研究如何压缩一个程序，使它能够以压缩的形式执行，从而使用更少的内存。我们还探讨了压缩数据库，使其仍然支持查询操作。这两个应用程序共享在原始结构化数据中查找和利用冗余的基本方法。我们依靠理论和实验评估来确定我们的方法是否实用和有益。