Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
en:projects:mth:masterlthcamin1 [2010/11/24 17:00] karbasi |
en:projects:mth:masterlthcamin1 [2012/12/20 09:26] (current) behn |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | **A New Model for an Interactive Browser** | + | //Doctoral School or Master thesis project//\\ |
| + | \\ | ||
| + | |||
| + | |||
| + | |||
| + | =====Compression with Graphical Constraints: An Interactive Browser===== | ||
| In this work we consider the problem of searching in a | In this work we consider the problem of searching in a | ||
| - | database of objects . Contrary to traditional | + | database of objects with different popularities. Contrary to traditional |
| databases, users do not submit queries that are subsequently | databases, users do not submit queries that are subsequently | ||
| matched to objects. Instead, a search for a target | matched to objects. Instead, a search for a target | ||
| Line 21: | Line 27: | ||
| methods is the so-called //membership oracle//, which allows | methods is the so-called //membership oracle//, which allows | ||
| the search mechanism to ask a user questions of the form | the search mechanism to ask a user questions of the form | ||
| - | “does the target belong to set A”. Branson et al. deploy such an interactive | + | “does the target belong to set A”. It is well known that to find a target t one needs to submit at least H(μ) queries, on average, to the oracle where η is the popularity distribution on objects. Moreover, there exists an algorithm |
| - | method for object classification and evaluate it on the Ani- | + | (//Huffman coding//) that finds the target with only H(μ)+1 |
| - | mals with attributes database. A similar approach was used | + | queries on average. Having access to a membership oracle however is a strong assumption, as humans may |
| - | by Geman et al who formulated shape recognition as a | + | |
| - | coding problem and applied this approach to handwritten | + | |
| - | numerals and satellite images. Having access to a membership oracle however is a strong assumption, as humans may | + | |
| not necessarily be able to answer queries of the above type | not necessarily be able to answer queries of the above type | ||
| for any object set A. Moreover, the large number of possible | for any object set A. Moreover, the large number of possible | ||
| Line 32: | Line 35: | ||
| over large datasets prohibitive. | over large datasets prohibitive. | ||
| - | One way to address the above constraints is through a graphical model. | + | One way to address the above constraints is through a graphical model, i.e., each query set must conform to the constraints |
| + | imposed by a graph . For instance, items (with potentially different popularity) can be associated with vertices and each query is any set of | ||
| + | nodes that is path connected. In this context, as a special case the optimum algorithm for finding an object on a complete graph reduces to that of Huffman coding. | ||
| + | **Goals**\\ | ||
| + | |||
| + | Intuitively, the efficiency of an algorithm that can find a target by using the membership oracle with graphical constraints should depend on the entropy of the objects as well as the charactersitics of the graph. We would like to understand this depencency. | ||
| + | |||
| + | **Prerequisites:**\\ | ||
| + | Programming skills and basic notions of information theory | ||
| + | |||
| + | **Supervisor:**\\ | ||
| + | Amin Karbasi, amin.karbasi@epfl.ch\\ | ||
| + | |||
| + | **Professor:**\\ | ||
| + | Ruediger Urbanke, office INR 116 ruediger.urbanke@epfl.ch | ||
| [[en:projects:masterthesis:mtp|back to master projects menu]] | [[en:projects:masterthesis:mtp|back to master projects menu]] | ||
| + | |||