Query-focused Sentence Compression in Linear Time
This work addresses the need for efficient sentence compression in search applications to reduce interface lags for users, though it is incremental as it builds on existing transition-based and dependency parse methods.
The paper tackles the problem of generating query-focused sentence compressions that meet length and lexical constraints, achieving an 11X speedup over baseline ILP methods while better reconstructing gold constrained shortenings.
Search applications often display shortened sentences which must contain certain query terms and must fit within the space constraints of a user interface. This work introduces a new transition-based sentence compression technique developed for such settings. Our query-focused method constructs length and lexically constrained compressions in linear time, by growing a subgraph in the dependency parse of a sentence. This theoretically efficient approach achieves an 11X empirical speedup over baseline ILP methods, while better reconstructing gold constrained shortenings. Such speedups help query-focused applications, because users are measurably hindered by interface lags. Additionally, our technique does not require an ILP solver or a GPU.