Disclosed are, inter alia, methods, apparatus, data structures, computer readable media, mechanisms, and means for partitioning and filtering a search space of particular use for determining a longest prefix match thereon, such as for routing packets. One implementation uses one or more filtering mechanisms to filter portions of a lookup word against a first set of lookup values, such as, but not limited to the value of any corresponding portion of any entry in the search space. A set of possible matching prefixes defined by consecutive matching portions of the lookup word from the highest-order position are determined, and lookup operations are typically performed in parallel on each of these possible matching prefixes to generate a set of matching results (if any), which is typically used to identify the longest matching prefix.