Query segmentation is one of the first steps towards query understanding where complex queries are partitioned into semantically coherent word sequences. In this talk, we will first discuss our proposed query segmentation algorithm which uses query logs as the only input resource. Next, we will show how we can enhance the segmentation using Wikipedia titles and part-of-speech sequence information. In the past, segmentation strategies were mainly validated against manual annotations. We will present the first evaluation framework for Web search query segmentation based directly on IR performance. Our work shows that the goodness of a segmentation algorithm as judged through evaluation against a handful of human annotated segmentations hardly reflects its effectiveness in an IR-based setup. We then highlight the challenges of granularity in traditional segmentation, and consequent difficulties in IR application. Subsequently, we explore nested or hierarchical query segmentation, where segments are defined recursively as consisting of contiguous sequences of segments or query words, as an effective and powerful alternative representation of a query. We design a lightweight and unsupervised nested segmentation scheme, and propose how to use the tree arising out of the nested representation of a query to improve IR performance. We examine several aspects of the IR application framework and show that nested segmentation can be suitably exploited for the re-ranking of documents leading to significant gains over baselines that include the state-of-the-art "flat" segmentation strategies.