Events Calendar

PhD Student Colloquium: Megha Gupta (Robotics Research Lab) & Hien To (Information Laboratory)

Speaker: Megha Gupta & Hien To , Robotics Research Lab & Information Laboratory

Talk Title: Megha Gupta: Interactive Environment Exploration in Clutter; Hien To: Entropy-based Histograms for Selectivity Estimation

Series: CS Colloquium

Abstract: Presenter: Megha Gupta (Robotics Research Lab)

Title: Interactive Environment Exploration in Clutter

Robotic environment exploration in cluttered environments is a challenging problem. The number and variety of objects present not only make perception very difficult but also introduce many constraints for robot navigation and manipulation. In this talk, we investigate the idea of a robot exploring a small, bounded environment (eg. the shelf of a home refrigerator) by physically interacting with the objects in the environment. The presence of multiple objects results in partial and occluded views of the scene. This inherent uncertainty in the scene's state forces the robot to adopt an observe-plan-act strategy and interleave planning (which object to move, where to move) with execution (rearrangement of the objects). Objects occupying the space and potentially occluding other hidden objects are rearranged to reveal more of the unseen area. The environment is considered explored when the state (free or occupied) of every voxel in the volume is known. The presented algorithm can be easily adapted to real world problems like object search, taking inventory, and mapping. We evaluate our planner using various metrics, then present an implementation on the PR2 robot and use it for object search in clutter.


Presenter: Hien To (Information Laboratory)

Title: Entropy-based Histograms for Selectivity Estimation

Selectivity estimation is the task of estimating the size of the result set of a relational algebra operator. For a particular query, multiple execution plans can be generated with different ordering of operators. Thus, selectivity estimation of intermediate temporary relations significantly influences the choice of a query plan chosen by a query optimizer. Accurate estimations are crucial to generate optimal execution plans while bad estimations often lead to large overhead in performance.

Histograms have been extensively used for selectivity estimation by academics and have successfully been adopted by database industry. However, the estimation error is usually large for skewed distributions and biased attributes, which are typical in real-world data. Therefore, we propose effective models to quantitatively measure bias and selectivity based on information entropy. These models together with the principles of maximum entropy are then used to develop a class of entropy-based histograms that achieves near-optimal quality in linear runtime. We conducted an extensive set of experiments to compare the accuracy and efficiency of our proposed techniques with many other histogram-based techniques, showing the superiority of the entropy-based approaches for both equality and range queries.

Host: PhD Committee

Location: Henry Salvatori Computer Science Center (SAL) - 101

Audiences: Everyone Is Invited

Contact: Assistant to CS chair